Combinatorics on words

Cover......Page 1
Series: Cambridge Mathematical Library......Page 3
Combinatorics on words......Page 4
Copyright......Page 5
Contents......Page 8
Foreword......Page 12
Preface......Page 14
Preface to this edition......Page 17
1.1 Free Monoids and Words......Page 20
1.2 Submonoids and Morphisms......Page 23
1.3 Conjugacy......Page 26
1.4 Formal Series......Page 30
Problems......Page 32
2.0 Introduction......Page 37
2.1 Preliminaries......Page 38
2.2 The Infinite Word of Thue-Morse......Page 42
2.3 Infinite Square-Free Words......Page 45
2.4 Idempotent Semigroups......Page 50
Notes......Page 54
Problems......Page 56
3.1 Classical Formulations......Page 58
3.2 A Combinatorial Proof of van der Waerden\'s Theorem......Page 60
3.3 Application to the Free Monoid......Page 63
3.4 A Topological Proof of van der Waerden\'s Theorem......Page 64
3.5 Further Results and Problems......Page 67
Notes......Page 71
Problems......Page 72
4.1 Repetitive Mappings......Page 74
4.2 Repetitive Morphisms......Page 77
4.3 Repetitive Semigroups......Page 79
Problems......Page 80
5.0 Introduction......Page 82
5.1 Lyndon Words......Page 83
5.2 Bisections of Free Monoids......Page 87
5.3 Free Lie Algebras......Page 95
5.4 The Theorem of Factorizations......Page 111
Notes......Page 117
Problems......Page 118
6.0 Introduction......Page 124
6.1 The Division Ordering......Page 125
6.2 Comparing the Subwords......Page 128
6.3 Counting the Subwords......Page 140
Problems......Page 153
7.1. Some Combinatorial Results......Page 162
7.2. Algebras with Polynomial Identities......Page 166
7.3. Consequences......Page 168
Notes......Page 169
Problems......Page 170
8.1. Preliminaries......Page 172
8.2. The Critical Factorization Theorem......Page 173
8.3. An Application......Page 178
Notes......Page 180
9.0 Introduction......Page 181
9.1. Preliminaries......Page 182
9.2. A Classical Equation: (x^n, y^m, z^p)......Page 183
9.3. Equations in Three Unknowns......Page 187
9.4. Rank of an Equation......Page 188
9.5 Fundamental Solutions......Page 190
9.6. The Graph Associated with an Equation......Page 194
9.7. Quadratic Equations......Page 196
9.8. Related Theories......Page 197
Problems......Page 199
10.1. Preliminaries......Page 203
10.2. The First Fundamental Transformation......Page 204
10.3. The Flow Monoid......Page 208
10.4. The Circuit Monoid......Page 212
10.5. The First Fundamental Transformation for Arbitrary Words......Page 216
10.6. The Second Fundamental Transformation......Page 219
10.7. The Sparre-Andersen Equivalence Principle......Page 222
Notes......Page 226
Problems......Page 227
11.0. Introduction......Page 232
11.1. Trees and Plane Trees......Page 233
11.2. Trees and Parenthesis Systems......Page 235
11.3. Lukaciewicz Language......Page 238
11.4. Lagrange Inversion Formula......Page 240
Problems......Page 244
Bibliography......Page 247
Index......Page 256