Algebraic and structural automata theory. Transl. of algebraiczna i structuralna teoria automatów (PWN, Warsaw, 1985) (Q1188575)

[The articles of this volume will not be indexed individually.] This monograph presents the work done in the seventies and the early eighties by a research group active at the Technical University of Poznan. We shall first describe briefly the twelve chaptes individually. Chapter 0 (Basic mathematical concepts by T. Gajewski; pp. 1-6) simply lists some basic mathematical concepts and notations. The aim of Chapter 1 (Automata and languages by J. Stoklosa; pp. 7-34) is to place the subject matter of the book into a larger context by reviewing briefly the Chomsky hierarchy and the relevant grammar and automata types. Chapter 2 (Finite automata by L. Beyga; pp. 35-82) introduces the Mealy, Moore and Rabin-Scott models of deterministic and nondeterministic finite automata, and regular languages along with several associated concepts. In Chapter 3 (Minimization of automata by B. Mikolajczak; 83-117) minimization algorithms for deterministic and incomplete automata are presented. The computational complexities of these problems are also considered. Chapter 4 (Input subautomata by J. Bergandy and Z. Miadowicz; pp. 119- 153) discusses automata obtained from a given automaton by changing the input and output alphabets so that these are formed by some input and output words, respectively, of the original automaton. When the alphabets are formed by all words of a fixed length k, such an input subautomaton may be regarded as a k-channel realization of the original automaton. In Chapter 5 (Automata homomorphisms by B. Mikolajczak; pp. 155-196) several notions of homomorphisms between automata are considered. Special attention is devoted to the computation of the homomorphisms between two given automata. Chapter 6 (Realizations of automata. State assignment by P. Siwak; pp. 197-228) considers ways to realize an automaton by another automaton or by a network of automata and the related problem of state assignments. The well-known approach of Hartmanis and Stearns based on SP partitions and partition pairs is used. Chapter 7 (Realizations of automata. Structures of nets by P. Siwak; pp. 229-268) is devoted to more specialized realization issues. Loop-free, parallel and serial decompositions and shift-register realizations are considered. There are also sections on networks of asynchronously operating automata, cellular nets and minimum feedback realizations. Chapter 8 (Time-varying automata by T. Gajewski; pp. 269-299) introduces time-varying automata; these are automata in which the state-set, the transition function and the output function may vary with time. Most of the discussion concerns automata with a periodically varying structure. In Chapter 9 (Transforms and extensions of automata by L. Beyga; pp. 301- 317) two special ways of constructing new automata are considered. A transform of an automaton is obtained by modifying the transition function by a fixed mapping of the state set; usually this is an automorphism. An extension of an automaton is formed by directing the transitions from one isomorphic copy of the automaton to another by means of an isomorphism. Chapter 10 (Periodic sums of automata by Z. Miadowicz; pp. 319-346) is a detailed study of periodic sums of automata which are extensions of automata of the kind defined in the previous chapter. Chapter 11 (Linear automata by J. Stoklosa; pp. 347-369) presents some results by G. Herman on linear realizations of automata and discusses briefly linear shift registers. The bibliography contains more than 200 references most of which are more than ten years old and none very recent. There is also an index of terms and names. Some critical remarks about the book must be made. There are far too many typographical and other mistakes, and the English translation has not been revised as it should have been. For example, a frequently recurring problem is caused by the authors' somewhat arbitrary use or omission of definite and indefinite articles; often it is hard to known whether something is intended to be uniquely defined or not. Even many very basic concepts are defined so carelessly that a reader without advance knowledge of the topic will get into serious difficulties from the very beginning. Some proofs are faulty and many algorithms contain steps which should have been explained in greater detail in order to make them feasible. The introduction of much notation, many minor notions and several variations of concepts which are not used, or used very little, easily distracts the readers attention from the main developments. Hence, it is clear that the book cannot be recommended as the main text for a course. A more advanced reader is perhaps disturbed by the fact that while many simple results are proved in detail, the proofs of less obvious theorems are often omitted. The two main areas of the book are the structural theory of automata and the theory of time-varying automata. For the general part of the structure theory there exist better expositions, and the preoccupation with the work of the research group has also meant that many important aspects of the theory are not even mentioned here. However, a reader with the proper background may find some interesting special ideas and results in this book. The presentation of the theory of time-varying automata is probably the most extensive to be found in the literature.