Synopsis
1. Combinatorics on Words.- 1.1 Preliminaries.- 1.2 Infinite words.- 1.3 Metric and topology.- 1.4 Periodicity and conjugacy.- 1.5 Lyndon words.- 1.6 Factorial languages and subword complexity.- 2. Unavoidable Regularities.- 2.1 Ramsey's theorem.- 2.2 Van der Waerden's theorem.- 2.3 Uniformly recurrent words.- 2.4 Shirshov's theorem.- 2.5 Bounded languages.- 2.6 Power-free words.- 2.7 Bi-ideal sequences.- 2.7.1 Canonical factorizations.- 2.7.2 Bi-ideal sequences and recurrence.- 2.7.3 Some extensions of the Shirshov theorem.- 3. Finiteness Conditions for Semigroups.- 3.1 Preliminaries on semigroups.- 3.2 Finitely generated semigroups.- 3.3 The Burnside problem.- 3.4 Permutation property.- 3.4.1 The weak permutability.- 3.4.2 The ?-permutability.- 3.5 Partial commutations.- 3.6 Chain conditions.- 3.6.1 The J-depth decomposition theorem.- 3.6.2 Minimal conditions on principal right ideals.- 3.6.3 Minimal conditions on principal bi-ideals.- 3.6.4 The McNaughton-Zalcstein and Straubing theorems.- 3.7 Iteration property.- 3.7.1 w-iteration property.- 3.7.2 Strong periodicity.- 3.8 Permutation and iteration property.- 3.9 Repetitivity.- 3.9.1 Repetitive morphisms and semigroups.- 3.9.2 Strongly repetitive morphisms.- 3.9.3 Uniformly repetitive semigroups.- 4. Finitely Recognizable Semigroups.- 4.1 The Myhill-Nerode theorem.- 4.2 Finitely recognizable semigroups.- 4.3 The factor semigroup.- 4.4 Rewriting systems.- 4.5 The word problem.- 4.6 On a conjecture of Brzozowski.- 4.6.1 Problems and results.- 4.7 On a conjecture of Brown.- 5. Regularity Conditions.- 5.1 Uniform conditions.- 5.2 Pumping properties.- 5.3 Permutative property.- 6. Well Quasi-orders and Regularity.- 6.1 Well quasi-orders.- 6.2 Higman's theorem.- 6.3 The generalized Myhill theorem.- 6.4 Quasi-orders and rewriting systems.- 6.5 A regularity condition for permutable languages.- 6.6 Almost-commutative languages.- 6.7 Copying systems.- References.
Les informations fournies dans la section « Synopsis » peuvent faire référence à une autre édition de ce titre.
