Transforming Prioritized Defaults and Specificity into Parallel Defaults
  We show how to transform any set of prioritized propositional defaults into
an equivalent set of parallel (i.e., unprioritized) defaults, in
circumscription. We give an algorithm to implement the transform. We show how
to use the transform algorithm as a generator of a whole family of inferencing
algorithms for circumscription. The method is to employ the transform algorithm
as a front end to any inferencing algorithm, e.g., one of the previously
available, that handles the parallel (empty) case of prioritization. Our
algorithms provide not just coverage of a new expressive class, but also
alternatives to previous algorithms for implementing the previously covered
class (?layered?) of prioritization. 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.
