Geodesic
On equations in free semigroups with certain constraints on their solutions
Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 120-129 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

It is shown that the solvability problem for equations in free semigroups with certain constraints on their solutions is algorithmically unsolvable. Bibl. – 23 titles. 
@article{ZNSL_2008_358_a6,
     author = {V. G. Durnev and O. V. Zetkina},
     title = {On equations in free semigroups with certain constraints on their solutions},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {120--129},
     year = {2008},
     volume = {358},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a6/}
}
TY  - JOUR
AU  - V. G. Durnev
AU  - O. V. Zetkina
TI  - On equations in free semigroups with certain constraints on their solutions
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2008
SP  - 120
EP  - 129
VL  - 358
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a6/
LA  - ru
ID  - ZNSL_2008_358_a6
ER  - 
%0 Journal Article
%A V. G. Durnev
%A O. V. Zetkina
%T On equations in free semigroups with certain constraints on their solutions
%J Zapiski Nauchnykh Seminarov POMI
%D 2008
%P 120-129
%V 358
%U http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a6/
%G ru
%F ZNSL_2008_358_a6
V. G. Durnev; O. V. Zetkina. On equations in free semigroups with certain constraints on their solutions. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 120-129. http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a6/

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

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

[3] V. G. Durnev, “Ob uravneniyakh na svobodnykh polugruppakh i gruppakh”, Matem. zametki, 16:5 (1974), 717–724 | MR | Zbl

[4] V. G. Durnev, “O pozitivnykh formulakh na svobodnykh polugruppakh”, Sib. matem. zhurn., 25:5 (1974), 1131–1137 | MR

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

[6] N. K. Kosovskii, “Nekotorye svoistva reshenii uravnenii v svobodnoi polugruppe”, Zap. nauchn. semin. LOMI, 32, Nauka, L., 1972, 21–28 | MR

[7] N. K. Kosovskii, “O mnozhestvakh, predstavimykh v vide reshenii uravnenii v slovakh i dlinakh”, Vtoraya vsesoyuznaya konfer. po matem. logike, Tezisy kratkikh soobschenii, M., 1972 | Zbl

[8] N. K. Kosovskii, “O reshenii sistem, sostoyaschikh odnovremenno iz uravnenii v slovakh i neravenstv v dlinakh slov”, Zap. nauchn. semin. LOMI, 33, Nauka, L., 1973, 24–29

[9] Kourovskaya tetrad, 11-e izd., dop., Novosibirsk, 1990

[10] G. S. Makanin, “Problema razreshimosti uravnenii v svobodnoi polugruppe”, DAN SSSR, 233:2 (1977), 287–290 | MR | Zbl

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

[12] G. S. Makanin, “Uravneniya v svobodnoi gruppe”, Izv. AN SSSR. Ser. matem., 46:6 (1982), 1199–1273 | MR | Zbl

[13] G. S. Makanin, “Razreshimost universalnoi i pozitivnoi teorii svobodnoi gruppy”, Izv. AN SSSR. Ser. matem., 48:4 (1984), 735–749 | MR | Zbl

[14] A. Sh. Malkhasyan, “O razreshimosti v podgruppakh uravnenii v svobodnoi gruppe”, Sb. Prikladnaya matematika, vyp. 2, 1986, 42–47 | Zbl

[15] Yu. V. Matiyasevich, “Diofantovost perechislimykh mnozhestv”, DAN SSSR, 130:3 (1970), 495–498 | MR

[16] Yu. V. Matiyasevich, “Svyaz sistem uravnenii v slovakh i dlinakh s 10-oi problemoi Gilberta”, Zap. nauchn. semin. LOMI, 8, Nauka, L., 1968, 132–144 | MR | Zbl

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

[18] Yu. I. Khmelevskii, Uravneniya v svobodnoi polugruppe, Nauka, M., 1971

[19] J. R. Büchi, S. Senger, “Definability in the existential theory of concatenation”, Z. Math. Logik Grundlag. Math., 34:4 (1988), 337–342 | DOI | MR | Zbl

[20] J. R. Büchi, S. Senger, “Coding in the existential theory of concatenation”, Arch. Math. Logik Grundlag., 26 (1986/87), 101–106 | DOI | MR | Zbl

[21] V. Diekert, C. Gutierrez, C. Hagenah, “The existential theory of equations with rational constraints in free groups is PSPACE-complete”, Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS' 01) (Dresden (Germany), 2001), Lecture Notes Computer Sci., 2010, eds. A. Ferreira, H. Reichel, Springer-Verlag, Berlin, 2001, 170–182 | MR | Zbl

[22] V. Diekert, C. Gutierrez, C. Hagenah, “The existential theory of equations with rational constraints in free groups is PSPACE-complete”, Information and Computation, 202 (2005), 105–140 | DOI | MR | Zbl

[23] K. U. Schulz, “Makanin's algorithm for word equations – two improvements and a generalization”, Lecture Notes Computer Sci., 572, 1990, 85–150 | MR