On equations with subsemigroup constraints on solutions in free semigroups

V. G. Durnev ; O. V. Zetkina

Čebyševskij sbornik, Tome 11 (2010) no. 3, pp. 78-87.

Bibliographie

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

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

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

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

[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., “Nekotorye svoistva reshenii uravnenii v svobodnoi polugruppe”, Zapiski nauchn. seminarov Leningr. otd. Matem. in-ta. AN SSSR, 32, L., 1972, 21–28 | MR

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

[8] Kosovskii N. K., “O reshenii sistem, sostoyaschikh odnovremenno iz uravnenii v slovakh i neravenstv v dlinakh slov”, Zapiski nauchn. seminarov Leningr. otd. Matem. in-ta. AN SSSR, 33, L., 1973, 24–29

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

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

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

[12] Makanin G. S., “Uravneniya v svobodnykh gruppakh”, Izv. AN SSSR. Ser. matem., 46:6 (1982), 1199–1274 | MR

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

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

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

[16] Matiyasevich Yu. V., “Svyaz sistem uravnenii v slovakh i dlinakh s 10-oi problemoi Gilberta”, Issledovaniya po konstruktivnoi matematike i matematicheskoi logike, Zapiski nauchn. seminarov Leningr. otd. Matem. in-ta. AN SSSR, 8, L., 1968, 132–143

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

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

[19] Diekert V., Makanin's Algorithm for Solving Word Equations with Regular Constraints, Report No 1998/02, Fakultat Informatik. Universitat Stuttgart, 1998 (Preliminary version of the chapter in M. Lothaire, Algebraic Combinatorics on Words)

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

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

[22] Buchi J. R., Senger S., “Definability in the existential theory of concatenation”, Z. Math. Log. und Grundl. Math., 34:4 (1988), 337–342 | MR

[23] Buchi J. R., Senger S., “Coding in the existential theory of concatenation”, Arch. Math. Logik, 26 (1986/87), 101–106 | MR

[24] Schulz K. U., “Makanin's Algprithm for Word Equations — Two Improvements and a Generalization”, Lecture Notes in Computer Science, 572, 1990, 85–150 | MR