zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Elements of automata theory. Translated from the French by Reuben Thomas. (English) Zbl 1188.68177
Cambridge: Cambridge University Press (ISBN 978-0-521-84425-3/hbk). xxiv, 758 p. £ 90.00; $ 145.00 (2009).

[The French original has been announced (see Zbl 1178.68002).]

The author gives a presentation of the theory of finite automata and shows its close connections with mathematics, especially with algebra.

In Chapter 0, the algebraic structures used in the book are provided.

Chapter I presents the theory of finite automata as a theory of free monoids. After a natural extension of the Kleene theorem, the problems of the transformation of an expression in an automaton and of searching for patterns in text strings are dealt with. Furthermore, a necessary and satisfactory version of the star lemma and a proof that the star height of a rational language can be arbitrarily large are treated.

Chapter II deals with the idea of morphisms (for monoids or automata) and in consequence with the distinction between action and automaton, and between a recognisable set and a rational set of an arbitrary monoid. With the help of the concept of morphism of automata, the author introduces the Schützenberger covering of an automaton and the universal automaton of a language, allowing a new treatment of McNaughton’s lemma on the star height of group languages.

Chapter III considers the weights of calculation (weighted automata). Formal languages become formal series, and actions become matrix representations. Here, series on free monoids with coefficients in continuous semirings and the star height of group languages are treated.

Chapter IV deals with relations realised by finite automata with weights. Weights are restricted to semirings. Furthermore, the problem of equivalence of finite transducers is treated, which is undecidable even in the case where the output alphabet is unary, but is decidable if weights are considered. Two families of relations are described: the deterministic relations and the synchronous relations.

In Chapter V, functional relations realised by finite automata are investigated. Two hypotheses of functionality and rationality give together some remarkable structural results, particularly the theorem of Elgot and Mezei. The chapter ends with the study of sequential transducers and a characterisation of the sequential functions.

The author does not treat the relations between automata and logic, tree automata, infinite words, pushdown automata, as well as relations between numeration systems and finite automata. Every chapter contains exercises whose solutions are given at the end of the respective chapter. There are also further remarks and references. The book closes with a detailed bibliography.

The book is subdivided as follows:

Chapter 0: Fundamental structures: 1. Relations; 2. Monoids; 3. Words and languages; 4. Free monoids; 5. Semirings; 6. Matrices; 7. Lexicon of graph theory; 8. Complexity and decidability.

Chapter I: The simplest possible machines (automata on a free monoid): 1. What is an automaton? 2. Rational languages; 3. The functional point of view; 4. Rational expressions; 5. From expressions to automata; 6. Star height; 7. A field of automata; 8. A crop of properties.

Chapter II: The power of algebra (automata over an arbitrary monoid): 1. Automata and relational sets; 2. Actions and recognisable sets; 3. Morphisms and coverings; 4. The universal automaton; 5. The importance of being well ordered; 6. Relations in free groups; 7. Relations in commutative monoids; 8. Star height of group languages.

Chapter III: The pertinence of enumeration (weighted automata): 1. Formal power series on a graded monoid; 2. K-automata and K-relational series; 3. K-representations and K-recognisable series; 4. K-relational series on a free monoid; 5. Series with coefficients in a continuous semiring; 6. Relational subsets in free products; 7. A non-commutative linear algebra primer.

Chapter IV: The richness of transducers (relations realised by finite automata): 1. Rational relations: an introduction; 2. K-relations; 3. Rational K-relations; 4. Equivalence of finite K-transducers; 5. Deterministic rational relations; 6. Synchronisation of transducers; 7. Malcev-Neumann series.

Chapter V: The simplicity of functional transducers (functions realised by finite automata): 1. Functionary; 2. Uniformisation of rational relations; 3. Cross-section of rational functions; 4. Sequential functions.

MSC:
68Q45Formal languages and automata
20M35Semigroups in automata theory, linguistics, etc.
68Q70Algebraic theory of languages and automata
68-01Textbooks (computer science)