Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1250.68007
Berstel, Jean; Reutenauer, Christophe
Noncommutative rational series with applications. (English)
[B] Encyclopedia of Mathematics and Its Applications 137. Cambridge: Cambridge University Press. xiii, 248~p. \sterling~50.00 (2011). ISBN 978-0-521-19022-0/hbk

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 {\it J. Sakarovitch} in [{\it M. Droste} (ed.), {\it W. Kuich} (ed.) and {\it 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. \par 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. \par 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. \par 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. \par 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. \par 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. \par 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. \par 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. \par 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. \par 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.
[Andreas Maletti (Stuttgart)]

MSC 2000:: *68-02 Research monographs (computer science)
68Q45 Formal languages
12K10 Semi-fields
15-02 Research monographs (linear algebra)
15A04 Linear transformations (linear algebra)
16W60 Filtrations and valuations, etc. (assoc. rings and algebras)
16Y60 Semirings
26A12 Rate of growth of functions of one real variable
68Q70 Algebraic theory of automata
94A45 Codes in connection with formal languages
05E15 Combinatorial problems concerning the classical groups

Keywords: formal power series; recognizable formal language; non-commutative rational series; rational series; minimization; rational expression; automatic sequence; polynomial; matrix semigroup; variable-length code

Citations: Zbl 0668.68005

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]