ISBN: 3540637710
TITLE: Finiteness and Regularity in Semigroups and Formal Languages
AUTHOR: Luca, Aldo de; Varricchio, Stefano
TOC:

Preface V
1. Combinatorics on Words 1
1.1 Preliminaries 1
1.2 Infinite words 4
1.3 Metric and topology 
1.4 Periodicity and conjugacy 7
1.5 Lyndon words 16
1.6 Factorial languages and subword complexity 21
2. Unavoidable Regularities 31
2.1 Ramsey's theorem 32
2.2 Van der Waerden's theorem 36
2.3 Uniformly recurrent words 41
2.4 Shirshov's theorem 46
2.5 Bounded languages 50
2.6 Power-free words 54
2.7 Bi-ideal sequences 59
2.7.1 Canonical factorizations 61
2.7.2 Bi-ideal sequences and recurrence 66
2.7.3 Some extensions of the Shirshov theorem 72
3. Finiteness Conditions for Semigroups 77
3.1 Preliminaries on semigroups 77
3.2 Finitely generated semigroups 83
3.3 The Burnside problem 88
3.4 Permutation property 90
3.4.1 The weak permutability 96
3.4.2 The omega-permutability 102
3.5 Partial commutations 103
3.6 Chain conditions 105
3.6.1 The J-depth decomposition theorem 109
3.6.2 Minimal conditions on principal right ideals 114
3.6.3 Minimal conditions on principal bi-ideals 116
3.6.4 The McNaughton-Zalcstein and Straubing theorems 123
3.7 Iteration property 127
3.7.1 omega-iteration property 133
3.7.2 Strong periodicity 136
3.8 Permutation and itertion property 137
3.9 Repetitivity 141
3.9.1 Repetitive morphisms and semigroups 141
3.9.2 Strongly repetitive morphisms 142
3.9.3 Uniformly repetitive semigroups 148
4. Finitely Recognizable Semigroups 153
4.1 The Myhill-Nerode theorem 154
4.2 Finitely recognizable semigroups 158
4.3 The factor semigroup 161
4.4 Rewriting systems 164
4.5 The word problem 166
4.6 On a conjecture of Brzozowski 170
4.6.1 Problems and results 171
4.7 On a conjecture of Brown 175
5. Regularity Conditions 179
5.1 Uniform conditions 180
5.2 Pumping properties 183
5.3 Permutative property 191
6. Well Quasi-orders and Regularity 195
6.1 Well quasi-orders 196
6.2 Higman's theorem 199
6.3 The generalized Myhill theorem 203
6.4 Quasi-orders and rewriting systems 206
6.5 A regularity condition for permutable languages 208
6.6 Almost-commutative languages 212
6.7 Copying systems 222
References 229
Index 237
END
