Michel RIGO, Full professor, University of Liège, Department of Math., Belgium.

• 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 β-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 morphism 962.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

"This nice book is devoted to a quickly growing field, at the frontier between theoretical computer science, combinatorics, and number theory." (Zentralblatt MATH, 2016)