Automata-theoretic aspects of formal power series
Author(s)
Bibliographic Information
Automata-theoretic aspects of formal power series
(Texts and monographs in computer science)
Springer-Verlag, 1978
- : pbk
Available at 1 libraries
  Aomori
  Iwate
  Miyagi
  Akita
  Yamagata
  Fukushima
  Ibaraki
  Tochigi
  Gunma
  Saitama
  Chiba
  Tokyo
  Kanagawa
  Niigata
  Toyama
  Ishikawa
  Fukui
  Yamanashi
  Nagano
  Gifu
  Shizuoka
  Aichi
  Mie
  Shiga
  Kyoto
  Osaka
  Hyogo
  Nara
  Wakayama
  Tottori
  Shimane
  Okayama
  Hiroshima
  Yamaguchi
  Tokushima
  Kagawa
  Ehime
  Kochi
  Fukuoka
  Saga
  Nagasaki
  Kumamoto
  Oita
  Miyazaki
  Kagoshima
  Okinawa
  Korea
  China
  Thailand
  United Kingdom
  Germany
  Switzerland
  France
  Belgium
  Netherlands
  Sweden
  Norway
  United States of America
Note
Bibliography: p. 165-167
Includes index
Description and Table of Contents
Description
This book develops a theory of formal power series in noncommuting variables, the main emphasis being on results applicable to automata and formal language theory. This theory was initiated around 196O-apart from some scattered work done earlier in connection with free groups-by M. P. Schutzenberger to whom also belong some of the main results. So far there is no book in existence concerning this theory. This lack has had the unfortunate effect that formal power series have not been known and used by theoretical computer scientists to the extent they in our estimation should have been. As with most mathematical formalisms, the formalism of power series is capable of unifying and generalizing known results. However, it is also capable of establishing specific results which are difficult if not impossible to establish by other means. This is a point we hope to be able to make in this book. That formal power series constitute a powerful tool in automata and language theory depends on the fact that they in a sense lead to the arithmetization of automata and language theory. We invite the reader to prove, for instance, Theorem IV. 5. 3 or Corollaries III. 7. 8 and III. 7.- all specific results in language theory-by some other means. Although this book is mostly self-contained, the reader is assumed to have some background in algebra and analysis, as well as in automata and formal language theory.
Table of Contents
I. Introduction.- I.1. Preliminaries from algebra and analysis.- I.2. Preliminaries from automata and formal language theory.- I.3. Formal power series in noncommuting variables.- II. Rational series.- II.1. Rational series and linear systems.- II.2. Recognizable series.- II.3. Hankel matrices.- II.4. Operations preserving rationality.- II.5. Regular languages and rational series.- II.6. Fatou properties.- II.7. On rational series with real coefficients.- II.8. On positive series.- II.9. Rational sequences.- II.10. Positive sequences.- II.11. On series in product monoids.- II.12. Decidability questions.- III. Applications of rational series.- III.1. On rational transductions.- III.2. Families of rational languages.- III.3. Rational series and stochastic automata.- III.4. On stochastic languages.- III.5. On one-letter stochastic languages.- III.6. Densities of regular languages.- III.7. Growth functions of L systems: characterization results.- III.8. Growth functions of L systems: decidability.- IV. Algebraic series and context-free languages.- IV.1. Proper algebraic systems of equations.- IV.2. Reduction theorems.- IV.3. Closure properties.- IV.4. Theorems of Shamir and Chomsky-Schiitzenberger.- IV.5. Commuting variables and decidability.- IV.6. Generalizations of proper systems. Fatou extensions.- IV.7. Algebraic transductions.- Historical and bibliographical remarks.- References.
by "Nielsen BookData"