Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
An introduction to automata theory
Shields M., Blackwell Scientific Publications, Ltd., Oxford, UK, 1987. Type: Book (9789780632015535)
Date Reviewed: Jan 1 1989

This book is based on a course of ten one-hour lectures given by the author to third year computer science and computer systems engineering students at the University of Kent. . . . My main aim was to show that systems, of which students had some experience, were capable of mathematical manipulation of a fairly non-trivial kind, that they are not obdurate monoliths approachable only by the dubious intuition of the ‘real programmer’. In other words, I attempted to present automata theory as a rudimentary formal theory of systems.

--From the Preface

This book focuses on relations between machines: implementation, equivalence, composition, and decomposition. It expounds the beautiful structure theory developed by Hartmanis and Stearns, but is much easier to read than the algebraic treatment in their book [1]. Two chapters show the extension of this approach to concurrent systems (specifically, to Petri nets and CCS).

A list of the chapter headings follows.

  • :9N(1) Great Aunt Eugenia and Other Automata

  • (2) Sundry Machines

  • (3) Implementing Finite Automata

  • (4) Implementation and Realisation

  • (5) Behavioural Equivalence, SP Partitions and Reduced Machines

  • (6) Parallel and Serial Composition of Automata

  • (7) The Parallel Decomposition Theorem

  • (8) The Serial Decomposition Theorem

  • (9) The Lattice of SP Partitions

  • (10) Analysis of Machines

  • (11) Concurrent Systems: Net Theory

  • (12) Concurrent Systems: The Calculus of Communicating Systems

The author succeeds admirably in his aims: the book serves as a worthy foil to the heavily language-theoretic viewpoint of standard textbooks such as Hopcroft and Ullman [2]. For a one-semester course, the teacher may add some formal language theory to build a rigorous course on finite state machines. Alternately, more material on concurrency could be added to form an advanced course on sequential and concurrent machines.

Reviewer:  K. Lodaya Review #: CR112676
1) Hartmanis, J. and Stearns, R. E.Algebraic structure theory of sequential machines. Prentice-Hall, Englewood Cliffs, NJ, 1966. See <CR> 8, 2 (March–April 1967), Rev. 11,635.
2) Hopcroft, J. E. and Ullmann, J. D.Introduction to automata theory. Addison-Wesley, Reading, MA, 1979. See <CR> 21, 6 (June 1980), Rev. 36,399.
Bookmark and Share
 
Automata (F.1.1 ... )
 
 
Parallelism And Concurrency (F.1.2 ... )
 
 
Relations Between Models (F.1.1 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Automata": Date
The congruence theory of closure properties of regular tree languages
Tirri S. Theoretical Computer Science 76(2-3): 261-271, 2001. Type: Article
Jun 1 1991
Distribution and synchronized automata
Petit A. Theoretical Computer Science 76(2-3): 285-308, 2001. Type: Article
Feb 1 1992
Efficient simulation of finite automata by neural nets
Alon N., Dewdney A., Ott T. Journal of the ACM 38(2): 495-514, 1991. Type: Article
Dec 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy