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 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.

Zielgruppe

Research

Autoren/Hrsg.

Börger, Egon

Grädel, Erich

Gurevich, Yuri

Fachgebiete

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

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.