Theoretical computer science is often viewed as a collection of disparate topics, including computability theory, formal language theory, complexity theory, logic, and so on. This well-written book attempts to unify the subject by introducing each of these topics in turn, then showing how they relate to each other. The book can be used as a text for a single graduate or undergraduate course in one of the areas mentioned above, or it could be used for a year-long course in the theory of computation; such a course could cover several of these areas.

The text is a revision of a book by Davis and Weyuker which first appeared in 1983 [1]. The original edition had five major parts: computability, grammars and automata, logic, complexity, and unsolvability. The new edition has kept most of the first four parts of the original, with the exception of a chapter on loop programs. However, Part5 of the new edition consists of three new chapters on semantics. The authors note that this part was added to give the student a deeper understanding of computable functions and computation, and to introduce some ideas from the theory of programming languages.

Chapter 1, “Preliminaries,” which precedes Part 1, covers the basics of discrete mathematics--functions, alphabets and strings, predicates and quantifiers, and various proof techniques--needed for the later chapters.

Part 1, “Computability,” is about twice as long as any other part of the book. The formal system defined in chapter 2 relies on the student’s intuition about programming languages, by introducing the idea of a program computing a function. Chapter 3 covers primitive recursive functions. Chapter 4 discusses the major themes of computability, including the halting problem and the idea of a universal program. It then continues to more advanced topics, including Rice’s theorem and the recursion theorem. Chapter 5 introduces calculations on strings by Post-Turing programs. Chapter 6 returns to classical computability theory by defining a Turing machine. This chapter provides a universal Turing machine and discusses the halting problem for Turing machines. Chapter 7 interprets these results from the point of view of grammars and languages, including semi-Thue systems and the Post correspondence problem. Chapter 8 extends these results by considering oracles, the arithmetic hierarchy, and the classification of unsolvable problems. One major result of Part 1 is that the class of computable functions does not depend upon the details of any one particular formal system.

In Part 2, “Grammars and Automata,” chapters 9 and 10 cover regular languages (namely, those recognized by finite automata) and context-free languages. Chapter 11 completes the classical Chomsky hierarchy by discussing the context-sensitive languages, including a relatively recent result of N. Immerman showing that the class of context-sensitive languages is closed under complementation.

Part 3, “Logic,” starts with a study of propositional calculus and quantification theory; it continues with Herbrand’s theorem, a brief discussion of unification, and Gödel’s incompleteness theorem. Part 4, “Complexity,” covers topics ranging from the Blum axioms for an abstract complexity measure to the gap and speedup theorems. Chapter 15 discusses polynomial-time computability, Cook’s theorem, NP-completeness, and the P = NP question.

Part 5 is called “Semantics.” Chapter 16 begins this topic by investigating approximation orderings. Chapter 17 applies these ideas to the study of denotational semantics of recursion equations. Chapter 18 returns to the concept of computations for programs, using operational semantics.

Although the book covers a wide variety of theoretical concepts, the authors take great pains to stress which topics rely on previous material and which do not. A detailed dependency graph outlines the order in which chapters can be studied. In each part, the authors have tried to integrate the material with earlier concepts. For example, chapter11, on context-sensitive languages, builds on the previous chapters on formal language theory; it also relies on notions from computability theory. Chapter 13, on quantification theory, depends on both chapter 12 (propositional calculus) and chapter 7 (processes and grammars). The material on semantics builds on results from the computability section.

The text follows a lemma-theorem-proof-corollary style of presentation. However, the writing style is exceptionally clear, and the reader should not have much trouble following the exposition. Almost every section now has a set of exercises. The exercises range from relatively simple examples of the results presented in the section, to proofs that extend these results, to more challenging problems. In fact, the second edition contains about twice as many exercises as the first edition, making the exercise set much more useful to an instructor. In addition, the authors have now included a “Notation Index,” which lists all of the symbols used in the text. This is especially helpful in Part 5, in which the notation gets rather dense. The book ends with a list of “Suggestions for Further Reading.” However, almost all of the recent references (from the last 10 years) deal with programming language semantics. The authors should include some of the many new books on other areas as well.

The authors note that the book can be used for a variety of introductory theoretical computer science courses (such as theory of computation, finite automata and languages, logic, and programming language semantics), or their preference, a unified approach to the subject. This is an excellent book that succeeds in tying together a number of areas in theoretical computer science.