Perspectives in Mathematical Logic, Springer-Verlag Berlin, Heidelberg etc., 1997, pp. XII+482. ISBN 3-540-57073-X
In 2001 also a cheaper textbook edition was printed.
Comprehensive treatment of the classical decision problem of mathematical logic with particular emphasis on its role in computer science. Contains a state-of-the-art analysis of the natural order of decidable and undecidable cases, including
- the complete classification of the solvable and unsolvable standard cases of the classical decision problem,
- the complexity analysis of the solvable cases,
- a detailed treatment of the reduction method,
- the model-theoretic analysis of the solvable cases.
Many cases are treated for the first time in this book which contains also many proof simplifications, a great number of exercises and an annotated bibliography of over 500 references.
Part I (Ch.1-5) written by E. Boerger, Part II by E. Graedel (Ch.6, 7.1., 7.2, 8) and Y. Gurevich (Ch.7.2), Appendix by C. Allauzen and B. Durand. Contrary to the claim made by Y. Gurevich (in the Bulletin of the European Association for Theoretical Computer Science, No. 107, June 2012), that a survey on the Decision Problem he wrote around 1970 `became the core of the 1997 Springer book "The Classical Decision Problem" ', this survey has not been used at all (and would have been outdated) for writing the book.