## The Classical Decision ProblemThis book is addressed to all those - logicians, computer scientists, mathe maticians, philosophers of science as well as the students in all these disci plines - who may be interested in the development and current status of one of the major themes of mathematical logic in the twentieth century, namely the classical decision problem known also as Hilbert's Entscheidungsproblem. The text provides a comprehensive modern treatment of the subject, includ ing complexity theoretic analysis. We have made an effort to combine the features of a research monograph and a textbook. Only the basic knowledge of the language of first-order logic is required for understanding of the main parts of the book, and we use standard terminology. The chapters are written in such a way that various combinations of them can be used for introductory or advanced courses on undecidability, decidability and complexity of logical decision problems. This explains a few intended redundancies and repetitions in some of the chapters. The annotated bibliography, the historical remarks at the end of the chap ters and the index allow the reader to use the text also for quick reference purposes. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

II | 1 |

III | 5 |

IV | 8 |

V | 17 |

VI | 18 |

VII | 33 |

VIII | 38 |

IX | 43 |

LVIII | 229 |

LIX | 233 |

LX | 239 |

LXI | 242 |

LXII | 247 |

LXIII | 249 |

LXV | 257 |

LXVI | 261 |

X | 44 |

XI | 48 |

XII | 57 |

XIII | 66 |

XIV | 70 |

XV | 71 |

XVI | 74 |

XVII | 77 |

XVIII | 78 |

XIX | 81 |

XX | 85 |

XXI | 87 |

XXIII | 91 |

XXIV | 98 |

XXV | 109 |

XXVI | 115 |

XXVII | 124 |

XXIX | 130 |

XXX | 131 |

XXXI | 135 |

XXXII | 137 |

XXXIII | 143 |

XXXIV | 146 |

XXXV | 149 |

XXXVI | 150 |

XXXVII | 159 |

XXXVIII | 161 |

XXXIX | 163 |

XL | 171 |

XLI | 178 |

XLII | 186 |

XLIII | 188 |

XLIV | 189 |

XLV | 190 |

XLVII | 198 |

XLVIII | 202 |

XLIX | 205 |

L | 210 |

LI | 216 |

LII | 219 |

LIII | 220 |

LIV | 223 |

LV | 227 |

LVI | 228 |

LXVII | 270 |

LXVIII | 271 |

LXIX | 281 |

LXX | 285 |

LXXI | 290 |

LXXIII | 295 |

LXXIV | 304 |

LXXV | 306 |

LXXVI | 310 |

LXXVII | 315 |

LXXVIII | 316 |

LXXIX | 318 |

LXXX | 323 |

LXXXI | 329 |

LXXXII | 337 |

LXXXIII | 338 |

LXXXIV | 341 |

LXXXV | 345 |

LXXXVII | 348 |

LXXXVIII | 351 |

LXXXIX | 354 |

XC | 357 |

XCI | 359 |

XCII | 360 |

XCIII | 365 |

XCIV | 369 |

XCV | 370 |

XCVI | 374 |

XCVII | 377 |

XCVIII | 382 |

XCIX | 387 |

C | 388 |

CI | 390 |

CIII | 393 |

CIV | 400 |

CV | 407 |

CVII | 408 |

CVIII | 410 |

CIX | 414 |

CX | 419 |

CXI | 421 |

477 | |

### Other editions - View all

### Common terms and phrases

1-satisfies algorithm arbitrary arity atomic formulae automaton Biichi binary predicate bound classes of formulae clause closure complexity computation configuration conjunction conservative reduction class constant construct contains decidable decision problem defined definition domain domino problem elements encoding Entscheidungsproblem equality equivalent Exercise existential exists Fagin's Theorem finite model property finite satisfiability first-order logic formalized formula ip function symbols G(ip given Godel graph Gurevich halting problems Herbrand Horn formulae implies infinite infinity axioms input intended interpretation Krom KROM n HORN Lemma length Math monadic predicate monadic theory natural numbers node NP-complete obtained pair polynomial predicate logic predicate symbols prefix classes prefix-vocabulary classes prenex prenex normal form proof propositional prove quantifier-free quasi ordered recursive reduction formulae reduction property restrict result satisfiability problem Sect sentence Skolem normal form Theorem Turing machine TV-successor unary function undecidable unique universal quantifiers variables vertex vocabulary