Compiling Prioritized Default Rules into Ordinary Logic Programs

Prioritized default rules offer a conveniently higher level of specification that facilitates revision and modularity. They handle conflicts, including arising during updating of rule sets, using partially-ordered prioritization information that is naturally available based on relative specificity, recency, and authority. Despite having received much study, however, they have had as yet little impact on practical rule-based systems and software engineering generally, and had very few deployed serious applications.

We give a new approach to the semantics and implementation of prioritized default rules: to compile them into ordinary logic programs (LPs). (By "logic program" and "prioritized default rules") we mean in the sense of declarative knowledge representation (KR), including model-theoretic entailment and forward as well as backward inferencing. In particular, by "logic program", we do not simply mean prolog.)

We use the compilation approach both to expressively generalize and to implement courteous LPs, a previous formalism featuring classical negation and prioritized conflict handling. WE show that we preserve courteous LPs attractive reasoning behaviors and polynomial-time computations cost. Our expressive generalization enables recursion, and also reasoning about the prioritization. Our implementation enable courteous LPs functionality to be added modularly to ordinary LP rule engines, via a pre-processor, with moderate, tractable computational overhead.

More generally, we show that the compilation approach is applicable to implementing, and to defining, numerous variants of prioritized default rule KR's beyond the particular courteous LP variant given here.

This takes a long step towards actual deployment of prioritized default rules in commercially fielded technology and applications.