Around the world, a course in the theory of computation, for graduate students or advanced undergraduates, is a staple of the curriculum.

The outlines of the subject itself were developed starting with Turing (On computable numbers, with an application to the Entscheidungsproblem, 1936). By now, the results that make it into a book at this level do not form a brand new subject: In Chen’s book, Chapter 1 concludes with the Myhill–Nerode theorem (1957), Chapter 2 with Rice’s theorem (1951), and Chapter 3 with NP-completeness results going back to Cook (The Complexity of Theorem Proving Procedures, 1971). The final Chapter 4 goes beyond the 1970s with parametrized complexity as introduced by Gurevich, Stockmeyer, and Vishkin (Solving NP-hard problems on graphs that are almost trees and an application to facility location problems, 1984). This subject was first systematically treated in Downey and Fellows. Parametrized Complexity (1999) and has been due for an appearance in introductory texts.

Of course, the topics covered do not exhaust the subject of computability and complexity. Randomness in computation and the complexity class BPP are missing from Chen’s book, as are context-free languages and quantum computing. Instructors deciding which book to use for their course will have to weigh what they consider to be essential.

Given the age of the subject, there are now quite a few books available: Hopcroft and Ullman’s Introduction to Automata Theory, Languages, and Computation (first edition 1979) and Sipser’s Introduction to the Theory of Computation (first edition 1996) have been popular choices. Hubie Chen’s doctoral advisor Dexter Kozen has a book at the undergraduate level— Automata and Computability (1997)—and there are comprehensive books aimed at researchers, such as Arora and Barak’s Computational Complexity: A Modern Approach (2007).

While Hopcroft and Ullman eventually was considered too demanding for many undergraduates, Sipser famously breaks proofs down into two parts, an intuitive sketch and a detailed treatment. At the same time, Sipser is lacking in formality in some ways.

A pet peeve of mine is the treatment of finite automata: Instead of extending the transition function $\delta $ to a function on words $\delta ^*$ , Sipser talks about sequences of states. Shallit’s A Second Course in Formal Languages and Automata Theory (2008) gives a more succinct and advanced treatment. Hubie Chen’s book finds a middle ground in terms of configurations of finite automata. I find his approach elegant, although some results (notably the closure of regular languages under complementation) become more cumbersome than with the $\delta ^*$ approach. Pleasingly, the author chooses to allow multiple start states for NFAs. Less so, he defines $\epsilon $ -NFAs by an abuse of notation: If x is a word, a is a symbol, and $\epsilon $ is the empty word, then the juxtapositional concatenations $\epsilon x$ and $ax$ are of different types but are treated as the same.

The physical book is attractively constructed, with beautiful and informative illustrations. A bit disorientingly, sections, subsections, and other mysterious headings (such as an unnumbered “Theory” heading on page 44) are in the same font size. The exercises are mixed in with notes, so that one has Note 3.10.4 followed by Exercises 3.10.5–6, followed by Note 3.10.7. Separation would have been preferable.

Chen’s book gives detailed proofs of most results. This certainly has its merits. On the other hand, there can also be merit in giving only an illuminating sketch, thereby challenging instructors (and students) to fill in the gaps or consult the literature and allowing for a wider coverage of topics. Given the density of proof text, I suggest that the margins be larger in the next printing.

The explanation of fixed-parameter tractability (FPT) in Chen’s book is the best I have seen. Such explanations often fall into one of two categories: (i) quite formal, leaving the beginner confused about what the big idea is; (ii) quite informal, giving merely an impression that FPT somehow means that a problem is efficiently solvable once some parameter is fixed. In Chen’s book, the main point, in terms of fixing the degree of a polynomial, is clearly explained. Reading Chen’s explanation feels like a transcript of a conversation at a conference (in a good way).

Before starting this review, I had long wondered whether FPT applies to automatic complexity (Shallit and Wang, Automatic complexity of strings, J. Automata, Languages and Combinatorics , 2001). Chen’s explanation makes it easy to see that it does: Once an automaton is fixed, the dependence on the word is polynomial. For example, the following NFA can process arbitrarily long words.

For other tasks such as computing the optimal score in a protein folding model (Dill K.A., Theory for the folding and stability of globular proteins, Biochemistry , 1985), a similar FPT algorithm is not apparent: A protein monomer folds in an injective way allowing no returns to previous positions. Thus, the following fold applies only to words of length four:

This ability to distinguish potentially NP-hard problems is important given that theoretically intractable problems often seem tractable in practice. I am glad that Chen has brought it to the standard curriculum with his well-crafted textbook.