On ``simple'' algorithmically undecidable fragments of elementary theory of an infinitely generated free semigroup
Čebyševskij sbornik, Tome 21 (2020) no. 4, pp. 56-71
Voir la notice de l'article provenant de la source Math-Net.Ru
We prove algorithmic undecidability of $\exists \forall^2 \exists^3$-theory for a free semigroup of countable rank. This strengthens the classical Quine's (1946) result [1] on algorithmic undecidability of elementary theory of an arbitrary non-cyclic free semigroup.
Keywords:
free semigroups, elementary theories.
@article{CHEB_2020_21_4_a6,
author = {V. G. Durnev and O. V. Zetkina and A. I. Zetkina},
title = {On ``simple'' algorithmically undecidable fragments of elementary theory of an infinitely generated free semigroup},
journal = {\v{C}eby\v{s}evskij sbornik},
pages = {56--71},
publisher = {mathdoc},
volume = {21},
number = {4},
year = {2020},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/CHEB_2020_21_4_a6/}
}
TY - JOUR AU - V. G. Durnev AU - O. V. Zetkina AU - A. I. Zetkina TI - On ``simple'' algorithmically undecidable fragments of elementary theory of an infinitely generated free semigroup JO - Čebyševskij sbornik PY - 2020 SP - 56 EP - 71 VL - 21 IS - 4 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/CHEB_2020_21_4_a6/ LA - ru ID - CHEB_2020_21_4_a6 ER -
%0 Journal Article %A V. G. Durnev %A O. V. Zetkina %A A. I. Zetkina %T On ``simple'' algorithmically undecidable fragments of elementary theory of an infinitely generated free semigroup %J Čebyševskij sbornik %D 2020 %P 56-71 %V 21 %N 4 %I mathdoc %U http://geodesic.mathdoc.fr/item/CHEB_2020_21_4_a6/ %G ru %F CHEB_2020_21_4_a6
V. G. Durnev; O. V. Zetkina; A. I. Zetkina. On ``simple'' algorithmically undecidable fragments of elementary theory of an infinitely generated free semigroup. Čebyševskij sbornik, Tome 21 (2020) no. 4, pp. 56-71. http://geodesic.mathdoc.fr/item/CHEB_2020_21_4_a6/