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.

Last update:

Up to Benjamin Grosof's Papers page

Up to Benjamin Grosof home page

**[
IBM home page |
Order |
Search |
Contact IBM |
Help |
(C) |
(TM)
]
**