Formal Languages, Automaton and Numeration Systems presents readers with a review of research related to formal language theory, combinatorics on words or numeration systems, such as Words, DLT (Developments in Language Theory), ICALP, MFCS (Mathematical Foundation of Computer Science), Mons Theoretical Computer Science Days, Numeration, CANT (Combinatorics, Automata and Number Theory). Combinatorics on words deals with problems that can be stated in a non-commutative monoid, such as subword complexity of finite or infinite words, construction and properties of infinite words, unavoidable regularities or patterns. When considering some numeration systems, any integer can be represented as a finite word over an alphabet of digits. This simple observation leads to the study of the relationship between the arithmetical properties of the integers and the syntactical properties of the corresponding representations. One of the most profound results in this direction is given by the celebrated theorem by Cobham. Surprisingly, a recent extension of this result to complex numbers led to the famous Four Exponentials Conjecture. This is just one example of the fruitful relationship between formal language theory (including the theory of automata) and number theory.

FOREWORD ixINTRODUCTION xiiiCHAPTER 1. WORDS AND SEQUENCES FROM SCRATCH 11.1. Mathematical background and notation 21.1.1. About asymptotics 41.1.2. Algebraic number theory 51.2. Structures, words and languages 111.2.1. Distance and topology 161.2.2. Formal series 241.2.3. Language, factor and frequency 281.2.4. Period and factor complexity 331.3. Examples of infinite words 361.3.1. About cellular automata 431.3.2. Links with symbolic dynamical systems 461.3.3. Shift and orbit closure 591.3.4. First encounter with beta-expansions 621.3.5. Continued fractions 691.3.6. Direct product, block coding and exercises 701.4. Bibliographic notes and comments 77CHAPTER 2. MORPHIC WORDS 852.1. Formal definitions 892.2. Parikh vectors and matrices associated with a morphism962.2.1. The matrix associated with a morphism 982.2.2. The tribonacci word 992.3. Constant-length morphisms 1072.3.1. Closure properties 1172.3.2. Kernel of a sequence 1192.3.3. Connections with cellular automata 1202.4. Primitive morphisms 1222.4.1. Asymptotic behavior 1272.4.2. Frequencies and occurrences of factors 1272.5. Arbitrary morphisms 1332.5.1. Irreducible matrices 1342.5.2. Cyclic structure of irreducible matrices 1442.5.3. Proof of theorem 2.35 1502.6. Factor complexity and Sturmian words 1532.7. Exercises 1592.8. Bibliographic notes and comments 163CHAPTER 3. MORE MATERIAL ON INFINITE WORDS 1733.1. Getting rid of erasing morphisms 1743.2. Recurrence 1853.3. More examples of infinite words 1913.4. Factor Graphs and special factors 2023.4.1. de Bruijn graphs 2023.4.2. Rauzy graphs 2063.5. From the Thue-Morse word to pattern avoidance 2193.6. Other combinatorial complexity measures 2283.6.1. Abelian complexity 2283.6.2. k-Abelian complexity 2373.6.3. k-Binomial complexity 2453.6.4. Arithmetical complexity 2493.6.5. Pattern complexity 2513.7. Bibliographic notes and comments 252BIBLIOGRAPHY 257INDEX 295SUMMARY OF VOLUME 2 303