Finiteness and regularity in semigroups and formal languages
Author(s)
Bibliographic Information
Finiteness and regularity in semigroups and formal languages
（Monographs in theoretical computer science : an EATCS series）
Springer, 1999
- : pbk
Available at / 27 libraries
-
No Libraries matched.
- Remove all filters.
Note
Includes bibliographical references (p. [229]-235) and index
Description and Table of Contents
- Volume
-
ISBN 9783540637714
Description
This is a rigorous and self-contained monograph on a central topic in theoretical computer science: finiteness conditions for semigroups and regularity conditions for formal languages. For the first time in book form, original results from the last ten years are presented, some previously unpublished, using combinatorial and algebraic methods. These are mainly based on combinatorics on words and especially on the theory of "unavoidable regularities" in free monoids. Many finiteness conditions are considered, formulated in terms of such concepts as: permutability, iteration, repetitivity, and chain conditions. These give rise to regularity conditions for formal languages. Non-algebraic regularity conditions are also investigated. A background in mathematics and computer science is required.
- Volume
-
: pbk ISBN 9783642641503
Description
This is a rigorous and self-contained monograph on a central topic in theoretical computer science. For the first time in book form, original results from the last ten years are presented, some previously unpublished, using combinatorial and algebraic methods. These are mainly based on combinatorics on words and especially on the theory of "unavoidable regularities." Researchers will find important new results on semigroups and formal languages, as well as various applications for these methods.
Table of Contents
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.
by "Nielsen BookData"
