Algebraic structure theory of sequential machines. (English) Zbl 0154.41701

Hartmanis, J.; Stearns, R. E.

Prentice-Hall International Series in Applied Mathematics. Englewood Cliffs, N.J.: Prentice-Hall, Inc. viii, 211 p. (1966).

The subject of this book is an area of research was started around 1954 by D. A. Huffman and E. F. Moore [J. Franklin Inst. 257, 161–190 (1954), 257, 275–303 (1954)] and an article in “Automata studies” (ed. by C. E. Shannon and J. McCarthy) (1956; this Zbl. 74, 112), pp. 129-156] and has since undergone a considerable growth in several diverse directions.
This book is devoted to the “structure theory” which was created and developed to a considerable degree of completeness and unity, in the period from 1960 to 1965. It is a merit of the book, that it can be read by anyone who has either some mathematical maturity, achieved through formal study, or engineering intuition developed through work in switching theory or experience in practical computer design.
After chapter 0 (Introduction to algebra) which is a review of basic algebraic concepts for the benefit of the non-mathematician reader, one can read a very clearly written exposition of the author’s original work on sequential machine decompositions (see chapters 1–6, Machines, Partitions and the substitution property, Partitions pairs and pair algebra, Loop-free structure of machines, State splitting Feedback and errors).
For the original papers, see e. g. the first author [Inform. and Control 5, 25-43 (1962); J. ACM 10, 78-88 (1963)], both authors [Inf. Control 5, 252–260 (1962) and 7, 485–507 (1964)].
Chapter 7 (Semigroups and machines) is a brief introduction to the modern machine decomposition theory as developed by K. B. Krohn and J. L. Rhodes (this Zbl. 148, 10). The proofs contained in this chapter follow H. P. Zeiger [MIT Ph. D. Thesis, Electrical Engineering Department (1964)] who used set systems and permutation rest machines.

Reviewer: József Dénes

MSC:

68Q45	Formal languages and automata
68-02	Research exposition (monographs, survey articles) pertaining to computer science
68-03	History of computer science