×

Semirings, automata, languages. (English) Zbl 0582.68002

EATCS Monographs on Theoretical Computer Science, 5. Berlin etc.: Springer-Verlag. IX, 374 p. DM 118.00 (1986).
Usually, an automaton over an alphabet \(\Sigma\) is defined as being a system \(A=(Q,M,q_ 0,P)\) with Q the set of states, \(q_ 0\in Q\) the initial state, \(P\subset Q\) the set of final states and M:Q\(\times \Sigma \to {\mathcal P}(Q)\) the transition function. If one replaces the transition function by an equivalent transition matrix \(M\in {\mathcal P}(\Sigma)^{Q\times Q}\) one can develop automata and language theory by using the tools from linear algebra. From this point of view, a very nice result shows that the behavior of an automaton is a component of the unique solution of the linear system \(Y=MY+P\). The advantage of this approach consists in the fact that the ad hoc proofs are replaced by proofs computational in nature which are more satisfactory from mathematical point of view. This book contains the basic results concerning regular and context-free languages, pushdown automata and abstract families of languages from the point of view of semirings and linear algebra.
The first chapter familiarizes the reader with notions of linear algebra. Each section contains a list of exercises.
Contents: Introduction. Linear algebra, Semirings and power series, Convergence, Equations and identities, Strong convergence and cycle-free power series, Matrices, Linear systems and identities, Semirings with particular properties, Morphisms and representations. Automata: Automata in terms of matrices, Rational power series and decidability, Rational transductions, Pushdown automata, Abstract families of power series, Substitutions, Reset pushdown automata and counter automata. Algebraic systems, Algebraic series and context-free languages, The super normal form; Commuting variables, Decidability and Parikh’s theorem. Historical and bibliographical remarks. References. Subject index. Symbol index.
Reviewer: D.Lucanu

MSC:

68-02 Research exposition (monographs, survey articles) pertaining to computer science
68Q45 Formal languages and automata
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68Q70 Algebraic theory of languages and automata