Tractable Deduction in Knowledge Representation Systems.
Mukesh Dalal · 1992
A widely-used way to deal with the intractability of various deduction problems is based on identifying their tractable cases. Current techniques for this are highly problem specific. We present a new technique that obtains powerful tractability results for many different problems. Our technique is based on a notion of partial consistency for logical theories. Any set of theories for which a fixed level of partial consistency can guarantee logical consistency provides a tractable class of deduction problems. We apply this technique to obtain tractability results in the areas of constraint satisfaction problems, databases with incomplete information and disjunctive logic programming. 1 INTRODUCTION It is well known that deductive reasoning in a knowledge representation system becomes more difficult as the representation language becomes more expressive [ Levesque and Brachman, 1985 ] . Deductive reasoning (or deduction) is intractable 1 even for the very weak representation language ...