Неразрешимые фрагменты позитивных теорий свободных полугрупп

А. И. Зеткина, В. Г. Дурнев

Ярославский государственный университет им. П. Г. Демидова, ул. Советская, 14/2, Ярославль 150003

Аннотация: Доказана алгоритмическая неразрешимость нескольких простых фрагментов позитивных теорий свободных нециклических полугрупп, состоящих из позитивных формул с простыми кванторными приставками и с малым числом констант в их бескванторной части.

Ключевые слова: свободная полугруппа, позитивная формула.

УДК: 512+512.5+512.54+512.54.03

MSC: 35R30

Статья поступила: 21.04.2025
Окончательный вариант: 21.04.2025
Принята к печати: 05.07.2025

DOI: 10.33048/smzh.2025.66.507

 Англоязычная версия: Siberian Mathematical Journal, 2025, 66:5, 1171–1183