Combinatorics on words, facrordynamics and normal forms

I. A. Reshetnikov

Čebyševskij sbornik, Tome 22 (2021) no. 2, pp. 202-235.

Résumé

Methods of symbolic dynamics play an essential role in the study of combinatorial properties of words, problems in number theory and the theory of dynamical systems. The paper is devoted to the problems of combinatorics on words, its applications in algebra and dynamical systems. Section 2.1 considers the one-dimensional case using the key example of Sturm's words. The proof of the criterion for substitutionality of Sturm palindromes using the Rauzy induction is given, the case of one-dimensional facordynamics is considered. Section 2.2 discusses the shift of the torus and the Rauzy fractal that generates the word Tribonacci. The relationship between the periodicity of Rauzy's schemes and the substitutionality of the word generated by this system is discussed. The implementation of the word Tribonacci through the rearrangement of line segments is given. An approach to the Pisot hypothesis is outlined. Section 2.3 talks about unipotent torus transformations and billiards in polygons. Chapter 3 talks about normal forms and the growth of groups and algebras. Chapter 4 is devoted to Rosie graphs, Gröbner bases and co-growth, and algebraic applications. Section 4.1 discusses the results in the combinatorics of multilinear words developed by V. N. Latyshev and the problems he posed. Section 4.2 talks about finitely defined objects and the problems of controlling the relationships that define them. Section 4.3 describes some monomial algebras in terms of uniformly recurrent words. Chapter 5 deals with the problem of height and normal forms.

Détail

Keywords: combinatorics of words, Sturm words, factordynamics, Rauzy fractals, interval exchangings, symbolic dynamics, Shirshov's height theorem, almost periodic sequence, height theorem, non-periodic mosaics, DOLL-systems, Vershik-Livshitz type theorems, Rauzy schemes, definability in structures, the Gröbner-Shirshov basi, $n$-splitability, Dilworth's theorems, Burnside type problems.

Bibliographie

[1] S.I. Adyan, Problema Bernsaida i tozhdestva v gruppakh, Nauka, M., 1975

[2] Adyan S. I., Razborov A. A., “Periodicheskie gruppy i algebry Li”, Uspekhi mat. nauk, 42:2 (1987), 2–68 | MR | Zbl

[3] S. V. Aleshin, “Svobodnaya gruppa konechnykh avtomatov”, Vestn. Mosk. un-ta. Ser. 1. Matem., mekh., 1983, no. 4, 12–14 | MR | Zbl

[4] S.V. Aleshin, “O superpozitsiyakh avtomatnykh otobrazhenii”, Kibernetika, 1, Kiev, 1975, 29–34 | Zbl

[5] S.V. Aleshin, “Konechnye avtomaty i problema Bernsaida o periodicheskikh gruppakh”, Mat. Zametki, 11 (1972), 319–328 | Zbl

[6] V. I. Arnold, “Malye znamenateli i problemy ustoichivosti dvizheniya v klassicheskoi i nebesnoi mekhanike”, Uspekhi Mat. Nauk, 18:6(114) (1963), 91–192 | DOI | MR | Zbl

[7] Yu.A. Bakhturin, Tozhdestva v algebrakh Li, Nauka, M., 1985, 448 pp. | MR

[8] Babenko I. K., “Problemy rosta i ratsionalnosti v algebre i topologii”, Uspekhi mat. nauk, 41:2 (1986), 96–142 | MR

[9] A.Ya.Belov, “Klassifikatsiya slabo neterovykh monomialnykh algeb”, Fund. i prikl. mat., 1:4 (1995), 1085–1089 | MR | Zbl

[10] A.Ya.Belov, V.V.Borisenko, V.N.Latyshev, “Monomialnye algebry”, Itogi nauki i tekhniki. Sovr. Mat. Pril. Tem. Obzory, 26, M., 2002, 35–214

[11] Belov A. Ya., “O ratsionalnosti ryadov Gilberta otnositelno svobodnykh algebr”, Uspekhi mat. nauk, 52:2 (1997), 153–154 | DOI | MR | Zbl

[12] Belov A. Ya., “O bazise Shirshova otnositelno svobodnykh algebr slozhnosti $n$”, Mat. sb., 135:31 (1988), 373–384 | Zbl

[13] Belov A. Ya., “Teorema o vysote dlya iordanovykh i lievykh PI-algebr”, Sib. shkola po mnogoobr. algebraicheskikh sistem, Tezisy (Barnaul, 1988), 12–13

[14] A. Belov, G. Kondakov, “Obratnye zadachi simvolicheskoi dinamiki”, Fundamentalnaya i prikladnaya matematika, 1 (1995) | MR

[15] Golod E. S., Shafarevich I. R., “O bashne polei klassov”, Izv. AN SSSR. Ser. mat., 28:2 (1964), 261–272 | Zbl

[16] Golod E. S., “O nilalgebrakh i finitno-approksimiruemykh $p$-gruppakh”, Izv. AN SSSR. Ser. mat., 28:2 (1964), 273–276

[17] Grigorchuk R. I., “K probleme Milnora o gruppovom roste”, Dokl. AN SSSR, 271:1 (1983), 53–54

[18] Grigorchuk R. I., “Stepeni rosta konechno porozhdennykh grupp i teoriya invariantnykh srednikh”, Izv. AN SSSR. Ser. mat., 48:5 (1984), 939–985 | MR

[19] Grigorchuk R. I., “O ryadakh Gilberta-Puankare graduirovannykh algebr, assotsiirovannykh s gruppami”, Mat. sb., 180:2 (1989), 207–225

[20] Dnestrovskaya tetrad: operativno-informats. sbornik, 4-e izd., izd. in-ta matem. SO AN SSSR, Novosibirsk, 1993, 73 pp.

[21] A. Kanel-Belov, I. Melnikov, I Mitrofanov, “On cogrowth function of algebras and its logarithmical gap”, Comptes Rendus - Série Mathématique, 2021 (to appear) | MR

[22] M. I. Kharitonov, “Otsenki struktury kusochnoi periodichnosti v teoreme Shirshova o vysote”, Vestnik Moskovskogo universiteta, Seriya 1, Matematika. Mekhanika, 2013, no. 1, 10–16, arXiv: 1108.6295 | Zbl

[23] M. I. Kharitonov, “Dvustoronnie otsenki suschestvennoi vysoty v teoreme Shirshova o vysote”, Vestnik Moskovskogo universiteta, Seriya 1, Matematika. Mekhanika, 2012, no. 2, 24–28

[24] M. I. Kharitonov, Otsenki, svyazannye s teoremoi Shirshova o vysote, dissertatsiya, 2015

[25] Petr Lavrov, Number of restrictions required for periodic word in the finite alphabet, arXiv: 1209.0220

[26] Bogdanov Ilya I., Chelnokov Grigory R., The maximal length of the period of a periodic word defined by restrictions, arXiv: 1305.0460

[27] Mikhail Kharitonov, Estimates on the number of partially ordered sets, arXiv: 1307.1886

[28] Kargapolov M.I., Merzlyakov Yu.I., Osnovy teorii grupp, 3e izd., Nauka, 1982, 288 pp. | MR

[29] I. A. Ivanov-Pogodaev, “Algebra s konechnym bazisom Grebnera i nerazreshimoi problemoi delitelei nulya”, Fundament. i prikl. matem., 12:8 (2006), 79–96

[30] A. B. Katok, A. M. Stepin, “Approksimatsii v ergodicheskoi teorii”, Uspekhi Mat.Nauk, 22:5(137) (1967), 81–106 | MR | Zbl

[31] A.T. Kolotov, “Aperiodicheskie posledovatelnosti i funktsii rosta v algebrakh”, Algebra i logika, 20 (1981), 138–154 ; 250 | MR

[32] A.T. Kolotov, “Algebry i polugruppy s periodicheskoi funktsiei rosta”, Algebra i logika, 19 (1980), 659–668 ; 745 | MR

[33] A. G. Kolotov, “O verkhnei otsenke vysoty konechno-porozhdennoi algebry s tozhdestvennymi sootnosheniyami”, Sib. mat. zh., 23:1 (1982), 187–189 | MR | Zbl

[34] Kostrikin A. I., Vokrug Bernsaida, Nauka, M., 1986, 232 pp. | MR

[35] Kurosh A. G., “Problemy teorii kolets, svyazannye s problemoi Bernsaida o periodicheskikh gruppakh”, Izv. AN SSSR, ser. mat., 5 (1941), 233–240 | Zbl

[36] V. B. Kudryavtsev, S. V. Aleshin, A. S. Podkolzin, Vvedenie v teoriyu avtomatov, Nauka, M., 1985, 320 pp. | MR

[37] V.N. Latyshev, “K teoreme Regeva o tozhdestvakh tenzoronogo proizvedeniya $PI$-algebr”, Uspekhi matem. nauk, 27:4 (1972), 213–214 | MR | Zbl

[38] R.Lindon, P.Shupp, Kombinatornaya teoriya grupp, Mir, M., 1980

[39] Mikhalev A. A., “Tekhnika kompozitsii A. I. Shirshova v superalgebrakh Li (nekommutativnye bazisy Grebnera)”, Tr. seminara im. I. G. Petrovskogo, 18, 1994

[40] Mischenko S. P., “Variant teoremy o vysote dlya algebr Li”, Mat. zametki, 47:4 (1990), 83–89

[41] Ivan Mitrofanov, On uniform recurrence of HD0l systems, 20 pp., arXiv: 1111.1999

[42] Ivan Mitrofanov, A proof for the decidability of HD0L ultimate periodicity, 33 pp., arXiv: 1110.4780

[43] Mitrofanov I. V., Algoritmicheskie problemy, svyazannye s morficheskimi posledovatelnostyami, dissertatsiya, 2017

[44] Olshanskii A. Yu., Geometriya opredelyayuschikh sootnoshenii v gruppakh, Sovrem. algebra, Nauka, M., 1989, 447 pp. | MR

[45] V.I.Oseledets, “O spektre ergodicheskikh avtomorfizmov”, DAN SSSR, 168 (1966), 1009–1011 | Zbl

[46] Pchelintsev S. V., “Teorema o vysote dlya alternativnykh algebr”, Mat. sb., 124:4 (1984), 557–567 | MR | Zbl

[47] Salomaa A., Zhemchuzhiny formalnykh yazykov, Mir, M., 1986, 159 pp.

[48] Ya.G. Sinai, Vvedenie v ergodicheskuyu teoriyu, FAZIS, M., 1996, 144 pp.

[49] Trofimov V. I., “Ob odnom priznake eksponentsialnogo rosta graduirovannykh algebr”, Issledovanie algebraicheskikh sistem po svoistvam ikh podsistem (Sverdlovsk, 1980), 152–160 | Zbl

[50] Ufnarovskii V. A., “Teorema o nezavisimosti i ee sledstviya”, Mat. sb., 128:1 (1985), 124–132 | MR | Zbl

[51] Ufnarovskii V.A., “Kombinat. i asimpt. metody v algebre”, Itogi nauki i tekh. Seryu Sovr. Probl. Mat. Fund. napravl., 57, VINITI, M., 1990, 5–177 | MR

[52] Chekanu G. P., “O lokalnoi konechnosti algebr”, Mat. issled. (Kishinev), 1988, no. 105, 153–171 | MR | Zbl

[53] Chekanu G. P., “K teoreme Shirshova o vysote”, XIX Vses. algebr. konf., Tezisy soobsch. (Lvov, 1987), v. I, 306

[54] G. R. Chelnokov, “O chisle zapretov, zadayuschikh periodicheskuyu posledovatelnost”, Modelirovanie i analiz informatsionnykh sistem, 13:3 (2007), 66–70

[55] Shirshov A. I., “O nekotorykh neassotsiativnykh nil-koltsakh i algebraicheskikh algebrakh”, Mat. sb., 41:3 (1957), 381–394 | Zbl

[56] Shirshov A. I., “O koltsakh s tozhdestvennymi sootnosheniyami”, Mat. sb., 43:2 (1957), 277–283 | Zbl

[57] Shirshov A. I., “O svobodnykh koltsakh Li”, Mat. sb., 45:2 (1958), 113–122 | Zbl

[58] Shirshov A. I., “O bazakh svobodnoi algebry Li”, Algebra i logika, 1:1 (1962), 14–19 | MR | Zbl

[59] A.Aberkane, “Words whose complexity satisfies $\lim p(n)/n = 1$”, Theor. Comp. Sci., 307 (2003), 31–46 | DOI | MR | Zbl

[60] P.Ambroz, L. Hákov, E. Pelantová, “Properties of 3iet preserving morphisms and their matrices”, Proceedings WORDS 2007, eds. P. Arnoux, N. Bedaride, J. Cassaigne, 2007, 18–24

[61] P. Arnoux, “Un exemple de semi-conjugaison entre un échange d'intervalles et une translation sur le tore”, Bull. Soc. Math. France, 116 (1988), 489–500 | DOI | MR | Zbl

[62] P. Arnoux and G. Rauzy, “Representation geometrique des suites the complexite $2n + 1$”, Bull. Soc. Math. France, 119 (1991), 199–215 | DOI | MR | Zbl

[63] Arnoux Pierre, Mauduit Christian, Shiokawa Iekata, Tamura Jun-ichi, “Complexity of sequences defined by billiard in the cube”, Bull. Soc. Math. France, 122:1 (1994), 1–12 | DOI | MR | Zbl

[64] P.Balázi, Infnite Words Coding Three-Interval Exchange, diploma work CTU, 2003 | Zbl

[65] P.Balázi, “Substitution properties of ternary words coding 3-interval exchange”, Proceedings WORDS 2003, eds. T. Harju and J. Karhumdaki, 2003, 119–124 | MR

[66] P. Balázi, Z. Masáková, E. Pelantová, “Characterization of substitution invariant 3iet words”, Integers, 2007 (to appear) , arXiv: 0709.2638 | MR | Zbl

[67] A.Belov, T. Gateva-Ivanova, “Radicals of monomial algebras”, Proceedings of Taiwan-Moscow Algebra Workshop, 159–169 | MR | Zbl

[68] A. Belov, “Some estimations for nilpotence of nil-algebras over a field of an arbitrary characteristic and height theorem”, Communications in algebra, 20:10 (1992), 2919–2922 | DOI | MR | Zbl

[69] Belov A., Michailov R., “Free subalgebras of Lie algebras close to nilpotent”, Groups, Geometry, and Dynamics, 2010, no. 1, 15–29 | DOI | MR | Zbl

[70] Belov A., Kontsevich M.L., “Jacobian and Dixmier Conjectures are stably equivalent”, Moscow Mathematical Journal, 7:2, A special volume dedicated to the 60-th anniversary of A.G.Khovanskii (2007), 209–218 | DOI | MR | Zbl

[71] A. Ya. Belov, “Lineinye rekurrentnye uravneniya na dereve”, Matem. zametki, 78:5 (2005), 643–651 | DOI | MR | Zbl

[72] Kanel–Belov A., M. Kharitonov, “Subexponential estimates in the height theorem and estimates on numbers of periodic parts of small periods”, Fundam. Prikl. Mat. (Fundamental and Applied Mathematics), 17:5 (2011/2012), 21–54 | MR

[73] Kanel–Belov A., Rowen Louis H., Vishne Uzi, “Full exposition of Specht's problem”, Serdica Math. J., 38 (2012), 313–370 | MR | Zbl

[74] A. Ya. Belov, M. I. Kharitonov, “Subeksponentsialnaya otsenka v teoreme Shirshova o vysote”, Matem. Sbornik, 203:4 (2012), 81–102 | DOI | MR | Zbl

[75] Kanel–Belov A., Eli Aljadeff, “Representability and Specht problem for $G$-graded algebras”, Adv. in Mat., 225:5 (2010), 2391–2428 | DOI | MR | Zbl

[76] Kanel–Belov A., Rowen Louis H., Vishne Uzi, “Structure of Zariski-closed algebras”, Trans. Amer. Math.Soc., 362:9, 4695–4734 | DOI | MR | Zbl

[77] V. N. Latyshev, “Kombinatornye porozhdayuschie polilineinykh polinomialnykh tozhdestv”, Fundament. i prikl. matem., 12:2 (2006), 101–110 | MR

[78] Durand Fabien, Decidability of uniform recurrence of morphic sequences, arXiv: 1204.5393

[79] Durand Fabien, Decidability of the HD0L ultimate periodicity problem, arXiv: 1111.3268

[80] Fabien Durand, Samuel Petite, Unimodular pisot substitutions and domain exchanges, arXiv: 1408.2110 [math.DS]

[81] A.Belov, I.Mitrofanov, Periodichnost skhem Rozi i podstanovochnye sistemy, arXiv: 1107.0185

[82] A.Ya.Belov, G.V.Kondakov, I.Mitrofanov, “Inverse problems of symbolic dynamics”, Banach Center Publ., 94, 2011, 43–60 | DOI | MR | Zbl

[83] Belov A. J., Ivanov I.A., “Construction of semigroups with some exotic properties”, Acta Appl. Math., 85:1-3 (2005), 49–56 | DOI | MR | Zbl

[84] Berele Allan, “Applications of Belov's theorem to the cocharacter sequence of p.i. algebras”, J. Algebra, 298:1 (2006), 208–214 | DOI | MR | Zbl

[85] Kanel–Belov A., Rowen Louis H., Vishne Uzi, “Full quivers of representations of algebras”, Trans. Amer. Math. Soc., 364 (2012), 5525–5569 | DOI | MR | Zbl

[86] Kanel–Belov A., Eli Aljadeff, “Hilbert series of $PI$-relative free $g$-graded algebras are rational functions”, Bull. London Math. Soc., 44:3 (2012), 520–532 | DOI | MR | Zbl

[87] Kanel–Belov A., Malev S., Rowen Louis H., “The images of non-commutative polynomials evaluated on $2\times 2$ matrices”, Proc. Amer. Math. Soc., 140 (2012), 465–478, arXiv: 1005.0191v2 | DOI | MR | Zbl

[88] Kanel–Belov A., Rowen Louis H., Vishne Uzi, “Application of full quivers of representations of algebras, to polynomial identities”, Comm. in Algebra, 39 (2011), 4536–4551 | DOI | MR | Zbl

[89] Kanel–Belov A., Rowen Louis H., Vishne Uzi, “Normal bases of $PI$-algebras”, Adv. in Appl. Math., 37:3 (2006), 378–389 | DOI | MR | Zbl

[90] Kanel–Belov A., Rowen Louis H., “Perspectives on Shirshov's Height Theorem”, Selected papers of A.I.Shirshov, Birkhüser Verlag AG, 2009, 3–20 | MR

[91] Kanel–Belov Alexei, Rowen Louis Halle, Combinatorial aspects in polynomial identities, Research Notes in Mathematics, 9, A K Peters, Ltd., Wellesley, MA, 2005, xxii+378 pp. | MR

[92] Doklady Mathematics, 81:3 (2010), 458–461 | DOI | MR | Zbl

[93] Izvestiya: Mathematics, 74:1, 1–126 | DOI | MR | Zbl

[94] A.L. Chernyat'ev, “Balanced Words and Dynamical Systems”, Fundamental and Applied Mathematics, 13:5 (2007), 213–224

[95] A.L. Chernyat'ev, “Words with Minimal Growth Function”, Vestnik Mosk. Gos. Univ., 2008

[96] A.Ya. Belov, A.L. Chernyat'ev, “Describing Sturmian Words over an $n$-letter Alphabet”, Math. Met. Appl. IV, MGSU, 1999, 122–128

[97] Belov A. J., “About Non-Specht varieties”, Fund. i prikl. matem., 5:1 (1999), 47–66 | MR | Zbl

[98] Sbornik: Mathematics, 191:3 (1999), 329–340 | DOI | DOI | MR

[99] A.Ya. Kanel-Belov, A.L. Chernyat'ev, “Describing the set of words generated by interval exchange transformation”, Comm. in Algebra, 38:7 (2010), 2588–2605 | DOI | MR | Zbl

[100] G.M. Bergman, A note on growth functions of algebras and semigroups, Research Note, University of California, Berkeley, 1978

[101] V. Berthé, S. Ferenczi, L. Zamboni, “Interactions between dynamics, arithmetics and combina- torics: the good, the bad, and the ugly”, AMS Contemporary Math., 385 (2005), 333–364 | DOI | MR | Zbl

[102] J. Berstel, P. Séébold, “Sturmian words”, Algebraic Combinatorics on Words, Chap. 2, Encyclopedia of Mathematics and Its Applications, 90, ed. M. Lothaire, Cambridge University Press, Cambridge, 2002 | MR

[103] J.Berstel, “Resent results on Sturmian words”, Developments in language theory II, World Scientific, 1996, 13–24 | MR | Zbl

[104] J.Cassaigne, “Special factors with linear subword complexity”, Developments in language theory II (Magdeburg, 1995), World Sci. Publ., River Edge, NJ, 1996, 25–34 | MR | Zbl

[105] Cassaigne J., Hubert P., Troubetzkoy S., “Complexity and growth for polygonal billiards”, Ann. Inst. Fourier (Grenoble), 52:3 (2002), 835–847 | DOI | MR | Zbl

[106] X. Droubay, G. Pirillo, “Palindromes and sturmian word”, Theroret. Comput. Sci., 223 (1999), 73–85 | DOI | MR | Zbl

[107] X.Droubay, J.Justin, G.Pirillo, “Episturmian words and some construction of de Luca and Rauzy”, Theoret. Comp. Sci., 2001, 539–553 | DOI | MR | Zbl

[108] Drensky V., “Codimensions of $T$-ideals and Hilbert series of relatively free algebras”, J. Algebra, 91:1 (1984), 1–17 | DOI | MR | Zbl

[109] Drensky V., Free algebras and PI-algebras, Springer, 2000, 271 | MR | Zbl

[110] H. Furstenberg, “Poincaré reccurence and number theory”, Bull. Amer. Math. Soc., 5 (1981), 211–234 | DOI | MR | Zbl

[111] R. L. Graham, “Covering the Positive Integers by disjoints sets of the form $\{[n\alpha + \beta]:\ n=1, 2, \ldots\}$”, J. Combin. Theory Ser. A, 15 (1973), 354–358 | DOI | MR | Zbl

[112] P. Hubert, “Well balanced sequences”, Theoret. Comput. Sci., 242 (2000), 91–108 | DOI | MR | Zbl

[113] S. Ferenczi, C. Holton, L. Zamboni, “The structure of three-interval exchange transformations II: a combinatorial description of the trajectories”, J. Anal. Math., 89 (2003), 239–276 | DOI | MR | Zbl

[114] Ferenczi, L. Zamboni, A new induction for symmetric $k$-interval exchange transformations and distances theorem, submitted http://iml.univ-mrs.fr/f̃erenczi/fz1.pdf | MR

[115] Ferenczi, L. Zamboni, Examples of $4$-interval exchange transformations, 2006 http://iml.univ-mrs.fr/f̃erenczi/fz2.pdf | MR

[116] Ferenczi, L. Zamboni, Languages of k-interval exchange transformations, submitted http://iml.univ-mrs.fr/f̃erenczi/fz3.pdf | MR

[117] Giambruno A., Zaicev M., “Exponential Codimentional Growth of PI-algebras: an exact estimate”, Adv.in Math., 142 (1999), 221–243 | DOI | MR | Zbl

[118] Giambruno A., Zaicev M., “Minimal varieties of exponential growth”, Adv.in Math., 142 (1999), 221–243 | DOI | MR | Zbl

[119] Gromov M., “Groups of polynomial growth and extending maps”, Publ. Math. inst. hautes etud. sci., 53 (1981), 53–73 | DOI | MR

[120] Kemer A. R., “Multilinear identities of the algebras over a field of characteristic $p$”, Intern. J. of Algebra and Computations, 5:2 (1995), 189–197 | DOI | MR | Zbl

[121] Krause G., Lenagan T.H., “Growth of algebra and Gelfand-Kirillov dimension”, Research Notes in Math., Pitman, London, 1985 | MR | Zbl

[122] A. de Luca, “Sturmian words: structure, combinatorics and their arithmetics”, Theoret. Comp. Sci., 183 (1997), 45–82 | DOI | MR | Zbl

[123] A. de Luca and S. Varricchio, “Combinatorial properties of uniformly recurrent words and an application to semigroups”, Inter. J. Algebra Comput., 1:2 (1991), 227–246 | DOI | MR

[124] Application of Adic representations in the investigations of metric, spectral and topological properties of dynamical systems, Sanct-Petersburg, 1995, 176 pp.

[125] M. Lothaire, “Combinatorics on Words”, Encyclopedia of Mathematics and its Applications, 17, Addison-Wesley, Reading, MA, 1983 | MR | Zbl

[126] M. Lothaire, Algebraic combinatorics on words, A collective work by Jean Berstel, Dominique Perrin, Patrice Seebold, Julien Cassaigne, Aldo De Luca, Steffano Varricchio, Alain Lascoux, Bernard Leclerc, Jean-Yves Thibon, Veronique Bruyere, Christiane Frougny, Filippo Mignosi, Antonio Restivo, Christophe Reutenauer, Dominique Foata, Guo-Niu Han, Jacques Desarmenien, Volker Diekert, Tero Harju, Juhani Karhumaki and Wojciech Plandowski. With a preface by Berstel and Perrin, Encyclopedia of Mathematics and its Applications, 90, Cambridge University Press, Cambridge, 2002, 504 pp. | MR | Zbl

[127] Mauduit C., “Substitutions, arithmetic and finite automata: an introduction”, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Math., 1794, Springer, Berlin, 2002, 35–52 | DOI | MR

[128] Milnor J., “Problem 5603”, American Mathematical monthy, 75:6 (1968), 675–686

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

[130] G. Rauzy, “Nombres algebriques et substitutions”, Bull. Soc. Math. France, 110 (1982), 147–178 | DOI | MR | Zbl

[131] G. Rauzy, “Mots infnis en arithmetique”, Automata on Infnite Words (Ecole de Printemps d'Informatique Thfeorique, Le Mont Dore, May 1984), Lecture Notes in Computer Science, 192, eds. M. Nivat, D. Perrin, Springer-Verlag, Berlin etc., 1985, 165–171 | MR

[132] G. Rauzy, “Suites á termes dans un alphabet fini”, Sémin. Théorie des Nombres, 1982–1983, no. 25, 25-01–25-16 | MR

[133] G. Rauzy, “Échanges d'intervalles et transformations induites”, Acta Arith., 34 (1979), 315–328 (in French) | DOI | MR | Zbl

[134] G. Rozenberg, A. Salomaa, The Mathematical Theory of L Systems, Academic Press, New York etc, 1980 | MR | Zbl

[135] G. Rote, “Sequences with subword complexity $2n$”, J. Number Theory, 46 (1994), 196–213 | DOI | MR | Zbl

[136] R. Tijdeman, “Decomposition of the integers as a direct sum of two subsets”, Number Theory, Number Theory Seminar (Paris 1992-93), ed. S. David, Cambridge University Press, 1995, 261–276 | MR | Zbl

[137] R.Tijdeman, “Fraenkel's conjecture for six sequences”, Discrete Mathematics, 222:1–3 (2000), 223–234 | DOI | MR | Zbl

[138] L. Vuillon, “Balanced words”, Bull. Belg. Math. Soc. Simon Stevin, 10:5 (2003), 787–805 | DOI | MR

[139] L. Vuillon, “A characterization of Sturmian word by return words”, European Journal of Combinatorics, 22 (2001), 263–275 | DOI | MR | Zbl

[140] Vershik A. M., “The adic realizations of the ergodic actions with the homeomorphisms of the Markov compact and the ordered Bratteli diagrams”, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 223, 1995 ; Teor. Predstav. Din. Sistemy, Kombin. i Algoritm. Metody. I, 338, 120–126; J. Math. Sci. (New York), 87:6 (1997), 4054–4058 | MR | DOI

[141] Vershik A. M., Livshits A. N., “Adic models of ergodic transformations, spectral theory, substitutions, and related topics. Representation theory and dynamical systems”, Adv. Soviet Math., 9, Amer. Math. Soc., Providence, RI, 1992, 185–204 | MR

[142] Russian Math. Surveys, 52:2 (1997), 394–395 | DOI | DOI | MR | Zbl

[143] H. Weyl, “Über der gleichverteilung von zahlen mod 1”, Math. Ann., 77 (1916), 313–352 | DOI | MR