Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1188.68177
Sakarovitch, Jacques
Elements of automata theory. Translated from the French by Reuben Thomas. (English)
[B] Cambridge: Cambridge University Press. xxiv, 758~p. \sterling~90.00; \$~145.00 (2009). ISBN 978-0-521-84425-3/hbk

[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.
[Siegmar Gerber (Leipzig)]

MSC 2000:: *68Q45 Formal languages
20M35 Semigroups in automata theory, linguistics, etc.
68Q70 Algebraic theory of automata
68-01 Textbooks (computer science)

Keywords: finite automata; functional transducers; morphisms; weighted automata; free monoids; formal languages; formal power series

Citations: Zbl 1178.68002

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]