Counter-Free Automata

By Robert McNaughton and Seymour A. Papert




A particular class of finite-state automata, christened by the authors “counter-free,” is shown here to behave like a good actor: it can frape itself so thoroughly in the notational guise and embed itself so deeply in the conceptual character to several quite different approaches to automata theory that on the surface it is hard to believe that all these roles are being assumed by the same class.

The author's write “... it is noteworthy that the class of automata we shall discuss was defined more or less explicitly by several people working from very different directions and using very different directions and using very different concepts. The remarkable happening was that these definitions could not be recognized as equivalent until algebraic tools of analysis were brought to the field in the works of Schützenberger and in the works of Krohn and Rhodes.”

The theme of the monograph is the unity and equivalence of these different definitions of counter-free automata. Its organization follows the plan of taking up, one by one, each of a number of different conceptualizations: the historically important “nerve net” approach; the algebraic approach, in which automata are treated as semigroups; the “classical” theory based on state transition diagrams; the “linguistic” approach based on the concept pf regular expressions; and the “behavioral” descriptions using symbolic logic. In each of these conceptual areas, the class of automata under study is found in a new guise. Each time it appears as yet another special case. The author's burden is to show that all these definitions are in fact equivalent.

Care has been taken so that this research monograph can be used as a self-sufficient text. Notations have been defined carefully and always in the context of the discussion. Most of the chapters end with a substantial number of exercises. It is self-contained in that al concepts are defined, and all theorems used are, with one exception, either fully proved or safely left as exercises for the student.


Out of Print ISBN: 9780262130769 163 pp. |