zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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. £ 50.00 (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-02Research monographs (computer science)
68Q45Formal languages and automata
12K10Semi-fields
15-02Research monographs (linear algebra)
15A04Linear transformations, semilinear transformations (linear algebra)
16W60Filtrations and valuations, etc. (associative rings and algebras)
16Y60Semirings
26A12Rate of growth of functions of one real variable, orders of infinity, slowly varying functions
68Q70Algebraic theory of languages and automata
94A45Prefix, length-variable, comma-free codes (communication theory)
05E15Combinatorial aspects of groups and algebras