Automata-Theoretic Aspects of Formal Power Series
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...
| Main Authors: | , |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
New York, NY
Springer New York
1978, 1978
|
| Edition: | 1st ed. 1978 |
| Series: | Monographs in Computer Science
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
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