The Resolution Calculus

Alexander Leitsch (Autor)

Buch | Softcover

VIII, 300 Seiten

2011 | 1. Softcover reprint of the original 1st ed. 1997
Springer Berlin (Verlag)
978-3-642-64473-3 (ISBN)

Artikel merken

The History of the Book In August 1992 the author had the opportunity to give a course on resolution theorem proving at the Summer School for Logic, Language, and Information in Essex. The challenge of this course (a total of five two-hour lectures) con sisted in the selection of the topics to be presented. Clearly the first selection has already been made by calling the course "resolution theorem proving" instead of "automated deduction" . In the latter discipline a remarkable body of knowledge has been created during the last 35 years, which hardly can be presented exhaustively, deeply and uniformly at the same time. In this situ ation one has to make a choice between a survey and a detailed presentation with a more limited scope. The author decided for the second alternative, but does not suggest that the other is less valuable. Today resolution is only one among several calculi in computational logic and automated reasoning. How ever, this does not imply that resolution is no longer up to date or its potential exhausted. Indeed the loss of the "monopoly" is compensated by new appli cations and new points of view. It was the purpose of the course mentioned above to present such new developments of resolution theory. Thus besides the traditional topics of completeness of refinements and redundancy, aspects of termination (resolution decision procedures) and of complexity are treated on an equal basis.

The Basis of the Resolution Calculus.- First-Order Logic.- Transformation to Clause Form.- Term Models and Herbrand's Theorem.- Decision Methods for Sets of Ground Clauses.- The Propositional Resolution Principle.- Substitution and Unification.- The General Resolution Principle.- A Comparison of Different Resolution Concepts.- 3. Refinements of Resolution.- A Formal Concept of Refinement.- Normalization of Clauses.- Refinements Based on Atom Orderings.- Lock Resolution.- Linear Refinements.- Hyperresolution.- Refinements: A Short Overview.- 4. Redundancy and Deletion.- The Problem of Proof Search.- The Subsumption Principle.- Subsumption Algorithms.- The Elimination of Tautologies.- Clause Implication.- 5. Resolution as Decision Procedure.- The Decision Problem.- A-Ordering Refinements as Decision Procedures.- Hyperresolution as Decision Procedure.- Hyperresolution and Automated Model Building.- 6. On the Complexity of Resolution.- Herbrand Complexity and Proof Length.- Extension and the Use of Lemmas.- Structural Normalization.- Functional Extension.

Erscheint lt. Verlag	28.9.2011
Reihe/Serie	Texts in Theoretical Computer Science. An EATCS Series
Zusatzinfo	VIII, 300 p.
Verlagsort	Berlin
Sprache	englisch
Maße	155 x 235 mm
Gewicht	480 g
Themenwelt	Informatik ► Software Entwicklung ► User Interfaces (HCI)
	Mathematik / Informatik ► Informatik ► Theorie / Studium
	Mathematik / Informatik ► Mathematik ► Analysis
	Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
	Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
Schlagworte	algorithms • Calculus • Complexity • Decision • Decision Procederes • Deduction • Resolution
ISBN-10	3-642-64473-2 / 3642644732
ISBN-13	978-3-642-64473-3 / 9783642644733
Zustand	Neuware