商品詳細(参照) | Knowledge Worker

Automata-Theoretic Aspects of Formal Power Series 1978th ed.(Monographs in Computer Science) H x, 171 p. 78

Salomaa, Arto, Soittola, Matti 　著

在庫状況お取り寄せ	お届け予定日 1ヶ月
価格 \22,808（税込）

発行年月	1978年03月
出版社／提供元	Springer-Verlag New York
出版国	アメリカ合衆国
言語	英語
媒体	冊子
装丁	hardcover
ページ数／巻数	171 p.
ジャンル	洋書
ISBN	9783540902829
商品コード	0208419078
商品URL	https://kw.maruzen.co.jp/ims/itemDetail.html?itmCd=0208419078

内容

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.

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.