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.
Author(s): Jean Berstel, Christophe Reutenauer
Series: Encyclopedia of Mathematics and its Applications 137
Edition: 1
Publisher: Cambridge University Press
Year: 2010
Language: English
Pages: 249
Tags: Математика;Дискретная математика;
Cover......Page 1
Noncommutative Rational Series With Applications......Page 2
Preface......Page 6
Contents......Page 10
Part I - Rational series......Page 14
1 Semirings......Page 16
2 Formal series......Page 17
3 Topology......Page 18
4 Rational series......Page 19
5 Recognizable series......Page 23
6 Weighted automata......Page 28
7 The fundamental theorem......Page 30
1 Syntactic ideals......Page 40
2 Minimal linear representations......Page 45
3 The minimization algorithm......Page 48
1 Kleene’s theorem......Page 56
2 Series and rational languages......Page 58
3 Syntactic algebras and syntactic monoids......Page 61
4 Support......Page 62
5 Iteration......Page 65
6 Complementation......Page 66
1 Rational expressions......Page 72
2 Rational identities over a ring......Page 75
3 Star height......Page 77
4 Absolute star height......Page 83
Part II - Arithmetic......Page 86
1 Regular functions......Page 88
2 Stable submodules and operations on k-regular functions......Page 90
3 Automatic sequences......Page 95
4 Automatic sequences and algebraic series......Page 97
5 Algebraic series and diagonals of rational series......Page 101
1 Rational functions......Page 110
2 The exponential polynomial......Page 114
3 A theorem of Pólya......Page 118
4 A theorem of Skolem, Mahler, Lech......Page 122
1 Rational series over a principal ring......Page 134
2 Fatou extensions......Page 137
3 Polynomial identities and rationality criteria......Page 141
4 Fatou ring extensions......Page 143
1 Poles of positive rational series......Page 148
2 Polynomially bounded series over Z and N......Page 150
3 Characterization of K+-rational series......Page 152
4 Star height 2......Page 157
Part III - Applications......Page 164
1 Finite matrix semigroups and the Burnside problem......Page 166
2 Polynomial growth......Page 169
3 Limited languages and the tropical semiring......Page 177
1 The weak algorithm......Page 184
2 Continuant polynomials......Page 187
3 Inertia......Page 190
4 Gauss’s lemma......Page 195
1 Codes......Page 200
2 Completeness......Page 204
3 The degree of a code......Page 208
4 Factorization......Page 209
1 Bi x codes......Page 218
2 Cyclic languages......Page 221
Appendix 2: Minimal ideals in nite monoids......Page 225
Open problems and conjectures......Page 232
References......Page 234
Index of notation......Page 243
Index......Page 244
