Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Switching and finite automata theory (3rd ed.)
Kohavi Z., Jha N., Cambridge University Press, New York, NY, 2009. 630 pp. Type: Book (978-0-521857-48-2)
Date Reviewed: Jul 16 2010

This timeless classic is back again with a new edition, 32 years after its last edition [1]. If you intend to study computer engineering, read this book first, then do the hundreds of excellent exercises, and then read the book again. Then, continue your studies with Hopcroft, Ullman, and Motwani’s text [2]. Finally, read Hennessy and Patterson’s book [3]. Only then can you call yourself well prepared. The book has undergone some changes since its first edition in 1970 [4], but thanks to the authors’ touch, it has not lost its original charm.

The book is divided into three parts. Part 1 comprises two chapters. Chapter 1 deals with the representation of numerical data. It describes special methods of representing numerical data that afford protection against various transmission errors and component failures. The focus is on those representations that use only two symbols. It is a concise introduction to number systems and error-detecting and error-correcting codes. Chapter 2 develops, in an intuitive manner, the notions of sets, relations, and partial ordering, which together form the basis for the representation of some results from lattice theory and Boolean algebra. Thus, it furnishes the algebraic concepts necessary to understand later chapters. The chapter is by no means a complete treatment of the subjects, but rather a survey of some results.

After these preliminaries, Part 2 deals with various aspects of the analysis and design of combinational switching circuits. Chapter 3 develops a switching algebra from the simplest set of basic postulates and applies it to the study of switching circuits and the calculus of propositions. Finally, this switching algebra is shown to be a special case of Boolean algebra. Systematic simplification procedures of these switching expressions are then presented in chapter 4. For this edition, two sections were added to the chapter, including one of the most detailed descriptions of Karnaugh maps that I know of. Logical design, with special attention being paid to conventional logic, is studied in chapter 5. A completely rewritten description of complementary metal-oxide semiconductor (CMOS) circuits is presented in chapter 6, and threshold logic is the topic of chapter 7. Both chapters are rather specific and could be omitted at first reading. The final chapter of Part 2, which was also completely rewritten, studies various fault models and presents techniques for generating tests regarding different types of faults.

Part 3 is concerned with synchronous sequential circuits in general, and finite state automata in particular. Compared to combinational switching circuits, the output values of synchronous sequential circuits are functions of external input values, as well as internally stored information. These are introduced in chapter 9 and discussed in more detail in chapter 10. In larger systems, it is often desirable to allow certain subsystems to operate asynchronously, thereby avoiding some of the problems associated with clocking. Asynchronous sequential circuits are presented in chapter 11. A finite state automaton is an abstract model that describes the synchronous sequential machine. Chapters 12 to 16 study the behavior, capabilities, limitations, and structure of finite state automata. Although these last few chapters deal with rather advanced topics, the authors do not rush--they patiently keep the pace of a verbose textbook.

This recent edition removed the dust and polished some parts, where necessary. Now, this book shines again.

Reviewer:  Klaus Galensa Review #: CR138172 (1103-0248)
1) Kohavi, Z. Switching and finite automata theory (2nd ed.). McGraw-Hill, New York, NY, 1978.
2) Hopcroft, J.E.; Motwani, R.; Ullman, J.D. Introduction to automata theory, languages, and computation (3rd ed.). Pearson/Addison Wesley, Boston, MA, 2007.
3) Hennessy, J.L.; Patterson, D.A. Computer architecture: a quantitative approach (4th ed.). Morgan Kaufmann, Boston, MA, 2007.
4) Kohavi, Z. Switching and finite automata theory. McGraw-Hill, New York, NY, 1970.
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
Automata (F.1.1 ... )
 
 
Combinational Logic (B.6.1 ... )
 
 
Design Styles (B.6.1 )
 
 
General (F.4.0 )
 
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