Undecidable fragments of positive theories of free semigroups

A. I. Zetkina, V. G. Durnev

Demidov Yaroslavl State University, Yaroslavl, Russia

Abstract: We prove the algorithmic undecidability of several simple fragments of the positive theories of free noncyclic semigroups, consisting of positive formulas with simple quantifier prefixes and with a small number of constants in their quantifier-free part.

Keywords: free semigroup, positive formula.

UDC: 512+512.5+512.54+512.54.03

MSC: 35R30

Received: 21.04.2025
Revised: 21.04.2025
Accepted: 05.07.2025

DOI: 10.33048/smzh.2025.66.507

 English version: Siberian Mathematical Journal, 2025, 66:5, 1171–1183