Detailansicht
Finiteness and Regularity in Semigroups and Formal Languages
Monographs in Theoretical Computer Science. An EATCS Series
ISBN/EAN: 9783642641503
Umbreit-Nr.: 4152205
Sprache:
Englisch
Umfang: x, 240 S.
Format in cm:
Einband:
kartoniertes Buch
Erschienen am 18.09.2011
Auflage: 1/1999
- Zusatztext
- Inhaltsangabe1. 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.
- Kurztext
- Rigorous presentation of latest research results A unique and definitive monograph on a central subject in theoretical computer science with various applicationsA must for all experts in theoretical computer science and combinatorics Self-contained account of new results on semigroups and formal languagesIncludes supplementary material: sn.pub/extras