Automata and Computability (Undergraduate Texts in Computer Science)

This course mainly deals with notions and models of computation, a previous reviewer noted that it doesn't include NP-completeness. There is a reason for this, because at Cornell University, this course is the first in a sequence, the second of which covers algorithms and complexity issues. That course covers NP-completeness and all the basic algorithm techniques.

For those readers in a similar situation as the previous reviewer, it's difficult to find a more simple introduction to computer theory. I thought DFAs were the easiest part of the book/course, DFAs are the simplest models of computation, you can think of counting fingers as a form of DFA. I'm confident that anyone that can count will be able to understand the explanations of DFA in this book.

The material is very well chosen, and the writing stile is directly thought with students in mind. Kozen has a pluri-annual experience in teaching at Cornell University, and it seems he has developed an effective style of communication with students, that's perfectly reflected in his books.

Some important topics are present in this book and not in both Sipser and Hopcroft-Ullman. If you need (as I did) to learn about Myhill-Nerode Relations and Theorem, this book features the best account I've seen (the other, much shorter, reference can be found in the first editon of Hopcroft-Ullman but not in the second one !).
A nice shot of the Lambda-calculus is also featured, and this too lacks in the other two books.

The organization in lectures is a very good idea when studying. Lectures are carefully cut and self-contained, so that you can organize your time using this unit, and wherever you choose to stop a study session, you always stop at correct boundary of a topics.

As a further (and important) note, the notation used is very clear and elegant. As soon as you get used with it (very soon since its clarity) it becomes very stimulating. Don't understimate this value, since many books feature too-hard-to-follow notations, or no notation at all. Both of which cases are to be avoided, INMH.

I have used other books for my course, starting from both the editions of the Hopcroft and Ullman, but one way or the other I found myself always with this book (and Sipser's) in my hands.

The greatest strengths of the book are (1) its exceptionally clear writing. (2) Excellent collection of problems (with hints and solutions to a subset of these).

This book follows the "standard" approach to the introduction of notion of effective computability in present day CS curriculum, namely the Turing Machine and formal grammars approach. There is however, thankfully, some introductory material on other formalisms like lamda calculus etc.

One topic whose omission is striking is NP Completeness. It is kind of dissappointing to find a treatment of that subject missing from this wonderful text. I really find it hard to believe that Kozen does not deal with this topic in his under grad class. Considering he has a chapter on something as profound and complicated as Godel's Incompleteness Theorem (and its proof), the omission of NPC is inexplicable. (which is why I give it only 4 stars). Personally, I would have liked to see a good discussion of the Post's Correspondence problem too.

In our class, we kept going back to Sipser's book on this subject, which is an outstanding book in its own right - having the best qualities of Kozen's book and The Book by Hofcroft & Ullman, for more advanced material.

All in all, I think this is a great book for its intended audience.