Compiling Defeasible Inference: A Dynamic Approach To System Z

Non-monotonic reasoning is essential for drawing plausible conclusions from incomplete information. Many approaches model changing belief states using Ordinal Conditional Functions (OCFs), which assign degrees of surprise to possible worlds. This paper demonstrates how OCFs are ideally suited for the knowledge compilation paradigm, particularly with Binary Decision Diagrams (BDDs). We introduce a compilation pipeline for System Z, a prominent ranking-based semantics, which pre-compiles a conditional knowledge base into a set of materialized theories represented by BDDs. This compilation enables polynomial-time conditional entailment and efficient, incremental updates, avoiding costly re-computation. We further extend this approach using Algebraic Decision Diagrams (ADDs) to directly compile the entire ranking function, facilitating direct and efficient implementation of complex belief revision operations such as Spohn conditioning.