The Classical Decision Problem

Softcover Nachdruck of the original 1. Auflage 1997
ISBN: 978-3-540-42324-9
Verlag: Springer

Buch, Englisch, 482 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 1520 g

Reihe: Universitext

This book offers a comprehensive treatment of the classical decision problem of mathematical logic and of the role of the classical decision problem in modern computer science. The text presents a revealing analysis of the natural order of decidable and undecidable cases and includes a number of simple proofs and exercises.

Zielgruppe

Research

Autoren/Hrsg.

Börger, Egon

Grädel, Erich

Gurevich, Yuri

Fachgebiete

• Wirtschaftswissenschaften Volkswirtschaftslehre Volkswirtschaftslehre Allgemein Ökonometrie
• Mathematik | Informatik Mathematik Mathematik Allgemein Grundlagen der Mathematik
• Mathematik | Informatik EDV | Informatik Informatik Logik, formale Sprachen, Automaten
• Technische Wissenschaften Technik Allgemein Computeranwendungen in der Technik
• Mathematik | Informatik Mathematik Mathematik Allgemein Mathematische Logik
• Wirtschaftswissenschaften Betriebswirtschaft Wirtschaftsmathematik und -statistik
• Mathematik | Informatik EDV | Informatik Angewandte Informatik Computeranwendungen in Wissenschaft & Technologie

Inhaltsverzeichnis

1. Introduction: The Classical Decision Problem.- 1.1 The Original Problem.- 1.2 The Transformation of the Classical Decision Problem.- 1.3 What Is and What Isn’t in this Book.- I. Undecidable Classes.- 2. Reductions.- 3. Undecidable Standard Classes for Pure Predicate Logic.- 4. Undecidable Standard Classes with Functions or Equality.- 5. Other Undecidable Cases.- II. Decidable Classes and Their Complexity.- 6. Standard Classes with the Finite Model Property.- 7. Monadic Theories and Decidable Standard Classes with Infinity Axioms.- 8. Other Decidable Cases.- A. Appendix: Tiling Problems.- A.1 Introduction.- A.2 The Origin Constrained Domino Problem.- A.3 Robinson’s Aperiodic Tile Set.- A.4 The Unconstrained Domino Problem.- A.5 The Periodic Problem and the Inseparability Result.- Annotated Bibliography.