Tractable Reasoning in First-Order Knowledge Bases with Disjunctive Information

Yongmei Liu, Hector J. Levesque

This work proposes a new methodology for establishing the tractability of a reasoning service that deals with expressive first-order knowledge bases. It consists of defining a logic that is weaker than classical logic and that has two properties: first, the entailment problem can be reduced to the model checking problem for a small number of characteristic models; and second, the model checking problem itself is tractable for formulas with a bounded number of variables. We show this methodology in action for the reasoning service previously proposed by Liu, Lakemeyer and Levesque for dealing with disjunctive information. They show that their reasoning is tractable in the propositional case and decidable in the first-order case. Here we apply the methodology and prove that the reasoning is also tractable in the first-order case if the knowledge base and the query both use a bounded number of variables.

Content Area: 10. Knowledge Representation & Reasoning

Subjects: 11. Knowledge Representation; 3. Automated Reasoning

Submitted: May 8, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.