Rational series and their languages.

*(English)*Zbl 0668.68005
EATCS Monographs on Theoretical Computer Science, 12. Berlin etc.: Springer-Verlag. viii, 151 p.; DM 64.00 (1988).

The book is the English version of “Les séries rationelles et leurs languages” by the same authors [Études et recherches en informatique, Masson, Paris (1984; Zbl 0573.68037)], with two new chapters added at its end. It is an elegant exposition of the theory of rational series and some of their most important applications, which asks for a careful and advanced reader. There are interesting exercises and notes at the end of each chapter, the latter on the historical development, further remarks, and open problems, all with hints to the about 80 references given in the bibliography.

Let \(K=(K,+, \cdot,0,1)\) be an additively commutative semiring with neutral elements 0 and 1 for \(+\) and \(\cdot\) such that \(0a=a0=0\) holds for all \(a\in K\), and \(X\neq \emptyset\) a finite set, called alphabet. The subsets of the free monoid \(X^*\), called languages over X, form a semiring \({\mathcal L}=({\mathcal L},\cup,\circ,\emptyset,1)\), where 1 denotes here the empty word of \(X^*\). For K as above, the set of all mappings S: \(X^*\to K\) denoted by \(w\to (S,w)\in K\) form a semiring with respect to pointwise addition and convolution as multiplication, which contains \((X^*, \cdot)\) and \((K,+, \cdot,0,1)\) as substructures in a natural way. In this book, the semiring of formal series is denoted by \(K\ll X\gg\). The polynomials, i.e., the series with finite support, form a subsemiring \(K<X>\) of \(K\ll X\gg\). By a topology on \(K\ll X\gg\), also introduced in Chapter I, summable families \((S_ i)_{i\in I}\) of power series \(S_ i\) are defined. In particular, \(((S,w)w)_{w\in X^*}\) is summable for each \(S\in K\ll X\gg\) and yields \(S=\sum_{w\in X^*}(S,w)w\). Moreover, for each proper series S, defined by \((S,1)=0\), the sum \(S^*=\sum_{n\geq 0}S^ n\) exists, called the star of S. A formal series is called rational if it is contained in the rational closure of \(K<X>\), i.e., the smallest subsemiring of \(K\ll X\gg\) which contains \(K<X>\) and is closed with respect to the star operation.

For the Boolean semiring \({\mathbb{B}}=\{0,1\}\), each series of \({\mathbb{B}}\ll X\gg\) corresponds uniquely to a language over X such that the semirings \({\mathbb{B}}\ll X\gg\) and \({\mathcal L}\) are isomorphic. So a famous theorem of Kleene can be reformulated as follows: each language recognized by a finite-state automaton corresponds to a rational series of \({\mathbb{B}}\ll X\gg\) and conversely. This can be generalized for each semiring K to a theorem due to Schützenberger, stating that a series \(S\in K\ll X\gg\) is recognizable iff it is rational, where the former refers to K-linear analogues of finite automata or is defined algebraically by the existence of a certain linear representation of S.

In Chapter II, using concepts as syntactic ideal and syntactic algebra [cf. J. Algebra 66, 448-483 (1980; Zbl 0444.68075)], the reduction of those linear representations to reduced ones is investigated. In Chapter III the relations between rational series and languages are considered, where the support of those series is one of the main objects.

The next chapter on rational series in one variable over a commutative field K deals with arithmetic properties of the expansion of rational fractions. Also Chapter V is closely connected to number theory, where rational series over special rings and semirings are considered with respect to the question which rational series of \(K\ll X\gg\) are those over a subsemiring of K. The next chapter presents some positive results concerning decidability. In the last two chapters, added in this edition of the book, polynomials in non-commutative variables, properties concerning their factorization, and applications to coding theory are studied.

Let \(K=(K,+, \cdot,0,1)\) be an additively commutative semiring with neutral elements 0 and 1 for \(+\) and \(\cdot\) such that \(0a=a0=0\) holds for all \(a\in K\), and \(X\neq \emptyset\) a finite set, called alphabet. The subsets of the free monoid \(X^*\), called languages over X, form a semiring \({\mathcal L}=({\mathcal L},\cup,\circ,\emptyset,1)\), where 1 denotes here the empty word of \(X^*\). For K as above, the set of all mappings S: \(X^*\to K\) denoted by \(w\to (S,w)\in K\) form a semiring with respect to pointwise addition and convolution as multiplication, which contains \((X^*, \cdot)\) and \((K,+, \cdot,0,1)\) as substructures in a natural way. In this book, the semiring of formal series is denoted by \(K\ll X\gg\). The polynomials, i.e., the series with finite support, form a subsemiring \(K<X>\) of \(K\ll X\gg\). By a topology on \(K\ll X\gg\), also introduced in Chapter I, summable families \((S_ i)_{i\in I}\) of power series \(S_ i\) are defined. In particular, \(((S,w)w)_{w\in X^*}\) is summable for each \(S\in K\ll X\gg\) and yields \(S=\sum_{w\in X^*}(S,w)w\). Moreover, for each proper series S, defined by \((S,1)=0\), the sum \(S^*=\sum_{n\geq 0}S^ n\) exists, called the star of S. A formal series is called rational if it is contained in the rational closure of \(K<X>\), i.e., the smallest subsemiring of \(K\ll X\gg\) which contains \(K<X>\) and is closed with respect to the star operation.

For the Boolean semiring \({\mathbb{B}}=\{0,1\}\), each series of \({\mathbb{B}}\ll X\gg\) corresponds uniquely to a language over X such that the semirings \({\mathbb{B}}\ll X\gg\) and \({\mathcal L}\) are isomorphic. So a famous theorem of Kleene can be reformulated as follows: each language recognized by a finite-state automaton corresponds to a rational series of \({\mathbb{B}}\ll X\gg\) and conversely. This can be generalized for each semiring K to a theorem due to Schützenberger, stating that a series \(S\in K\ll X\gg\) is recognizable iff it is rational, where the former refers to K-linear analogues of finite automata or is defined algebraically by the existence of a certain linear representation of S.

In Chapter II, using concepts as syntactic ideal and syntactic algebra [cf. J. Algebra 66, 448-483 (1980; Zbl 0444.68075)], the reduction of those linear representations to reduced ones is investigated. In Chapter III the relations between rational series and languages are considered, where the support of those series is one of the main objects.

The next chapter on rational series in one variable over a commutative field K deals with arithmetic properties of the expansion of rational fractions. Also Chapter V is closely connected to number theory, where rational series over special rings and semirings are considered with respect to the question which rational series of \(K\ll X\gg\) are those over a subsemiring of K. The next chapter presents some positive results concerning decidability. In the last two chapters, added in this edition of the book, polynomials in non-commutative variables, properties concerning their factorization, and applications to coding theory are studied.

Reviewer: H.J.Weinert

##### MSC:

68-02 | Research exposition (monographs, survey articles) pertaining to computer science |

16Y60 | Semirings |

16W60 | Valuations, completions, formal power series and related constructions (associative rings and algebras) |

68Q45 | Formal languages and automata |

68Q70 | Algebraic theory of languages and automata |