Неразрешимые фрагменты позитивных теорий свободных полугрупп
Неразрешимые фрагменты позитивных теорий свободных полугрупп
Сибирский математический журнал, 66, 5, 854-869 (2025)
Аннотация:
Доказана алгоритмическая неразрешимость нескольких простых фрагментов позитивных теорий свободных нециклических полугрупп, состоящих из позитивных формул с простыми кванторными приставками и с малым числом констант в их бескванторной части.
Литература:
- Дурнев В. Г., Зеткина А. И. Неразрешимые фрагменты позитивной теории свободной полугруппы с простыми кванторными приставками и малым числом констант // Материалы международной конференции «Алгебра и математическая логика: теория и приложения», посвященной 130-летию со дня рождения основателя кафедры алгебры Казанского университета члена-корреспондента АН СССР Николая Григорьевича Чеботарева и 80-летия со дня рождения заведующего кафедрой академика АН РТ Марата Мирзаевича Арсланова (г. Казань, 27 июня–1 июля 2024 г.). Казань: Казанский (Приволжский) федеральный университет, 2024. С. 200–201.
- Quine W. Concatenation as a basis for arithmetic // J. Symbol. Logic. 1946. V. 11. P. 105–114.
- Tarski A., Mostowski A., Robinson R. M. Undecidable theories. Amsterdam: Noth-Holland Publ. Company, 1953.
- Мерзляков Ю. И. Позитивные формулы на свободных группах // Алгебра и логика. 1966. Т. 5, № 4. С. 25–42.
- Маканин Г. С. Разрешимость универсальной и позитивной теорий свободной группы // Изв. АН СССР. Сер. мат. 1984. Т. 48, № 4. С. 735–749.
- Kharlampovich O. G., Myasnikov A. G. Elementary theory of free non-abelian groups // J. Algebra. 2006. V. 302. P. 451–552.
- Дурнев В. Г. Позитивная теория свободной полугруппы // Докл. АН СССР. 1973. Т. 211, № 4. С. 772–774.
- Дурнев В. Г. О позитивных формулах на свободных полугруппах // Сиб. мат. журн. 1974. Т. 25, № 6. С. 1131–1137.
- Хмелевский Ю. И. Уравнения в свободной полугруппе. М.: Наука, 1971.
- Косовский Н. К. Некоторые свойства решений уравнений в свободной полугруппе // Зап. науч. семин. Ленингр. отд. Мат. ин-та. им. В. А. Стеклова АН СССР. 1972. Т. 32. С. 21–28.
- Дурнев В. Г. Неразрешимость позитивной $\forall \exists^3$ -теории свободной полугруппы // Сиб. мат. журн. 1995. Т. 36, № 5. С. 1067–1080.
- Karhumaki J., Mignosi F., Plandowski W. On the expressibility of languages by word equations with a bounded number of variables // Bull. Belg. Math. Soc. 2001. V. 8, N 2. P. 293–303.
- Марченков С. С. Неразрешимость позитивной $\forall \exists$-теории свободной полугруппы // Сиб. мат. журн. 1982. Т. 23, № 1. С. 196–198.
- Маканин Г. С. Проблема разрешимости уравнений в свободной полугруппе // Мат. сб. 1977. Т. 103, № 2. С. 147–236.
- Дурнев В. Г. О позитивной теории свободной полугруппы // Вопросы теории групп и полугрупп. Тула: Тульск. гос. пед. ин-т. им. Л. Н. Толстого, 1972. С. 122–172.
- Перязев Н. А. Позитивные теории свободных моноидов // Алгебра и логика. 1993. Т. 32, № 2. С. 148–159.
- Адян С. И., Дурнев В. Г. Алгоритмические проблемы для групп и полугрупп // Успехи мат. наук. 2000. Т. 55, № 2. С. 3–94.
Зеткина Алена Игоревна (ORCID 0009-0006-2347-3662)
- Ярославский государственный университет им. П. Г. Демидова,
ул. Советская, 14/2, Ярославль 150003
E-mail: a.zetkina1@uniyar.ac.ru
Дурнев Валерий Георгиевич (ORCID 0000-0003-1731-3372)
- Ярославский государственный университет им. П. Г. Демидова,
ул. Советская, 14/2, Ярославль 150003
E-mail: durnev@uniyar.ac.ru
Статья поступила 21 апреля 2025 г.
После доработки — 21 апреля 2025 г.
Принята к публикации 5 июля 2025 г.