Les séries rationnelles et leurs langages. (French) Zbl 0573.68037

Berstel, J.; Reutenauer, C.

Etudes et Recherches en Informatique. Paris etc.: Masson. 132 p. (1984).

The book is an introduction into the rational series in several noncommutative variables and their connection with formal languages, from algebraic point of view. As stated by the authors, the aim of the book is that of presenting the fundamental results about rational series, without dealing with the applications in engineering, combinatorics and so on.
In the first chapter the rational and recognizable series are introduced. The principal general results are given, such as the fundamental theorem of Schützenberger which establishes the equality between rational and recognizable series. It is shown that the Hadamard product preserves the recognizability.
Using syntactic algebras, chapter II includes the fact that the rational series are characterized by the finite dimension of their syntactic algebras. The linear reduced representation of rational series is studied and an algorithm for finding them is given.
The languages associated to rational series are studied in chapter III. Using Schützenberger’s theorem, the Kleene’s theorem is obtained. It is proved that any series on a commutative ring has as support a rational (regular) language. Closure properties of the family of languages which are supports of rational series are also included.
Chapter IV deals with rational series in one variable. The arithmetic properties of the coefficients of such rational series are studied. Using a theorem due to Skolem, it is shown that the support of rational series with coefficients in Q are rational languages.
Chapter V analyzes how the class of rational series is modified by extending the semiring in which they are defined. Properties of the positive rational series as well as a characterization of \(R_+\)- rational series are given.
Chapter VI is dedicated to decidability problems as: the finiteness of the supports and images of rational series and the equality of the supports of two such series. It is proved that it is decidable if a rational series with integer coefficients has a polynomial growth.
The book is of special interest for researchers in theoretical informatics, especially through the rigorous and didactical approach of the subject.

Reviewer: H.Georgescu

MSC:

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

Keywords:

rational series; formal languages; recognizable series; syntactic algebras; Closure properties; rational languages; decidability