Finiteness and regularity in semigroups and formal languages. (English) Zbl 0935.68056

EATCS Monographs on Theoretical Computer Science. Berlin: Springer. x, 240 p. (1999).
The aim of this book is to present recent research works on the combinatorial aspects of the theory of semigroups.
Chapter 1 is concerned with some classical and basic notations of combinatorics on words (periodicity, conjugation, Lyndon words, subword complexity). Chapter 2 deals with properties satisfied by sufficiently long words over a finite alphabet. Chapter 3 studies finiteness conditions for semigroups especially finitely generated. Particular relationship between finiteness conditions for semigroups and the theory of automata and regular languages are investigated. The study of regularity conditions for periodic languages has been called the Burnside problem for languages.
Chapter 4 is devoted important families of semigroups, namely recognizable subsets of semigroups and rational subsets of semigroups. Especially conditions for finitely generated semigroups are investigated. Chapter 5 considers conditions for regularity formulated not syntactic. Some versions of conditions which cannot be expressed as properties of the syntactic monoid of the language are analyzed. Chapter 6 gives some regularity conditions that can be expressed in terms of well quasi-orders. Under which conditions for semi-Thue systems, unitary rewriting systems and copying systems.
In the following two further classes of rewriting systems and regularity conditions of quasi-periodic languages are considered.
Reviewer: S.Gerber (Leipzig)


68Q45 Formal languages and automata
68R15 Combinatorics on words
68-02 Research exposition (monographs, survey articles) pertaining to computer science
68Q42 Grammars and rewriting systems