О неразрешимости теорий подмножеств некоторых унаров

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

В данной работе исследуются алгоритмические свойства унаров с разнозначной функцией. Мы доказываем, что теория любого такого унара допускает элиминацию кванторов при подходящем обогащении сигнатуры счётным множеством предикатных символов. Устанавливаются необходимые и достаточные условия для того, чтобы элиминация кванторов была эффективной, и формулируется критерий разрешимости теорий таких унаров. С помощью полученного критерия приводится пример такого унара с разрешимой теорией, что теория унара его подмножеств неразрешима.

Об авторах

Б. Н. Карлов

Тверской государственный университет

Автор, ответственный за переписку.
Email: bnkarlov@gmail.com
Россия, Тверь

Список литературы

  1. Mostowski A. On direct products of theories // Journal of Symbolic Logic. 1952. V. 17. N 3. P. 1–31. https://doi.org/10.1016/S0049-237X(09)70257-5
  2. Marini C., Simi G., Sorbi A., Sorrentino M. A note on algebras of languages // Theoretical Computer Science. 2011. V. 412. P. 6531–6536. https://doi.org/10.1016/j.tcs.2011.08.022
  3. Коновалов А.С., Селиванов В.Л. Булевы алгебры регулярных языков // Алгебра и логика. 2013. Т. 52. № 6. С. 676–711.
  4. Dudakov S.M. On undecidability of concatenation theory for one-symbol languages // Lobachevskii Journal of Mathematics. 2020. V. 41. N 2. P. 168–175. https://doi.org/10.1134/S1995080220020055
  5. Dudakov S., Karlov B. On decidability of theories of regular languages // Theory of Computing Systems. 2021. V. 65. N 3. P. 462–478.https://doi.org/10.1007/s00224-020-09995-4
  6. Ehrenfeucht A. Decidability of the theory of one function // Notices of the American Mathematical Society. 1959. V. 6. P. 268.
  7. Иванов А.А. Полные теории унаров // Алгебра и логика. 1984. Т. 23. № 1. С. 48–73.
  8. Иванов А.А. О полных теориях унаров // Сибирский математический журнал. 1986. Т. 27. № 1. С. 57–69.
  9. Карлов Б.Н. Об элементарной эквивалентности некоторых уноидов и уноидов их подмножеств // Вестник ТвГУ. Серия: Прикладная математика. 2021. Т. 3. С. 18–32.https://doi.org/10.26456/vtpmk620
  10. Дудаков С.М. Об алгоритмических свойствах алгебры конечных подмножеств некоторых уноидов // Вестник ТвГУ. Серия: Прикладная математика. 2019. Т. 4. С. 108–116. https://doi.org/10.26456/vtpmk550
  11. Карлов Б.Н. О некоторых свойствах уноидов подмножеств // Актуальные проблемы прикладной математики, информатики и механики: Сборник трудов Международной научной конференции, Воронеж, 13–15 декабря 2021 года. Воронеж: Общество с ограниченной ответственностью “Вэлборн”, 2022. С. 1594–1600.
  12. Monk J.D. Mathematical logic. New York: Springer, 1976. 542 p. https://doi.org/10.1007/978-1-4684-9452-5

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2024