Ebook: Finiteness and Regularity in Semigroups and Formal Languages

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.

---

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.
Content:
Front Matter....Pages I-X
Combinatorics on Words....Pages 1-30
Unavoidable Regularities....Pages 31-76
Finiteness Conditions for Semigroups....Pages 77-152
Finitely Recognizable Semigroups....Pages 153-177
Regularity Conditions ....Pages 179-194
Well Quasi-orders and Regularity ....Pages 195-227
Back Matter....Pages 229-242

---

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.
Content:
Front Matter....Pages I-X
Combinatorics on Words....Pages 1-30
Unavoidable Regularities....Pages 31-76
Finiteness Conditions for Semigroups....Pages 77-152
Finitely Recognizable Semigroups....Pages 153-177
Regularity Conditions ....Pages 179-194
Well Quasi-orders and Regularity ....Pages 195-227
Back Matter....Pages 229-242
....