Sequences close to periodic

An. A. Muchnik   ; Yu. L. Pritykin   ; A. L. Semenov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 64 (2009) no. 5, pp. 805-871

Résumé

This paper is a survey of concepts and results connected with generalizations of the notion of a periodic sequence, both classical and new. The topics discussed relate to almost periodicity in such areas as combinatorics on words, symbolic dynamics, expressibility in logical theories, computability, Kolmogorov complexity, and number theory. Bibliography: 124 titles.

Détail

Keywords: combinatorics on words, symbolic dynamics, decidability of logical theories, almost periodic sequence, morphic sequence, Thue–Morse sequence, complexity of a sequence, Sturmian sequences.

Bibliographie

[1] J. S. Hadamard, “Les surfaces à courbures opposées et leurs lignes géodésiques”, J. de Math. (5), 4 (1898), 27–73 | Zbl

[2] G. D. Birkhoff, “Nouvelles recherches sur les systèmes dynamiques”, Memoriae Pont. Acad. Scient. Novi Lyncaei, 1 (1935), 85–216

[3] B. Hasselblatt, A. Katok, “The development of dynamics in the 20th century and the contribution of Jürgen Moser”, Ergodic Theory Dynam. Systems, 22:5 (2002), 1343–1364 | DOI | MR | Zbl

[4] H. M. Morse, “Recurrent geodesics on a surface of negative curvature”, Trans. Amer. Math. Soc., 22:1 (1921), 84–100 | DOI | MR | Zbl

[5] M. Morse, G. A. Hedlund, “Symbolic dynamics”, Amer. J. Math., 60:4 (1938), 815–866 | DOI | MR | Zbl

[6] M. Morse, G. A. Hedlund, “Symbolic dynamics. II. Sturmian trajectories”, Amer. J. Math., 62:1 (1940), 1–42 | DOI | MR | Zbl

[7] A. Thue, “Über unendliche Zeichenreihen”, Norske Vidensk. Selsk. Skrifter. I. Mat. Nat. Kl., 7 (1906), 1–22; Selected mathematical papers, Universitetsforlaget, Oslo, 1977, 139–158 | MR | Zbl

[8] A. Thue, “Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen”, Norske Vidensk. Selsk. Skrifter. I. Mat. Nat. Kl., 1 (1912), 1–67 ; Selected mathematical papers, Universitetsforlaget, Oslo, 1977, 413–478 | Zbl | MR | Zbl

[9] S. I. Adjan, Defining relations and algorithmic problems for groups and semigroups, Proc. Steklov Inst. Math., 85, Amer. Math. Soc., Providence, RI, 1966 | MR | MR | Zbl

[10] A. L. Semenov, “On certain extensions of the arithmetic of addition of natural numbers”, Math. USSR-Izv., 15:2 (1980), 401–418 | DOI | MR | Zbl | Zbl

[11] A. L. Semenov, “Logical theories of one-place functions on the set of natural numbers”, Math. USSR-Izv., 22:3 (1984), 587–618 | DOI | MR | Zbl

[12] Yu. L. Pritykin, “Pochti periodichnost, konechno-avtomatnye preobrazovaniya i voprosy effektivnosti”, Izv. vuzov. Matem., 2010, no. 1, 74–87 ; Almost periodicity, finite automata mappings and related effectiveness issues, , 2006 arXiv: cs/0607009

[13] M. A. Raskin, “Ob otsenke regulyatora avtomatnogo obraza pochti periodicheskoi posledovatelnosti”, Trudy XXVIII konferentsii molodykh uchenykh, Izd-vo MGU, M., 2006, 181–185

[14] A. Yu. Rumyantsev, M. A. Ushakov, “Forbidden substrings, Kolmogorov complexity and almost periodic sequences”, STACS{'}06, 23rd Annual Symposium on Theoretical Aspects of Computer Science (Marseile, 2006), Lecture Notes in Comput. Sci., 3884, ed. B. Durand et al., Springer, Berlin, 2006, 396–407 | DOI | MR | Zbl

[15] Kolmogorovskii seminar, http://kolmsem.math.ru

[16] Seminar “faktornye yazyki”, http://math.nsc.ru/seminar/lang/2009.html

[17] J.-P. Allouche, J. Shallit, “The ubiquitous Prouhet–Thue–Morse sequence”, Sequences and their applications (Singapore, 1998), Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, London, 1999, 1–16 | MR | Zbl

[18] J. Berstel, D. Perrin, “The origins of combinatorics on words”, European J. Combin., 28:3 (2007), 996–1022 | DOI | MR | Zbl

[19] J.-P. Allouche, A. Arnold, J. Berstel, S. Brlek, W. Jockusch, S. Plouffe, B. Sagan, “A relative of the Thue–Morse sequence”, Formal power series and algebraic combinatorics (Montreal, PQ, 1992), Discrete Math., 139, no. 1–3, 1995, 455–461 | MR | Zbl

[20] M. Euwe, “Mengentheoretische Betrachtungen über das Schachspiel”, Proc. Konin. Akad. Wetenschappen, Amsterdam, 32 (1929), 633–642 | Zbl

[21] M. Morse, “Abstract 360: a solution of the problem of infinite play in chess”, Bull. Amer. Math. Soc., 44 (1938), 632 | MR

[22] M. Morse, G. A. Hedlund, “Unending chess, symbolic dynamics and a problem in semi-groups”, Duke Math. J., 11:1 (1944), 1–7 | DOI | MR | Zbl

[23] M. E. Prouhet, “Mémoire sur quelques relations entre les puissances des nombres”, Comptes Rendus des Séances de l'Académie des Sciences, 33 (1851), 225; http://gallica.bnf.fr/ark:/12148/bpt6k29901.image.f227.langFR | Zbl

[24] G. Tarry, “Question 4100”, L'intermédiaire des mathématiciens, 19 (1912), 200

[25] E. B. Escott, “Logarithmic series”, Quart. J., 41:2 (1910), 141–156 | Zbl

[26] E. B. Escott, “The calculation of logarithms”, Quart. J., 41:2 (1910), 157–167 | MR | Zbl

[27] G. H. Hardy, E. M. Wright, An introduction to the theory of numbers, 5th edition, The Clarendon Press, Oxford Univ. Press, New York, 1979 | MR | Zbl

[28] A. O. Gelfond, “Sur les nombres qui ont des propriétés additives et multiplicatives données”, Acta Arith., 13 (1968), 259–265 | MR | Zbl

[29] C. Mauduit, J. Rivat, “Sur un problème de Gelfond: la somme des chiffres des nombres premiers”, Ann. of Math. (to appear)

[30] P. S. Novikov, S. I. Adjan, “Infinite periodic groups. I”, Math. USSR Izv., 2:1 (1968), 209–236 | DOI | MR | Zbl

[31] P. S. Novikov, S. I. Adjan, “Infinite periodic groups. II”, Math. USSR Izv., 2:2 (1968), 241–479 | DOI | MR | Zbl

[32] P. S. Novikov, S. I. Adjan, “Infinite periodic groups. III”, Math. USSR Izv., 2:3 (1968), 665–685 | DOI | MR | Zbl

[33] S. I. Adian, The Burnside problem and identities in groups, Ergeb. Math. Grenzgeb., 95, Springer-Verlag, Berlin–New York, 1979 | MR | MR | Zbl | Zbl

[34] V. S. Kirsanov, “Unichtozhennye knigi: ekho stalinskogo terrora v sovetskoi istorii nauki”, Voprosy istorii estestvoznaniya i tekhniki, 2005, no. 4, 105–124

[35] N. Ya. Vilenkin, “Formuly na fanere”, Priroda, 6 (1991), 95–104 | MR

[36] S. E. Arshon, “Dokazatelstvo suschestvovaniya $n$-znachnykh beskonechnykh asimmetrichnykh posledovatelnostei”, Matem. prosveschenie, ser. 2, 2 (1934), 24–33

[37] S. E. Arshon, “Dokazatelstvo suschestvovaniya $n$-znachnykh beskonechnykh asimmetrichnykh posledovatelnostei”, Matem. sb., 2:4 (1937), 769–779 | Zbl

[38] M. Lothaire, Algebraic combinatorics on words, Encyclopedia Math. Appl., 90, Cambridge Univ. Press, Cambridge, 2002 | MR | Zbl

[39] J. Bernoulli, “Sur une nouvelle espèce de calcul”, Recueil pour les astronomes, 1 (1775), 255–284

[40] E. B. Christoffel, “Observatio arithmetica”, Brioschi Ann. (2), 6:1 (1873), 148–153 | Zbl

[41] A. Markoff, “Sur une question de Jean Bernoulli”, Math. Ann., 19:1 (1881), 27–36 | DOI | MR | Zbl

[42] J.-P. Allouche, J. Shallit, Automatic sequences. Theory, applications, generalizations, Cambridge Univ. Press, Cambridge, 2003 | MR | Zbl

[43] H. Bohr, “Zur Theorie der fastperiodischen Funktionen. I”, Acta Math., 45:1 (1925), 29–127 | DOI | MR | Zbl

[44] A. S. Besicovitch, Almost periodic functions, Cambridge Univ. Press, Cambridge, 1932 | MR | Zbl

[45] K. Jacobs, “Turing-Maschinen und zufallige 0-1-Folgen”, Selecta Math., II, Heidelberger Taschenbucher, 67, Springer, Berlin, 1970, 141–167 ; K. Yakobs, “Mashiny Tyuringa i rekursivnye funktsii”, Populyarnaya seriya “Sovremennaya matematika”, eds. G.-D. Ebbinkhauz, K. Yakobs, F.-K. Man, Mir, M., 1972, 183–215 | MR | Zbl | MR

[46] An. Muchnik, A. Semenov, M. Ushakov, “Almost periodic sequences”, Theoret. Comput. Sci., 304:1–3 (2003), 1–33 | DOI | MR | Zbl

[47] Yu. L. Pritykin, “Finite-automaton transformations of strictly almost-periodic sequences”, Math. Notes, 80:5–6 (2006), 710–714 | DOI | MR | Zbl

[48] M. Lothaire, Combinatorics on words, 2nd edition, Cambridge Math. Lib., Cambridge Univ. Press, Cambridge, 1997 | MR | Zbl

[49] Yu. L. Pritykin, “Konechno-avtomatnye preobrazovaniya pochti periodicheskikh posledovatelnostei i algoritmicheskaya nerazreshimost”, Trudy XXVIII konferentsii molodykh uchenykh, Izd-vo MGU, M., 2006, 177–181

[50] J. Cassaigne, “Recurrence in infinite words”, STACS (Dresden, 2001), Lecture Notes in Comput. Sci., 2010, Springer, Berlin, 2001, 1–11 | DOI | MR | Zbl

[51] N. P. Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Math., 1794, Springer-Verlag, Berlin, 2002 | DOI | MR | Zbl

[52] M. Keane, “Generalized Morse sequences”, Z. Wahrscheinlichkeitstheor. verw. Geb., 10:4 (1968), 335–353 | DOI | MR | Zbl

[53] S. Kakutani, “Ergodic theory of shift transformations”, Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. Vol. II: Contributions to Probability Theory, Part {\rm2} (Berkeley, CA, 1965/66), Univ. California Press, Berkeley, CA, 1967, 405–414 | MR | Zbl

[54] A. Hoit, “Arithmetic on blocks”, Integers, 4 (2004), A1 | MR | Zbl

[55] A. Cobham, “Uniform tag sequences”, Math. Systems Theory, 6:1–2 (1972), 164–192 | DOI | MR | Zbl

[56] Yu. Pritykin, M. Raskin, Almost periodicity and finite automata, Electronic Proceedings of WIWAD (satellite to CSR 2007), Ekaterinburg, 2007 | Zbl

[57] M. Raskin, O proizvedenii pochti periodicheskikh posledovatelnostei, ne opublikovano

[58] P. Salimov, “On uniform recurrence of a direct product”, AutoMathA 2009 (Liège, Belgium, 2009)

[59] R. McNaughton, “Testing and generating infinite sequences by a finite automaton”, Information and Control, 9:5 (1966), 521–530 | DOI | MR | Zbl

[60] J. R. Büchi, “On a decision method in restricted second-order arithmetic”, Logic, Methodology and Philosophy of Science (1960), Stanford Univ. Press, Stanford, CA, 1962, 1–11 | MR | Zbl

[61] D. Siefkes, “Undecidable extensions of monadic second order successor arithmetic”, Z. Math. Logik und Grundlagen der Math., 17:5 (1971), 383–394 | MR

[62] O. Carton, W. Thomas, “The monadic theory of morphic infinite words and generalizations”, Inform. and Comput., 176:1 (2002), 51–65 | DOI | MR | Zbl

[63] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York–Toronto–London, 1967 | MR | MR | Zbl | Zbl

[64] Yu. L. Pritykin, “O neregulyarnosti nekotorykh mnozhestv beskonechnykh slov”, Trudy 30-i konferentsii molodykh uchenykh ITiS 2007, IPPI RAN, Moskva, 2007, 134–137

[65] An. A. Muchnik, “The definable criterion for definability in Presburger arithmetic and its applications”, Theoret. Comput. Sci., 290:3 (2003), 1433–1444 | DOI | MR | Zbl

[66] A. Adler, Sh.-Y. R. Li, “Magic cubes and Prouhet sequences”, Amer. Math. Monthly, 84:8 (1977), 618–627 | DOI | MR | Zbl

[67] J.-P. Allouche, J. Shallit, “Sums of digits, overlaps, and palindromes”, Discrete Math. Theor. Comput. Sci., 4:1 (2000), 1–10 | MR | Zbl

[68] P. Séébold, “On some generalizations of the Thue–Morse morphism”, Theoret. Comput. Sci., 292:1 (2003), 283–298 | DOI | MR | Zbl

[69] Yu. Pritykin, “On almost periodicity criteria for morphic sequences in some particular cases”, Developments in language theory, Lecture Notes in Comput. Sci., 4588, Springer, Berlin, 2007, 361–370 | DOI | MR | Zbl

[70] F. Nicolas, Yu. Pritykin, “On uniformly recurrent morphic sequences”, Internat. J. Found. Comput. Sci., 20:5 (2009), 919–940 | DOI | MR

[71] F. M. Dekking, “Iteration of maps by an automaton”, Discrete Math., 126:1–3 (1994), 81–86 | DOI | MR | Zbl

[72] J.-P. Allouche, “Sur la complexité des suites infinies”, Journées Montoises (Mons, 1992), Bull. Belg. Math. Soc. Simon Stevin, 1, no. 2, 1994, 133–143 | MR | Zbl

[73] S. Ferenczi, “Complexity of sequences and dynamical systems”, Combinatorics and number theory (Tiruchirappalli, 1996), Discrete Math., 206:1–3 (1999), 145–154 | DOI | MR | Zbl

[74] J. Cassaigne, “Sequences with grouped factors”, Developments in language theory III (DLT'97), Aristotle University of Thessaloniki, 1998, 211–222

[75] A. L. Chernyatiev, “Balanced words and dynamical systems”, J. Math. Sci. (N. Y.), 156:2 (2009), 351–358 | DOI | MR

[76] J.-J. Pansiot, “Complexité des facteurs des mots infinis engendrés par morphismes itérés”, Automata, languages and programming (Antwerp, 1984), Lecture Notes in Comput. Sci., 172, Springer, Berlin, 1984, 380–389 | DOI | MR | Zbl

[77] J.-J. Pansiot, “Subword complexities and iteration”, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 26 (1985), 55–62

[78] R. Devyatov, “On subword complexity of morphic sequences”, Computer science – theory and applications, Lecture Notes in Comput. Sci., 5010, Springer, Berlin, 2008, 146–157 | DOI | MR

[79] R. Devyatov, “More on subword complexity of morphic sequences” (to appear)

[80] S. V. Avgustinovich, D. G. Fon-Der-Flaass, A. E. Frid, “Arithmetical complexity of infinite words”, Words, languages combinatorics, III (Kyoto, 2000), eds. M. Ito, T. Imaoka, World Sci. Publ., River Edge, NJ, 2003, 51–62 | MR

[81] A. E. Frid, “On possible growths of arithmetical complexity”, Theor. Inform. Appl., 40:3 (2006), 443–458 | DOI | MR | Zbl

[82] S. V. Avgustinovich, J. Cassaigne, A. E. Frid, “Sequences of low arithmetical complexity”, Theor. Inform. Appl., 40:4 (2006), 569–582 | DOI | MR | Zbl

[83] M. Waldschmidt, “Words and transcendence”, Analytic number theory, Cambridge Univ. Press, Cambridge, 2009, 449–470 | MR | Zbl

[84] É. Borel, “Les probabilités dénombrables et leurs applications arithmétiques”, Rend. Circ. Mat. Palermo (2), 27:1 (1909), 247–271 | DOI | MR | Zbl

[85] É. Borel, “Sur les chiffres décimaux de $\sqrt{2}$ et divers problèmes de probabilités en chaînes”, C. R. Acad. Sci. Paris, 230 (1950), 591–593 | MR | Zbl

[86] S. Ferenczi, C. Mauduit, “Transcendence of numbers with a low complexity expansion”, J. Number Theory, 67:2 (1997), 146–161 | DOI | MR | Zbl

[87] B. Adamczewski, Y. Bugeaud, “On the complexity of algebraic numbers. I. Expansions in integer bases”, Ann. of Math. (2), 165:2 (2007), 547–565 | DOI | MR | Zbl

[88] A. Cobham, “On the Hartmanis–Stearns problem for a class of tag machines”, Proceedings of the 9th Annual Symposium on Switching and Automata Theory (SWAT'68), IEEE Computer Society, 1968, 51–60

[89] J. Albert, Propriétés combinatoires et arithmétiques de certaines suites automatiques et substitutives, Thèse de Doctorat, Université Paris XI, Orsay, 2006

[90] Y. Bugeaud, J.-H. Evertse, “On two notions of complexity of algebraic numbers”, Acta Arith., 133:3 (2008), 221–250 | DOI | MR | Zbl

[91] M. Li, P. Vitányi, An introduction to Kolmogorov complexity and its applications, 2nd edition, Grad. Texts Comput. Sci., Springer-Verlag, New York, 1997 | MR | Zbl

[92] V. A. Uspenskii, N. K. Vereschagin, A. Shen, Kolmogorovskaya slozhnost, Neopubl. kniga

[93] Yu. L. Pritykin, “Kolmogorovskaya slozhnost”, Matem. prosveschenie, ser. 3, 13 (2009), 127–133

[94] A. Yu. Rumyantsev, “Kolmogorov complexity, Lovász local lemma and critical exponents”, Proceedings of the 2nd International Symposium on Computer Science in Russia (CSR 2007, Ekaterinburg), Lecture Notes in Comput. Sci., 4649, Springer, Berlin, 2007, 349–355 | DOI | Zbl

[95] D. Krieger, J. Shallit, “Every real number greater than 1 is a critical exponent”, Theoret. Comput. Sci., 381:1–3 (2007), 177–182 | DOI | MR | Zbl

[96] Yu. Pritykin, “Information in infinite words”, Proceedings of the 6th International Conference on Words (WORDS 2007, CIRM, Marseille, France), 2007, 254–261

[97] B. Durand, L. Levin, A. Shen, “Complex tilings”, Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM, New York, 2001, 732–739 | MR

[98] M.-P. Béal, D. Perrin, “Symbolic dynamics and finite automata”, Handbook of formal languages, vol. 2, eds. G. Rozenberg, A. Salomaa, Springer, Berlin, 1997, 463–505 | MR

[99] Yu. Pritykin, J. Ulyashkina, “Aperiodicity measure for infinite sequences”, Proceedings of CSR 2009 (Novosibirsk, 2009), Lecture Notes in Comput. Sci., 5675, Springer, Berlin, 2009, 274–285 | DOI | Zbl

[100] B. Durand, A. Romashchenko, A. Shen, “Fixed point and aperiodic tilings”, Proceedings of DLT 2008, Lecture Notes in Comput. Sci., 5257, Springer, Berlin, 2008, 276–288 ; arXiv: 0802.2432 | DOI | Zbl

[101] E. Grant, J. Shallit, T. Stoll, “Bounds for the discrete correlation of infinite sequences on $k$ symbols and generalized Rudin–Shapiro sequences”, Acta Arith. (to appear); , 2008 arXiv: 0812.3186

[102] J. Cassaigne, N. Chekhova, “Fonctions de récurrence des suites d'Arnoux–Rauzy et réponse à une question de Morse et Hedlund”, Ann. Inst. Fourier (Grenoble), 56:7 (2006), 2249–2270 | MR | Zbl

[103] G. Rauzy, “Suites à termes dans un alphabet fini”, Seminar on number theory, Exp. No 25 (Talence, 1982/1983), Univ. Bordeaux I, Talence, 1983 | MR | Zbl

[104] A. Apostolico, A. Ehrenfeucht, “Efficient detection of quasiperiodicities in strings”, Theoret. Comput. Sci., 119:2 (1993), 247–265 | DOI | MR | Zbl

[105] S. Marcus, “Quasiperiodic infinite words”, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 82 (2004), 170–174 | MR | Zbl

[106] F. Levé, G. Richomme, “Quasiperiodic infinite words: some anwers”, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 84 (2004), 128–138 | MR | Zbl

[107] T. Monteil, S. Marcus, Quasiperiodic infinite words: multi-scale case and dynamical properties, , 2006 arXiv: math/0603354 | MR

[108] F. Levé, G. Richomme, “Quasiperiodic Sturmian words and morphisms”, Theoret. Comput. Sci., 372:1 (2007), 15–25 ; , 2006 arXiv: cs/0601027 | DOI | MR | Zbl

[109] J. Karhumäki, Y. Lifshits, W. Rytter, “Tiling periodicity”, Proceedings of CPM 2007, Lecture Notes in Comput. Sci., 4580, Springer, Berlin, 2007, 295–306 | DOI | Zbl

[110] D. J. Newman, “Tesselation of integers”, J. Number Theory, 9:1 (1977), 107–111 | DOI | MR | Zbl

[111] O. Toeplitz, “Ein Beispiel zur Theorie der fastperiodischen Funktionen”, Math. Ann., 98:1 (1928), 281–295 | DOI | MR | Zbl

[112] K. Jacobs, M. Keane, “0-1-sequences of Toeplitz type”, Z. Wahrscheinlichkeitstheor. verw. Geb., 13:2 (1969), 123–131 | DOI | MR | Zbl

[113] J. Cassaigne, J. Karhumäki, “Toeplitz words, generalized periodicity and periodically iterated morphisms”, European J. Combin., 18:5 (1997), 497–510 | DOI | MR | Zbl

[114] K. Culik II, J. Karhumäki, “Iterative devices generating infinite words”, Proceedings of STACS'92, Lecture Notes in Comput. Sci., 577, Springer, Berlin, 1992, 529–543 | DOI

[115] A. Lepistö, “On the power of periodic iteration of morphisms”, Automata, languages and programming (Lund, 1993), Lecture Notes in Comput. Sci., 700, Springer, Berlin, 1993, 496–506 | DOI | MR

[116] W. Kolakoski, “Problem 5304: Self generating runs”, Amer. Math. Monthly, 72:6 (1965), 674 | DOI | MR

[117] W. Kolakoski, N. Ucoluk, “Problems and solutions: Solutions of advanced problems: 5304”, Amer. Math. Monthly, 73:6 (1966), 681–682 | DOI | MR

[118] E. W. Weisstein, Kolakoski sequence, http://mathworld.wolfram.com/KolakoskiSequence.html

[119] A. Scolnicov, PlanetMath: Kolakoski Sequence, http://planetmath.org/encyclopedia/KolakoskiSequence.html | Zbl

[120] C. Kimberling, Integer sequences and arrays, http://faculty.evansville.edu/ck6/integer/

[121] C. Kimberling, Unsolved problems and rewards, http://faculty.evansville.edu/ck6/integer/unsolved.html

[122] N. J. A. Sloane, On-line encyclopedia of integer sequences, {id:A000002}, http://www.research.att.com/ñjas/sequences/A000002

[123] K. Culik II, J. Karhumäki, A. Lepistö, “Alternating iteration of morphisms and the Kolakovski sequence”, Lindermayer systems, eds. G. Rozenberg, A. Salomaa, Springer, Berlin, 1992, 93–106 | MR | Zbl

[124] S. I. Adian, A. L. Semenov, V. A. Uspenskii, “Andrei Al'bertovich Muchnik (obituary)”, Russian Math. Surveys, 62:4 (2007), 775–779 | DOI | MR | Zbl