×

Noncommutative rational series with applications. (English) Zbl 1250.68007

Encyclopedia of Mathematics and Its Applications 137. Cambridge: Cambridge University Press (ISBN 978-0-521-19022-0/hbk). xiii, 248 p. (2011).
The book is an updated, revised, and extended version of the classic textbook [Rational series and their languages. EATCS Monographs on Theoretical Computer Science, 12. Berlin etc.: Springer (1988; Zbl 0668.68005)]. It is a reference handbook suitable for researchers working on algebraic theory of automata and related fields. The text requires mathematically mature readers, but rewards the reader with insights beyond what is typically found in textbooks on the matter (see, e.g., Chapter 4 titled “Rational and recognisable power series” by J. Sakarovitch in [M. Droste (ed.), W. Kuich (ed.) and H. Vogler (ed.), Handbook of weighted automata. Monographs in Theoretical Computer Science. An EATCS Series. Berlin: Springer (2009; Zbl 1200.68001)]). Since the text was originally developed out of a lecture script, the book can also be used to run a graduate course on the subject matter. It contains exercises for each chapter together with bibliographical and historical remarks. Finally, a few open questions are raised on the final pages of the book.
A formal power series is a mapping from the set of all strings (elements of the free monoid) over a finite alphabet into the carrier of a (potentially non-commutative) semiring, which is a ring potentially lacking additive inverses. The polynomials are those series that map almost all strings to the additive neutral element 0. The set of all formal power series itself forms again a non-commutative semiring with point-wise addition and convolution. The iteration is the convolution closure (or iterated convolution), which is only defined for series that assign 0 to the empty string. The smallest subsemiring of the semiring of formal power series that contains all polynomials and is closed under iteration is the semiring of rational series. These series are the fundamental notion under inspection in this book.
Chapter 1 formally introduces the main notions and develops several equivalent characterizations of rational series in terms of weighted automata and stable finitely-generated submodules. The main result of the chapter shows that all those notions are indeed equivalent. The short section on weighted automata, which are the main operational model used in applications such as speech processing, is new and provides a tie to much of the current literature on rational series.
Chapter 2 shows that the linear representations used in weighted automata can be minimized if the semiring is actually a field. This is based on a vector space representation and its unique minimal basis. A simple algorithm for the minimization of a representation is provided and proved to be correct. Chapter 3 develops the relation between a rational series and its support, which is the language containing all non-zero weighted strings. It also recalls several additional characterizations of rational languages (those over the Boolean semiring) and ties language operations to the corresponding ones on series. The short treatment of syntactic algebras is new.
Chapter 4 is completely new and investigates rational expressions in the spirit of regular expressions in the Boolean-weighted case. The expressions use essentially the rational operations already mentioned (sum, convolution, iteration). Since iteration is also called star, we can consider the least number of iterations required to express a given rational series: the star-height of the series, which is another notion that is borrowed from the Boolean-weighted case.
Chapter 5 is another new chapter that adds an investigation of automatic sequences, which are rational languages representing numbers. The main notions are recalled and their closure properties discussed. Then it is demonstrated that automatic sequences correspond exactly to the algebraic series. Chapter 6 considers the classical case of rational series in one variable (with one letter). The arithmetic properties of the expansions of such series are considered (Hankel matrix, rank, etc.) and several well-known theorems such as Benzaghou’s, Polya’s and the Skolem-Mahler-Loch theorem are proved.
Chapter 7 presents a thorough investigation of the effects of changing the semiring to the notion of rationality. In particular, given a rational series over a semiring that takes values in a subsemiring, it is determined if and when this series is rational in the subsemiring. The main notion in this chapter are Fatou extensions. The Sections 7.3 and 7.4, which cover polynomial identities and Fatou ring extensions, are completely new.
Chapter 8 considers the special case of one-variable series with non-negative coefficients only. The growth of such series is investigated and the star height is reconsidered in this special case. Sections 8.2 and 8.4 on polynomially bounded series and star height 2, respectively, are new. Chapter 9 discusses finite semigroups of matrices and develops several decidability results for rational series. In addition, growth properties are also investigated in this scenario. Section 9.2 on polynomial growth contains new material and Section 9.3 on limited languages over the tropical semiring is completely new.
Chapter 10 discusses non-commutative polynomials and the main tool, Cohn’s weak algorithm, which extends the well-known Euclidean algorithm. In addition, Gauss’s lemma is derived. Chapter 11 uses the established results for variable-length codes. The goal and main result shows that every finite complete code can be factorized into 3 polynomials that reflect the combinatorial structure of the code. The final Chapter 12, which is also new, investigates semi-simple syntactic algebras, which are related and applicable to bifix codes.
Overall, the book is an essential reference for all active researchers in the theory of weighted automata and will replace its classical predecessor, which seems to be out of print already.

MSC:

68-02 Research exposition (monographs, survey articles) pertaining to computer science
68Q45 Formal languages and automata
12K10 Semifields
15-02 Research exposition (monographs, survey articles) pertaining to linear algebra
15A04 Linear transformations, semilinear transformations
16W60 Valuations, completions, formal power series and related constructions (associative rings and algebras)
16Y60 Semirings
26A12 Rate of growth of functions, orders of infinity, slowly varying functions
68Q70 Algebraic theory of languages and automata
94A45 Prefix, length-variable, comma-free codes
05E15 Combinatorial aspects of groups and algebras (MSC2010)
PDFBibTeX XMLCite