Automata, Formal Languages, and Complexity
Since God created computer science, the standard textbook in this
area has been Hopcroft and Ullman. For elementary material, many
people find Lewis and Papadimitriou more readable. For advanced
material, consult the new book by Papadimitriou: it is more readable
and more up to date than Hopcroft and Ullman.
- Hopcroft, John E. and Jeffrey D. Ullman (1979)
Introduction to Automata Theory, Languages, and Computation,
Addison-Wesley, Reading MA.
- Lewis, Harry R. and Christos H. Papadimitriou (1981)
Elements of the theory of computation, Prentice-Hall, Englewood Cliffs
- Papadimitriou, Christos H. (1994)
Computational complexity, Addison-Wesley, Reading MA.
If you understand the ideas involved in NP-completeness and need
to track down a specific result, the book by Garey and Johnson is
- Garey, Michael R. and David S. Johnson (1979)
Computers and intractability : a guide to the theory of NP-
completeness, W. H. Freeman, New York