The Classical Decision Problem

by Egon Börger, Erich Grädel and Yuri Gurevich

Springer 1997 .     Second printing 2001.

From the review by Maarten Marx in Journal of Logic, Language and Information 8:4 (1999), 478-481:

"This book is about --- as its title suggests --- the classical decision problem, also known as Hilbert's Entscheidungsproblem. The preface promises a comprehensive modern treatment of the subject; indeed it does, in a very thorough but still, I think, to most of the intended audience (logicians, computer scientists, mathematicians and philosophers of science) rather accessible manner. The book contains an enormous wealth of techniques, tricks and methods for showing decidability or undecidability of logics, and, in the decidable cases, also methods to establish the exact complexity of the decision algorithms. I guess that not a lot of people would want to read it in one go. Browsing through it might be a dangerous experience though: on several occasions I was, without realising it, drawn deeply into it and the hours had flown by.
For everyone with an interest in decidability or complexity questions related to logic this book is a valuable reference which you will always want to have within reach. As a guide to the literature in the field the book is highly useful. Each chapter ends with a pleasantly written section containing historical remarks (having the additional advantage of not cluttering up the places where real work is to be done). The bibliography is an outstanding achievement. In more than 50 pages, 549 annotated references are given. The annotations not only contain a short abstract of the work, they also often make connections with other works or with the text itself."