Overview

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. The complete classification of the solvable and unsolvable standard cases of the classical decision problem will be of particular interest to the reader. The classification comes complete with the complexity analysis of the solvable cases, with the comprehensive treatment of the reduction method, and with the model-theoretical analysis of solvable cases. Many cases are treated here for the first time, and a great number of simple proofs and exercises have been included. The results and methods of the book are extensively used in logic, computer science and artificial intelligence.

Full Product Details

Author:   Egon Börger ,  Erich Grädel ,  Yuri Gurevich
Publisher:   Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
Imprint:   Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Edition:   Softcover reprint of the original 1st ed. 1997
Dimensions:   Width: 15.50cm , Height: 2.50cm , Length: 23.50cm
Weight:   1.520kg
ISBN:  

9783540423249

ISBN 10:   3540423249
Pages:   482
Publication Date:   28 August 2001
Audience:   College/higher education ,  Undergraduate ,  Postgraduate, Research & Scholarly
Format:   Paperback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.

Table of Contents

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.

Reviews

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)

From the reviews of the first edition: <p> The authors a ] describe their effort as that of a ~combining the features of a research monograph and a textbook.a (TM) 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. a ] So there is usually a lot to think about in making sense of the authora (TM)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) <p> 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. (La (TM)Enseignement Mathematique, Vol. 48 (1-2), 2002) <p> The book is dedicated to a comprehensive presentation of the classical decision problem of first-order logic. a ] This book is an essential reference for any researcher in logic, complexity, and artificial intelligence. a ] 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. a ] 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)

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions