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/

[1] Quine W., “Concatenation as a basis for arithmetic”, J. Symbolic Logic, 11 (1946), 105–114 | DOI | MR | Zbl

[2] Durnev V. G., “O pozitivnoi teorii svobodnoi polugruppy”, Voprosy teorii grupp i polugrupp, Tulsk. gos. ped. in-t. imeni L. N. Tolstogo, Tula, 1972, 122–172 | MR

[3] Durnev V. G., “Pozitivnaya teoriya svobodnoi polugruppy”, DAN SSSR, 211:4 (1973), 772–774 | MR | Zbl

[4] Marchenkov S. S., “Nerazreshimost pozitivnoi $\forall\exists$-teorii svobodnoi polugruppy”, Sib. matem. zhurn., 23:1 (1982), 196–198 | MR | Zbl

[5] Durnev V. G., “Nerazreshimost pozitivnoi $\forall\exists^3$-teorii svobodnoi polugruppy”, Sib. matem. zhurn., 36:5 (1995), 1067–1080 | MR | Zbl

[6] Kosovskii N. K., Elementy matematicheskoi logiki i ee prilozheniya k teorii subrekursivnykh algoritmov, Izd-vo LGU, L., 1981, 192 pp. | MR

[7] Karhumaki J., Mignosi F., Plandowski W., “On the expressibility of languages by word equations with a bounded number of variables”, Bull. Belg. Math. Soc., 8:2 (2001), 293–303 | MR

[8] Lothaire M., Algebraic Combinatorics on Words, Cambridge Univ. Press, 2002, 504 pp. | MR | Zbl

[9] Makanin G. S., “Problema razreshimosti uravnenii v svobodnoi polugruppe”, Matematicheskii sbornik, 103(145):6 (1977), 147–236 | Zbl

[10] Taimanov A. D., Khmelevskii Yu. I., “Razreshimost universalnoi teorii svobodnoi polugruppy”, Sib. matem. zhurn., 21:1 (1980), 228–230 | MR | Zbl

[11] Merzlyakov Yu. I., “Pozitivnye formuly na svobodnykh gruppakh”, Algebra i logika, 5:4 (1966), 25–42 | Zbl

[12] Vazhenin Yu. M., Rozenblat B. V., “Razreshimost pozitivnoi teorii schetnoporozhdennoi polugruppy”, Matem. sbornik, 116(158):1(9) (1981), 120–127 | MR | Zbl

[13] Makanin G. S., “Razreshimost universalnoi i pozitivnoi teorii svobodnoi gruppy”, Izv. AN SSSR. Seriya matem., 1984, no. 2, 735–749

[14] Novikov P. S., “Ob algoritmicheskoi nerazreshimosti problemy tozhdestva slov v teorii grupp”, Trudy MIAN, 44, 1955 | MR | Zbl

[15] Borisov V. V., “Prostye primery grupp s nerazreshimoi problemoi tozhdestva”, Matem. zametki, 6:5 (1969), 521–532 | Zbl

[16] Matiyasevich Yu. V., “Prostye primery nerazreshimykh assotsiativnykh ischislenii”, Dokl. AN SSSR, 173:6 (1967), 1264–1266 | Zbl

[17] Schulz Klaus U., Makanin's Algorithm — Two Improvements and a generalization, Habilitationsschrift, Wilhelm-Schickard-Institut fur Informatik, 1990, 106 pp.

[18] Peryazev N. A., O pozitivnoi ekvivalentnosti svobodnykh polugrupp, Izd-vo Irkutskogo VTs SO AN SSSR, Irkutsk, 1986, 14 pp.