Tractable Reasoning in Artificial Intelligence

✍ Scribed by Marco Cadoli (auth.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 1995
• Tongue: English
• Leaves: 255
• Series: Lecture Notes in Computer Science 941 : Lecture Notes in Artificial Intelligence
• Edition: 1
• Category: Library

✦ Synopsis

Logic is one of the most popular approaches to artificial intelligence. A potential obstacle to the use of logic is its high computational complexity, as logical inference is an extraordinarily powerful computational device.
This book is concerned with computational aspects of the logical approach to AI. The focus is on two strategies for achieving computational tractability in knowledge representation and reasoning by language restriction and approximation. Several formalisms for knowledge representation are taken into account; among the computational problems studied are checking satisfiability and entailment of formulae, finding a model, and approximating and compiling a logical for

✦ Table of Contents

Introduction....Pages 1-26
Language restriction: Complexity of minimal reasoning....Pages 27-65
Approximation of a logical theory....Pages 67-121
Using complexity results for evaluating approximation techniques....Pages 123-132
Conclusion....Pages 133-139

✦ Subjects

Artificial Intelligence (incl. Robotics); Mathematical Logic and Formal Languages; Computation by Abstract Devices