Ehrig / Kiermeier / Kreowski Universal Theory of Automata

A Categorical Approach
1974
ISBN: 978-3-322-96644-5
Verlag: Vieweg & Teubner
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, 240 Seiten, eBook

Reihe: XTeubner Studienbücher Informatik

Zielgruppe

Upper undergraduate

Autoren/Hrsg.

Ehrig, H.

Kiermeier, K.-D.

Kreowski, H.-J.

Kühnel, W.

Inhaltsverzeichnis

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); strongminimality (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.