Incorporating Nonmonotonic Reasoning in Horn Clause Theories

James P. Delgrande

An approach for introducing default reasoning into first-order Horn clause theories is described. A default theory is expressed as a set of strict implications where the ai and b are function-free literals. A partial order of sets of formulae is obtained from these sets of (strict and default) implications. Default reasoning is defined with respect to this ordering and a set of contingent ground facts. Crucially, only strict implications appear in this structure. Consequently the complexity of default reasoning is that of classical reasoning, together with an attendant overhead for manipulating the structure. This overhead is O(n2), where n is the number of original formulae. Hence for defaults in propositional Horn clause form time complexity is O(n2m) where m is the total length of the original formulae. The approach is sound, in that default reasoning in this structure is proven to conform to that of an extant system for default reasoning.

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.