Berstel J., Reutenauer C. Rational Series and Their Languages

Springer, 2006. — 148 p.This book is an introduction to rational formal power series in several noncommutative variables and their relations to formal languages and to the theory of codes.
Formal power series have long been used in all branches of mathematics. They are invaluable in enumeration and combinatorics. For this reason, they are useful in various branches of computer science. As an example, let us mention the study of ambiguity in formal grammars.
It has appeared, for the past twenty years, that rational series in noncommutative variables have many remarkable properties which provide them with a rich structure. Knowledge of these properties makes them much easier to manipulate than, for instance, algebraic series. The depth and number of results for rational series are similar to those for rational languages. The aim of this text is to present the basic results concerning rational series.
The point of view adopted here seems to us to be a natural one. Frequently one observes that a set of results becomes a theory when the initial combinatorial techniques are progressively replaced by more algebraic ones. We have tried wherever possible to substitute an algebraic approach for a combinatorial description. This has made it possible for us to give a unified and more complete presentation that is hopefully also easier to understand. We feel that, in this manner, the fundamental mechanisms and their interactions are easier to grasp.
The first part of the book, comprising the first two chapters, illustrates very well how the introduction of an algebraic concept, namely syntactic algebra, can give a unified presentation. These two chapters contain the most important general results and discuss in particular the equality between rational and recognizable series and the construction of the reduced linear representation.
The following two chapters are devoted to the two applications which seemed most important to us. First, we describe the relationship with the families of formal languages studied in theoretical computer science. Next, we establish the correspondence with the rational functions in one variable as studied in number theory.
Chapter V presents arithmetic properties of rational series and their relations to the nature of their coefficients. These results are fairly profound, and there is a constant interaction with number theory. Let us mention the analytic characterization of N-rational series, which is the first result of this kind.
The next chapter presents several results on decidability. We describe only some positive results which are of increasing importance. Those given here are directly related to the Burnside problem.
The last two chapters are devoted to the study of polynomials in noncommutative variables, and to their application to coding theory. Because of noncommutativity, the structure of polynomials is much more complex that it would be in the case of commutativity, and the results are rather delicate to prove. We present here basic properties concerning factorizations, without trying to be complete. The main purpose of Chapter VII is to prepare the ground for the final chapter which contains the generalization of a result of M.-P. Schützenberger concerning the factorization of a polynomial associated with a finite code.
Exercises are provided for most chapters and also short bibliographical notes.
The algebraic and arithmetic approach adopted in this book implies a choice in the set of possible applications. We do not describe several important applications, such as the use of polynomials in control theory, where formal series in noncommutative variables are employed to represent the behavior of systems and replace the Volterra series (Fliess 1981, Isidori 1985). Another area of application is combinatorial graph theory. Enumeration of graphs by wellchosen encodings leads to systems of equations in noncommutative formal series whose solutions give the desired enumeration. Cori (1975) gives an introduction to the topic. The analysis of algorithms also leads to the study of formal series in a somewhat larger context (see Steyaert and Flajolet 1983, Berstel and Reutenauer 1982).Rational Series
Minimization
Series and Languages
Rational Series in One Variable
Changing the Semiring
Decidability
Noncommutative polynomials
Codes and Formal Series