In particular, we give a new query-answering algorithm for prioritized cirumscription which is sound and complete for the full expressive class of unrestricted finite prioritization partial orders, for propositional defaults (or minimized predicates). By contrast, previous algorithms required that the prioritization partial order be layered, i.e., structured similar to the system of rank in the military.
Our algorithm enables, for the first time, the implementation of the most useful class of prioritization: non-layered prioritization partial orders. Default inheritance, for example, typically requires non-layered prioritization to represent specificity adequately. Our algorithm enables not only the implementation of default inheritance (and specificity) within prioritized circumscription, but also the extension and combination of default inheritance with other kinds of prioritized default reasoning, e.g.: with stratified logic programs with negation-as-failure. Such logic programs are previously known to be representable equivalently as layered-priority predicate circumscriptions.
Worst-case, the transform increases the number of defaults exponentially. We discuss how inferencing is practically implementable nevertheless in two kinds of situations: general expressiveness but small numbers of defaults, or expressive special cases with larger numbers of defaults. One such expressive special case is non-top-heaviness of the prioritization partial order.
In addition to its direct implementation, the transform can also be exploited analytically to generate special case algorithms, e.g., a tractable transform for a class within default inheritance (detailed in another, forthcoming paper).
We discuss other aspects of the significance of the fundamental result. One can view the transform as reducing n degrees of partially ordered belief confidence to just 2 degrees of confidence: for-sure and (unprioritized) default. Ordinary, parallel default reasoning, e.g., in parallel circumscription or Poole's Theorist, can be viewed in these terms as reducing 2 degrees of confidence to just 1 degree of confidence: that of the non-monotonic theory's conclusions. The expressive reduction's computational complexity suggests that prioritization is valuable for its expressive conciseness, just as defaults are for theirs.
For Reiter's Default Logic and Poole's Theorist, the transform implies
how to extend those formalisms so as to equip them with a concept of
prioritization that is exactly equivalent to that in circumscription.
This provides an interesting alternative to Brewka's approach to
equipping them with prioritization-type precedence.
IBM home page |
Contact IBM |
Last update: 1-8-98
Up to Benjamin Grosof's Papers page
Up to Benjamin Grosof home page
[ IBM Research home page ]
[ IBM home page | Order | Search | Contact IBM | Help | (C) | (TM) ]