Universal Theory of Automata

ISBN-13: 9783519020547 / Niemiecki / Miękka / 1974 / 240 str.

H. Ehrig;K. -D Kiermeier;H. -J Kreowski

Opis

Our purpose in writing this book is to present a universal theory of automata which on one hand unifies the theories of several well-known types of automata and on the other hand allows interesting new applications and results. The frame work for our development is category theory, especially universal constructions in monoidal categories. But we will carefully motivate and introduce all those (and only those) notions and results of category theory which are needed in our approach. The reader is only assumed to be familiar with sets, deterministic functions, relations and the basic no tions of structural mathematics. However, some knowledge of discrete probability distributions, linear algebra and general topology would be useful in understanding the corre sponding applications and in having a better background for the general theory. All our constructions and results are motivated and interpreted carefully with respect to the classical theory of deterministic, partial, linear, topolog ical, nondeterministic, relational and stochastic automata. The book is mainly devoted to students of theoretical com puter science or mathematics and can be used as a textbook in graduate courses or seminars. On the other hand it will also be useful for many other people, who are concerned with the interesting new research area of category theory applied to computation and control.

Spis treści

1. Unified Representation of Automata.- deterministic, nondeterministic, stochastic, linear, bilinear, and topological automata (1.1–1.7); monoidal categories (1.8–1.10); automata in monoidal categories (1.11–1.14).- 2. Some Problems in Automata Theory.- behavior, reduction, minimization and realization of deterministic automata (2.1–2.6); nondeterministic automata (2.7); transition monoids (2.8); structure theory (2.9).- 3. General Concepts of Reduction, Minimization and Realization.- concept of systematics (3.1); reduced, minimal and realizing systems and subsystematics (3.2–3.3); reduction theorem (3.4); minimal realization theorem (3.6).- 4. Behavior of Automata in Closed Categories: The Deterministic Case.- extended output morphisms and coproducts (4.2); machine morphisms and closed categories (4.3–4.4); characterization of automata (4.5); behavior and image-factorization (4.6–4.7); behavior characterization (4.8); list of examples (4.9).- 5. Reduction and Minimization of Automata in Closed Categories.- systematic of automata in closed categories (5.2); minimal realization theorem (5.3); observable and reduced automata (5.4); reduction and minimization theorem (5.5); monoid automata and transition monoids (5.6–5.7).- 6. Behavior of Automata in Pseudoclosed Categories: The Nondeterministic Case.- automata in pseudoclosed categories — extended output, machine morphism and behavior (6.2–6.4); characterization of machine morphisms and behaviors (6.6–6.7); list of examples (6.8).- 7. Reduction and Minimization of Automata in Pseudoclosed Categories.- construction of reduced and observable automata (7.2–7.4); realization (7.5); systematic of automata in pseudoclosed categories (7.6); reduction theorem (7.7); minimization theorem (7.8); strong minimality (7.9).- 8. Power Automata.- construction of power automata (8.2); power automata theorem (8.3–8.4); kernel automata (8.5).- 9. Initial Automata.- systematic of initial automata (9.2); free realization (9.3); minimal realization theorem (9.5); reachability theorem (9.7); reduction and observability construction (9.8–9.9); observable and finite realization (9.10); initial power automata (9.11).- 10. Scoop Minimization.- scoops and scoop automata theorem (10.2–10.4); scoop construction (10.5–10.7); scoop minimization theorem (10.8).- 11. Structure Theory of Automata.- construction of equalizer, product, coequalizer, coproduct and free automata (11.2–11.7); characterization of iso-, mono- and epimorphisms (11.8); factorization of automata morphisms (11.9).- 12. Appendix: Basic Notions of Category Theory.- categories (12.1); diagrams (12.2); iso-, mono-, epimorphisms (12.3); products, coproducts (12.4); functors (12.5); natural transformations (12.6); adjoint functors (12.7); comma categories (12.8); special limits and colimits (12.9–12.10).- Special Symbols.- References.