Preface ........................................................ ix
Notation ....................................................... xi
Part I. Christoffel Words ....................................... 1
Chapter 1. Christoffel Words .................................... 5
1. Geometric definition ......................................... 5
2. Cayley graph definition ...................................... 7
Chapter 2. Christoffel Morphisms ................................ 9
1. Christoffel morphisms ........................................ 9
2. Generators .................................................. 14
Chapter 3. Standard Factorization .............................. 17
1. The standard factorization .................................. 17
2. The Christoffel tree ........................................ 20
Chapter 4. Palindromization .................................... 23
1. Christoffel words and palindromes ........................... 23
2. Palindromic closures ........................................ 24
3. Palindromic characterization ................................ 29
Chapter 5. Primitive Elements in the Free Group ................ 33
1. Positive primitive elements of the free group ............... 33
2. Positive primitive characterization ......................... 34
Chapter 6. Characterizations ................................... 39
1. The Burrows - Wheeler transform ............................. 39
2. Balanced1 Lyndon words ...................................... 41
3. Balanced2 Lyndon words ...................................... 41
4. Circular words .............................................. 42
5. Periodic phenomena .......................................... 44
Chapter 7. Continued Fractions ................................. 47
1. Continued fractions ......................................... 47
2. Continued fractions and Christoffel words ................... 48
3. The Stern-Brocot tree ....................................... 52
Chapter 8. The Theory of Markoff Numbers ....................... 55
1. Minima of binary quadratic forms ............................ 55
2. Markoff numbers ............................................. 56
3. Markoff's condition ......................................... 58
4. Proof of Markoff's theorem .................................. 61
Part II. Repetitions in Words .................................. 65
Chapter 1. The Thue-Morse Word ................................. 69
1. The Thue-Morse word ......................................... 69
2. The Thue-Morse morphism ..................................... 70
3. The Tarry-Escott problem .................................... 71
4. Magic squares ............................................... 74
Chapter 2. Combinatorics of the Thue - Morse Word .............. 77
1. Automatic sequences ......................................... 77
2. Generating series ........................................... 79
3. Overlaps .................................................... 81
4. Complexity .................................................. 82
5. Formal languages ............................................ 85
6. The Tower of Hanoi .......................................... 90
Chapter 3. Square-Free Words ................................... 97
1. One example, three constructions ............................ 97
2. Square-free morphisms and codes ............................ 100
3. A 3-square-free test for square-freeness ................... 102
4. A 2-square-free test for square-freeness ................... 105
Chapter 4. Squares in Words ................................... 107
1. Counting squares ........................................... 107
2. Centered squares ........................................... 111
3. Prefix arrays .............................................. 112
4. Crochemore factorization ................................... 114
5. Suffix trees ............................................... 116
Chapter 5. Repetitions and Patterns ........................... 125
1. Maximal repetitions ........................................ 125
2. Repetition thresholds ...................................... 126
3. Patterns ................................................... 127
4. Zimin patterns ............................................. 131
5. Bi-ideal sequences ......................................... 133
6. Repetitions in Sturmian words .............................. 134
Bibliography .................................................. 135
Index ......................................................... 143
|
