On the studies of Gennadii Semënovich Makanin on algorithmic questions of the theory of groups and semigroups

S. I. Adian

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 73 (2018) no. 3, pp. 553-568

Bibliographie

[M1] “Novyi razreshimyi sluchai problemy razresheniya ischisleniya predikatov pervoi stupeni”, Formalnaya logika i metodologiya nauki, Nauka, M., 1964, 125–153 | Zbl

[M2] “K probleme tozhdestva v konechno-opredelënnykh polugruppakh”, Dokl. AN SSSR, 171:2 (1966), 285–287 | MR | Zbl

[M3] “Problema sopryazhennosti v gruppe kos”, Dokl. AN SSSR, 182:3 (1968), 495–496 | MR | Zbl

[M4] “O normalizatorakh gruppy kos”, Matem. sb., 86(128):2(10) (1971), 171–179 | MR | Zbl

[M5] “O sistemakh uravnenii v svobodnykh gruppakh”, Sib. matem. zhurn., 13:3 (1972), 587–595 | MR | Zbl

[M6] “Problema razreshimosti uravnenii v svobodnoi polugruppe”, Dokl. AN SSSR, 233:2 (1977), 287–290 | MR | Zbl

[M7] “O range beskoeffitsientnykh uravnenii s chetyrmya neizvestnymi v svobodnoi polugruppe”, Matem. sb., 100(142):2(6) (1976), 285–311 | MR | Zbl

[M8] “Problema razreshimosti uravnenii v svobodnoi polugruppe”, Matem. sb., 103(145):2(6) (1977), 147–236 | MR | Zbl

[M9] “Raspoznavanie ranga beskoeffitsientnykh uravnenii v svobodnoi polugruppe”, Dokl. AN SSSR, 243:4 (1978), 851–854 | MR | Zbl

[M10] “Sistemy standartnykh uravnenii v slovakh v $n$-sloinom alfavite neizvestnykh”, Sib. matem. zhurn., 19:3 (1978), 637–645 | MR | Zbl

[M11] “Raspoznavanie ranga uravnenii v svobodnoi polugruppe”, Izv. AN SSSR. Ser. matem., 43:3 (1979), 547–602 ; “Recognition of the rank of equations in a free semigroup”, Math. USSR-Izv., 14:3 (1980), 499–545 | MR | Zbl | DOI

[M12] “Uravneniya v svobodnoi polugruppe”, Proceedings of the International Congress of Mathematicians. V. I (Helsinki, 1978), Acad. Sci. Fennica, Helsinki, 1980, 263–268 ; “Equations in a free semigroup”, Amer. Math. Soc. Transl. Ser. 2, 117, Amer. Math. Soc., Providence, RI, 1981, 1–6 | MR | Zbl | DOI

[M13] “Equations in a free semigroup”, Amer. Math. Soc. Transl. Ser. 2, 117 (1981), 1–6

[M14] “Uravneniya v svobodnoi gruppe”, Izv. AN SSSR. Ser. matem., 46:6 (1982), 1199–1273 ; “Equations in a free group”, Math. USSR-Izv., 21:3 (1983), 483–546 | MR | Zbl | DOI

[M15] “Issledovaniya po algoritmicheskim voprosam algebry”, Algebra, matematicheskaya logika, teoriya chisel, topologiya, Sbornik obzornykh statei. 1. K 50-letiyu Instituta, Tr. MIAN SSSR, 168, 1984, 197–217 (with S. I. Adyanom) ; “Investigations on algorithmic questions of algebra”, Proc. Steklov Inst. Math., 168 (1986), 207–226 (with S. I. Adian) | MR | Zbl

[M16] “Razreshimost universalnoi i pozitivnoi teorii svobodnoi gruppy”, Izv. AN SSSR. Ser. matem., 48:4 (1984), 735–749 ; “Decidability of the universal and positive theories of a free group”, Math. USSR-Izv., 25:1 (1985), 75–88 | MR | Zbl | DOI

[M17] “K voprosu o razreshimosti teorii svobodnoi gruppy”, Fundamentals of computation theory (Cottbus, 1985), Lecture Notes in Comput. Sci., 199, Springer, Berlin, 1985, 279–284 | DOI | MR | Zbl

[M18] “Ob odnom svedenii problemy razreshimosti teorii svobodnoi gruppy”, Matem. zametki, 40:1 (1986), 31–35 | MR | Zbl

[M19] “Razdelimye zamknutye kosy”, Matem. sb., 132(174):4 (1987), 531–540 ; “Separable closed braids”, Math. USSR-Sb., 60:2 (1988), 521–531 | MR | Zbl | DOI

[M20] “Ob odnom predstavlenii orientirovannogo uzla”, Dokl. AN SSSR, 299:5 (1988), 1060–1063 | MR | Zbl

[M21] “Ob odnom razreshimom fragmente elementarnoi teorii svobodnoi gruppy”, Voprosy kibernetiki, 134, Slozhnost vychislenii i prikladnaya matematicheskaya logika, Nauch. sovet po kompleksnoi probleme “Kibernetika” AN SSSR, M., 1988, 103–114 | MR | Zbl

[M22] “Ob odnom analoge teoremy Aleksandera–Markova”, Izv. AN SSSR. Ser. matem., 53:1 (1989), 200–210 ; “On an analogue of the Alexander–Markov theorem”, Math. USSR-Izv., 34:1 (1990), 201–211 | MR | Zbl | DOI

[M23] “Investigations on equations in a free group”, Word equations and related topics (Tübingen, 1990), Lecture Notes in Comput. Sci., 572, Springer, Berlin, 1992, 1–11 | DOI | MR

[M24] “On general solution of equations in a free semigroup”, Word equations and related topics (Rouen, 1991), Lecture Notes in Comput. Sci., 677, Springer, Berlin, 1993, 1–5 | DOI | MR | Zbl

[M25] “On general solution of word equations”, Results and trends in theoretical computer science (Graz, 1994), Lecture Notes in Comput. Sci., 812, Springer, Berlin, 1994, 251–263 (with H. Abdulrab) | DOI | MR

[M26] “Formal parametric equations”, Fundamentals of computation theory (Dresden, 1995), Lecture Notes in Comput. Sci., 965, Springer, Berlin, 1995, 353–362 (with H. Abdulrab, M. N. Maksimenko) | DOI | MR

[M27] “Multiplication of natural number parameters and equations in a free semigroup”, Trans. Amer. Math. Soc., 348:12 (1996), 4813–4824 | DOI | MR | Zbl

[M28] “Functions for the general solution of parametric word equations”, Logical foundations of computer science (Yaroslavl, 1997), Lecture Notes in Comput. Sci., 1234, Springer, Berlin, 1997, 189–202 (with H. Abdulrab, P. Goralcik) | DOI | MR | Zbl

[M29] “Parametrizatsiya reshenii nekotorykh uravnenii kvadratov v svobodnom monoide”, Diskret. matem., 11:3 (1999), 133–148 (with T. A. Makaninoi) | DOI | MR | Zbl

[M30] “Parametrisation of solutions of parametric equation in free monoid”, Theoret. Comput. Sci., 242:1-2 (2000), 403–475 (with T. A. Makanina) | DOI | MR | Zbl

[M31] “Functions for parametrization of solutions of an equation in a free monoid”, Trans. Amer. Math. Soc., 352:1 (2000), 1–54 (with T. A. Makanina) | DOI | MR | Zbl

[M32] “Towards parametrizing word equations”, Theor. Inform. Appl., 35:4 (2001), 331–350 (with H. Abdulrab, P. Goralčík) | DOI | MR | Zbl

[M33] “Parametrizatsiya reshenii uravneniya $x^{-1}y^{-1}xyz^{-1}v^{-1}zv=1$ v svobodnoi gruppe”, Diskret. matem., 13:2 (2001), 35–88 | DOI | MR | Zbl

[M34] “Uravnenie v svobodnoi gruppe, opredelyayuschee krashennye kosy”, Matem. zametki, 70:4 (2001), 591–602 (with A. G. Savushkinoi) | DOI | MR | Zbl

[M35] “Konechnaya parametrizatsiya reshenii uravnenii v svobodnom monoide. II”, Matem. sb., 195:4 (2004), 65–96 | DOI | MR | Zbl

[M36] “Konechnaya parametrizatsiya reshenii uravnenii v svobodnom monoide. I”, Matem. sb., 195:2 (2004), 41–90 | DOI | MR | Zbl

[M37] “Parametrizatsiya reshenii uravneniya $x_1x_2\dots x_{n-1}x_n=x_nx_{n-1}\dots x_2x_1$ v svobodnom monoide”, Matem. zametki, 89:6 (2011), 879–884 | DOI | MR | Zbl

[M38] “General solution of quadratic equations in free groups”, Proc. Yerevan State Univ., Phys. Math. Sci., 2015, no. 2(237), 62–65 (with A. Sh. Malkhasyan) | Zbl

[1] S. I. Adyan, “Matematicheskaya logika”, Matematicheskaya entsiklopediya, v. 3, Sovetskaya entsiklopediya, M., 1982, 568–574

[2] S. I. Adyan, “O fragmentakh slova $\Delta$ v gruppe kos”, Matem. zametki, 36:1 (1984), 25–34 | MR | Zbl

[3] S. I. Adyan, “Novye otsenki nechetnykh periodov beskonechnykh bernsaidovykh grupp”, Izbrannye voprosy matematiki i mekhaniki, Sbornik statei. K 150-letiyu so dnya rozhdeniya akademika Vladimira Andreevicha Steklova, Tr. MIAN, 289, MAIK “Nauka/Interperiodika”, M., 2015, 41–82 | DOI | Zbl

[4] E. Artin, “Theorie der Zöpfe”, Abh. Math. Sem. Univ. Hamburg, 4:1 (1925), 47–72 | DOI | MR | Zbl

[5] E. Artin, “Theory of braids”, Ann. of Math. (2), 48 (1947), 101–126 | DOI | MR | Zbl

[6] V. K. Bulitko, “Ob uravneniyakh i neravenstvakh v svobodnoi gruppe i svobodnoi polugruppe”, Uchenye zapiski matem. kafedr, 2, Tulskii gos. ped. in-t im. L. N. Tolstogo, Tula, 1970, 242–253 | MR

[7] A. Church, “An unsolvable problem of elementary number theory”, Amer. J. Math., 58:2 (1936), 345–363 | DOI | MR | Zbl

[8] A. Church, “A note on the Entscheidungsproblem”, J. Symbolic Logic, 1 (1936), 40–41 | DOI | Zbl

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

[10] Yu. L. Ershov, I. A. Lavrov, A. D. Taimanov, M. A. Taitslin, “Elementarnye teorii”, UMN, 20:4(124) (1965), 37–108 | MR | Zbl

[11] F. A. Garsaid, “Gruppa kos i drugie gruppy”, Matematika, 14:4 (1970), 117–132 ; F. A. Garside, “The braid group and other groups”, Quart. J. Math. Oxford Ser. (2), 20 (1969), 235–254 | Zbl | DOI | MR

[12] O. Kharlampovich, A. Myasnikov, “Elementary theory of free non-abelian groups”, J. Algebra, 302:2 (2006), 451–552 | DOI | MR | Zbl

[13] Yu. I. Khmelevskii, “Uravneniya v svobodnoi polugruppe”, Tr. MIAN SSSR, 107, 1971, 3–288 | MR | Zbl

[14] Yu. I. Khmelevskii, “Sistemy uravnenii v svobodnoi gruppe. I”, Izv. AN SSSR. Ser. matem., 35:6 (1971), 1237–1268 | MR | Zbl

[15] Yu. I. Khmelevskii, “Sistemy uravnenii v svobodnoi gruppe. II”, Izv. AN SSSR. Ser. matem., 36:1 (1972), 110–179 | MR | Zbl

[16] R. C. Lyndon, “Equations in free groups”, Trans. Amer. Math. Soc., 96 (1960), 445–457 | DOI | MR | Zbl

[17] A. A. Lorents, “O predstavleniyakh mnozhestv reshenii sistem uravnenii s odnim neizvestnym v svobodnoi gruppe”, Dokl. AN SSSR, 178:2 (1968), 290–292 | MR | Zbl

[18] A. A. Markov, “Osnovy algebraicheskoi teorii kos”, Tr. Matem. in-ta im. V. A. Steklova, 16, Izd-vo AN SSSR, M.–L., 1945, 3–53 | MR | Zbl

[19] A. A. Markov, “Nevozmozhnost nekotorykh algorifmov v teorii assotsiativnykh sistem”, Dokl. AN SSSR, 55:7 (1947), 587–590 | MR

[20] A. A. Markov, “Nevozmozhnost nekotorykh algorifmov v teorii assotsiativnykh sistem. II”, Dokl. AN SSSR, 58:3 (1947), 353–356 | MR | Zbl

[21] A. A. Markov, “Teoriya algorifmov”, Tr. MIAN SSSR, 42, Izd-vo AN SSSR, M.–L., 1954, 3–375 ; A. A. Markov, Theory of algorithms, The Israel Program for Scientific Translations, Jerusal, 1961, iv+444 pp. | MR | Zbl | MR

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

[23] Yu. V. Matiyasevich, “Diofantovo predstavlenie perechislimykh predikatov”, Izv. AN SSSR. Ser. matem., 35:1 (1971), 3–30 | MR | Zbl

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

[25] P. S. Novikov, “Ob algoritmicheskoi nerazreshimosti problemy tozhdestva slov v teorii grupp”, Tr. MIAN SSSR, 44, Izd-vo AN SSSR, M., 1955, 3–143 ; P. S. Novikov, “On the algorithmic insolvability of the word problem in group theory”, Amer. Math. Soc. Transl. Ser. 2, 9, Amer. Math. Soc., Providence, RI, 1958, 1–122 | MR | Zbl | DOI | MR | Zbl

[26] A. A. Razborov, “O sistemakh uravnenii v svobodnoi gruppe”, Izv. AN SSSR. Ser. matem., 48:4 (1984), 779–832 ; A. A. Razborov, “On systems of equations in a free group”, Math. USSR-Izv., 25:1 (1985), 115–162 | MR | Zbl | DOI

[27] Z. Sela, “Diophantine geometry over groups. VI. The elementary theory of a free group”, Geom. Funct. Anal., 16:3 (2006), 707–730 | DOI | MR | Zbl

[28] J. Surányi, Reduktionstheorie des Entscheidungsproblems im Prädikatenkalkül der ersten Stufe, Verlag der Ungarischen Akademie der Wissenschaften, Budapest, 1959, 216 pp. | MR | Zbl

[29] A. Tarski, A. Mostowski, R. M. Robinson, Undecidable theories, Stud. Logic Found. Math., North-Holland Publishing Co., Amsterdam, 1953, xi+98 pp. | MR | Zbl

[30] G. S. Tseitin, “Assotsiativnoe ischislenie s nerazreshimoi problemoi ekvivalentnosti”, Problemy konstruktivnogo napravleniya v matematike. 1, Sbornik rabot, Tr. MIAN SSSR, 52, Izd-vo AN SSSR, M.–L., 1958, 172–189 ; G. S. Tseĭtin, “An associative calculus with an unsolvable problem of equivalence”, Amer. Math. Soc. Transl. Ser. 2, 94, Amer. Math. Soc., Providence, RI, 1970, 73–92 | MR | Zbl | DOI

[31] A. M. Turing, “On computable numbers, with an application to the Entscheidungsproblem”, Proc. Lond. Math. Soc. (2), 42:3 (1936), 230–265 | DOI | MR | Zbl