Book review

The theory of automata has developed rapidly in the last decades to a clear algebraic insight into the basic concepts. The original notion of a sequential automaton (describing only the input-output behavior) has been generalized in many directions. The authors use in their book two such kinds of automata, namely linear sequential automata, arising from the theory of dynamical systems and tree automata, having an arbitrary algebra as their basic structure. Sequential automata and tree automata and their relationships with languages as well as their minimal realizations are studied in Chapters 1 and 2. Some results on these topics did not appear till now in a book. The first approach to automata theory by using categories and functors was given in the papers written by M.A. Arbib and G.E. Manes in seventieth (see [3] - [8]). They studied automata in a category which is the category of sets for the linear sequential automata and the tree automata, or the category of modules for the linear sequential automata. The fundamental idea is to express the type of studied automata by a suitable functor on that category. In the third chapter of the book, the concepts of Arbib and Manes are presented and thereafter the authors develop a theory of functorial automata, based on the researches of the Prague Seminar on General Mathematical Structures since 1970 (see [1], [2], [12], [13]).

An F-automaton in a category K, where F: K -> K is a functor expressing the type, is an algebra of type F endowed with an output. Automata in monoidal categories are also captured in this way. The authors have studied in the book the existence and construction of free F-algebras (Chapter 4), the existence of minimal realizations for all behaviors (Chapter 5) and their construction and universability (Chaptier 6), as well as the languages recognizable by finite deterministic and nondeterministic automata (Chapter 7).

Although these problems are very difficult when they are investigated in a general category with a general functor, in some individual cases considered in the book they can be solved in interesting ways. The authors established sufficient and necessary conditions on the functor for an affirmative answer to the existence problems quoted above. (or instance, if the functor F is a finitarity functor, then all behaviors have minimal realizations. For the converse, the automaton has to satisfy additional conditions.

Necessary and sufficient conditions for: (i) the constructive and "finitary" existence of free algebras; (ii) the existence and universability of minimal realizations; (iii) the descriptions of the languages recognized by finite automata using rational operations, and the coincidence of these languages with those recognized by nondeterministic automata, are given with diverse degree of generality. The problem (i) is studied in the general case, while (ii) need some restrictive assumptions, and (iii) is studied only in the category of sets.

In case of the categories Set and R-Vect (vector spaces over the field R), F-automata have minimal realizations if and only if F is a finitary functor. This is not true for other categories, which need other restrictions for the functor F. The construction of a free algebra (Chapter 4) holds for all functors in Set and R-Vect.

The existence of an adjoint for F where the category is closed has been obtained by J.A. Goguen [11], L. Budach and J.-H. Hoehnke [8] and others. The interplay between functors and automata has yielded new insights in both automata theory and category theory.

In what concerns the theory of automata, the book gives all necessary knowledge, while the reader has to be familiar with the basic category theory.

Historical comments appear at the ends of all chapters. A large list of references used in the book can be necessary for those who will read the book. The authors fixed carefully the notations and the set-theoretical conventions.

The book is addressing to mathematicians and computer scientists who have interest in automata theory, category theory and universal algebras.

References.

[1] Adamék, J.: Free algebras and automata realizations in the language of categories, Comment. Math. Univ. Carolinae 15 (1974), 589-602.

[2] Adamék, J.: Automata and categories, finiteness contra minimality, Lect. Notes Comp. Sci. 32, Springer Verlag, Berlin, Heidelberg, New York, 1975, 160-166.

[3] Arbib, M.A. and Manes, E.G.: Machines in a category: an expository introduction, SIAM Review 16 (1974), 163-192.

[4] Arbib, M.A. and Manes, E.G.: Foundations of system theory: decomposable systems, Automatica 10 (1974), 285-302.

[5] Arbib, M.A. and Manes, E.G.: Adjoint machines, state behavior machines and duality, J. Pure Appl. Algebra 6 (1975), 313-343.

[6] Arbib, M.A. and Manes, E.G.: Fuzzy machines in a category, Bull. Austral. Math. Soc. 13 (1975), 169-210.

[7] Arbib, M.A. and Manes, E.G.: Partially-additive categories and flow-diagram semantics, J. Algebra 62 (1980), 203-227.

[8] Budach, L. and Hoehnke, H.-J.: Automata und Funktoren, Akademic Verlag, Berlin, 1975.

[9] Eilenberg, S.: Automata, languages and machines, vol. A, Academic Press, New York, London, 1974.

[10] Eilenberg, S. and Wright, J.B.: Automata in general algebras, Inf. Control 11 (1967), 52-70.

[11] Goguen, J.A.: Minimal realization machines in closed categories, Bull. Amer. Math. Soc. 78 (1972), 778-783.

[12] Trnková, V.: On minimal realizations of behavior maps in categorical automata theory, Comment. Math. Univ. Carolinae 15 (1974), 555-566.

[13] Trnková, V.: Automata and categories, Lect. Notes Comp. Sci. 32, Springer Verlag, Berlin, Heidelberg, New York, 1975, 138-152.