Tractable reasoning in incomplete first-order knowledge bases
By: by Yongmei Liu.
Published: 2006
Language: eng
Number of pages: 180
ISBN-13: 9780494157602
Description: In order to specify a limited reasoning service for proper+ KBs, we propose a new logic of limited belief called the subjective logic   SL .   SL  supports unit resolution, but only does case analysis in a limited way. We give a sound and complete axiomatization for propositional   SL . Reasoning based on   SL  is classically sound and is also classically complete in some simple cases. We show that   SL -based reasoning with proper+ KBs is decidable in general, and tractable when both the KB and the query use a bounded number of variables.This thesis proposes a general methodology to establish tractable (by "tractable" we mean "solvable in polynomial time") limited reasoning services for incomplete first-order knowledge bases (KBs). It consists of defining a logic that is weaker than classical logic and has two properties: first, the entailment problem can be reduced to the model checking problem for a characteristic model; and second, the model checking problem is tractable for formulas with a bounded number of variables. We show this methodology in action for two forms of incomplete first-order KBs proposed by Levesque and Lakemeyer. One is called proper KBs, and is used for open-world reasoning. The other is called proper+ KBs, and is used for reasoning with disjunctive information.Levesque has proposed a reasoning scheme called V for proper KBs that is classically sound and is also classically complete when the query is in a certain normal form called   NF . We prove that V is tractable for queries with a bounded number of variables. We also settle the open problems concerning the expressiveness and succinctness of   NF . Then we extend V to reasoning in dynamic systems, and propose a tractable, sound, and sometimes complete solution to the projection problem, that is, determining whether a formula holds after a sequence of actions is performed.
Notes: Source: Dissertation Abstracts International, Volume: 67-06, Section: B, page: 3235.

Advisor: H.J. Levesque.

Thesis (Ph.D.)--University of Toronto, 2006.

Includes bibliographic references.

Electronic version licensed for access by U. of T. users.