Geodesic
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/