E-Book Overview
The algebraic theory of automata was created by Sch?tzenberger and Chomsky over 50 years ago and there has since been a great deal of development. Classical work on the theory to noncommutative power series has been augmented more recently to areas such as representation theory, combinatorial mathematics and theoretical computer science. This book presents to an audience of graduate students and researchers a modern account of the subject and its applications. The algebraic approach allows the theory to be developed in a general form of wide applicability. For example, number-theoretic results can now be more fully explored, in addition to applications in automata theory, codes and non-commutative algebra. Much material, for example, Sch?tzenberger's theorem on polynomially bounded rational series, appears here for the first time in book form. This is an excellent resource and reference for all those working in algebra, theoretical computer science and their areas of overlap.
E-Book Content
1
2
3
4
Jean Berstel Christophe Reutenauer
Noncommutative Rational Series With Applications
5
April 9, 2010
6
c 2006 Jean Berstel and Christophe Reutenauer
7
c 1988 English translation: Rational Series and Their Languages Springer-Verlag
8
c 1984 French edition: Les s´eries rationnelles et leurs langages Masson
9
Pour Anne et Anissa
10
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
Preface Formal power series have long been used in all branches of mathematics. They are invaluable in algebra, analysis, combinatorics and in theoretical computer science. Historically, the work of M.-P. Sch¨utzenberger in the algebraic theory of finite automata and the corresponding languages has led him to introduce noncommutative formal power series. This appears in particular in his work with Chomsky on formal grammars. This last point of view is at the origin of this book. The first part of the book, composed of Chapters 1–4, is especially devoted to this aspect: Formal power series may be viewed as formal languages with coefficients, and finite automata (and more generally weighted automata) may be considered as linear representations of the free monoid. In this sense, via formal power series, algebraic theory of automata becomes a part of representation theory. The first two chapters, contain general results and discuss in particular the equality between rational and recognizable series (Theorem of Kleene–Sch¨utzenberger) and the construction of the minimal linear representation. The exposition illustrates the synthesis of linear algebra and syntactic methods inherited from automata theory. The next two chapters are concerned with the comparison of some typical properties of rational (regular) languages, when they are transposed to rational series. First, Chapters 3 describes the relationship with the family of regular languages studied in theoretical computer science. Next, the chapter contains iteration properties for rational series, also known as pumping lemmas, which are much more involved than those for regular languages. Chapter 4 discusses rational expressions. It contains two main results: the so-called “triviality” of rational identities over a commutative ring and the characterization of the star height of a rational series and its two consequences: the star height is unbounded and the star height over an algebraically closed field is decidable. The same problem for rational languages is known to be extremely difficult. The second part of the book, composed of Chapters 5–8, is devoted to arithmetic properties of rational series. Chapter 5 is concerned with automatic sequences and algebraic series. Two main results are th