The Classical Decision Problem (häftad)
Häftad (Paperback / softback)
Antal sidor
Softcover reprint of the original 1st ed. 1997
Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Gradel, Erich
Bibliographie 3 schwarz-weiße Abbildungen
3 Illustrations, black and white; X, 482 p. 3 illus.
234 x 156 x 25 mm
690 g
Antal komponenter
1 Paperback / softback
The Classical Decision Problem (häftad)

The Classical Decision Problem

Häftad Engelska, 2001-08-01
Skickas inom 3-6 vardagar.
Fri frakt inom Sverige för privatpersoner.
Beställ boken senast tisdag 15 december kl. 15:00 för leverans innan julafton
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.
Visa hela texten

Passar bra ihop

  1. The Classical Decision Problem
  2. +
  3. Architecture Design and Validation Methods

De som köpt den här boken har ofta också köpt Architecture Design and Validation Methods av Egon Boerger (inbunden).

Köp båda 2 för 2498 kr


Har du läst boken? Sätt ditt betyg »

Fler böcker av författarna

Recensioner i media

From the reviews of the first edition: "The authors ... describe their effort as that of 'combining the features of a research monograph and a textbook.' They suggest that the book - or selected chapters of it - might be used for an introductory course on decision problems, undecidability, and the complexity of decision procedures. ... So there is usually a lot to think about in making sense of the author's arguments. This is part of what makes this book so enjoyable." (R. Gregory Taylor, The Review of Modern Logic, Vol. 9 (3-4), 2004) "This is the most comprehensive treatment available in book form of the classical decision problem of mathematical logic and of the role of the classical decision problem in modern computer science. A revealing analysis of the natural order of decidable and undecidable cases is given. ... Many cases are treated here for the first time, and a great number of simple proofs and exercises have been included." (L'Enseignement Mathematique, Vol. 48 (1-2), 2002) "The book is dedicated to a comprehensive presentation of the classical decision problem of first-order logic. ... This book is an essential reference for any researcher in logic, complexity, and artificial intelligence. ... Historical references that are placed at the end of each chapter are very enjoyable and help the reader follow the literature and gain a perspective of the field. ... an excellent reference book for researchers in the field, and for advanced doctoral students in theoretical computer science and logic." (Dan A. Simovici, SIGACT News, Vol. 35 (1), 2004)


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.- 2.1 Undecidability and Conservative Reduction.- 2.1.1 The Church-Turing Theorem and Reduction Classes.- 2.1.2 Trakhtenbrot's Theorem and Conservative Reductions.- 2.1.3 Inseparability and Model Complexity.- 2.2 Logic and Complexity.- 2.2.1 Propositional Satisfiability.- 2.2.2 The Spectrum Problem and Fagin's Theorem.- 2.2.3 Capturing Complexity Classes.- 2.2.4 A Decidable Prefix-Vocabulary Class.- 2.3 The Classifiability Problem.- 2.3.1 The Problem.- 2.3.2 Well Partially Ordered Sets.- 2.3.3 The Well Quasi Ordering of Prefix Sets.- 2.3.4 The Well Quasi Ordering of Arity Sequences.- 2.3.5 The Classifiability of Prefix-Vocabulary Sets.- 2.4 Historical Remarks.- 3. Undecidable Standard Classes for Pure Predicate Logic.- 3.1 The Kahr Class.- 3.1.1 Domino Problems.- 3.1.2 Formalization of Domino Problems by $$[\forall \exists \forall , (0,\omega )]$$-Formulae.- 3.1.3 Graph Interpretation of $$[\forall \exists \forall , (0,\omega )]$$-Formulae.- 3.1.4 The Remaining Cases Without $$\exists *$$.- 3.2 Existential Interpretation for $$[{<!-- -->{\forall }^{3}}\exists *, (0,1)]$$.- 3.3 The Gurevich Class.- 3.3.1 The Proof Strategy.- 3.3.2 Reduction to Diagonal-Freeness.- 3.3.3 Reduction to Shift-Reduced Form.- 3.3.4 Reduction toFi-Elimination Form.- 3.3.5 Elimination of MonadicFi.- 3.3.6 The Kostyrko-Genenz and Suranyi Classes.- 3.4 Historical Remarks.- 4. Undecidable Standard Classes with Functions or Equality.- 4.1 Classes with Functions and Equality.- 4.2 Classes with Functions but Without Equality.- 4.3 Classes with Equality but Without Functions: the Goldfarb Classes 161 4.3.1 Formalization of Natural Numbers in $$[{<!-- -->{\forall }^{3}}\exists *, (\omega ,\omega ),(0)]$$=.- 4.3.2 Using Only One Existential Quantifiers.- 4.3.3 Encoding the Non-Auxiliary Binary Predicates.- 4.3.4 Encoding the Auxiliary Binary Predicates of NUM*.- 4.4 Historical Remarks.- 5. Other Undecidable Cases.- 5.1 Krom and Horn Formulae.- 5.1.1 Krom Prefix Classes Without Functions or Equality.- 5.1.2 Krom Prefix Classes with Functions or Equality.- 5.2 Few Atomic Subformulae.- 5.2.1 Few Function and Equality Free Atoms.- 5.2.2 Few Equalities and Inequalities.- 5.2.3 Horn Clause Programs With One Krom Rule.- 5.3 Undecidable Logics with Two Variables.- 5.3.1 First-Order Logic with the Choice Operator.- 5.3.2 Two-Variable Logic with Cardinality Comparison.- 5.4 Conjunctions of Prefix-Vocabulary Classes.- 5.4.1 Reduction to the Case of Conjunctions.- 5.4.2 Another Classifiability Theorem.- 5.4.3 Some Results and Open Problems.- 5.5 Historical Remarks.- II. Decidable Classes and Their Complexity.- 6. Standard Classes with the Finite Model Property.- 6.1 Techniques for Proving Complexity Results.- 6.1.1 Domino Problems Revisited.- 6.1.2 Succinct Descriptions of Inputs.- 6.2 The Classical Solvable Cases.- 6.2.1 Monadic Formulae.- 6.2.2 The Bernays-Schoenfinkel-Ramsey Class.- 6.2.3 The Goedel-Kalmar-Schutte Class: a Probabilistic Proof.- 6.3 Formulae with One ?.- 6.3.1 A Satisfiability Test for [?*??*, all, all].- 6.3.2 The Ackermann Class.- 6.3.3 The Ackermann Class with Equality.- 6.4 Standard Classes of Modest Complexity.- 6.4.1 The Relational Classes in P, NP and Co-NP.- 6.4.2 Fragments of the Theory of One Unary Function.- 6.4.3 Other Functional Classes.- 6.5 Finite Model Property vs. Infinity Axioms.- 6.6 Historical Remarks.- 7. Monadic Theories and Decidable Standard Classes with Infinity Axioms.- 7.1 Automata, Games and Decidability of Monadic Theories.- 7.1.1 Monadic Theories.- 7.1.2 Automata on Infinite Words and the Monadic Theory of One Successor.- 7.1.3 Tree Automata, Rabin's Theorem and Forgetful De terminacy.- 7.1.4 The Forgetful Determinacy Theorem for Graph Games.- 7.2 The Monadic Second-Order Theory of One Unary Function.