When representing real-world knowledge, AI systems must handle defaults, exceptions, and changing environments. If you learn that a creature is a bird, you assume it flies; if you later learn it is a penguin, you must retract that conclusion. Formalisms like John McCarthy’s circumscription and Raymond Reiter’s default logic were designed precisely to handle this kind of nonmonotonic reasoning.
However, these logics present a severe computational challenge. Circumscription relies on minimizing predicate extensions across models—a process that inherently involves second-order logic or complex minimal-model filtering. Default logic requires finding fixed points ("extensions") over potentially infinite or highly combinatorial spaces.
Building specialized reasoning engines for every flavor of nonmonotonic logic is incredibly difficult. To solve this, researchers developed a powerful alternative strategy: compilation. By mathematically mapping high-level nonmonotonic theories into highly optimized, operational frameworks—such as Answer Set Programming (ASP), propositional logic (SAT), or classical description logic—we can leverage decades of engineering in modern solvers to execute complex common-sense reasoning efficiently.
Why Circumscription Maps to Stable Models
The reason circumscription can be compiled into logic programs lies in a shared philosophical foundation: minimization. Circumscription works by selecting classical models where the extensions of certain "abnormality" predicates are as small as possible. Similarly, the stable model semantics underlying ASP uses a form of minimization via the Gelfond-Lifschitz reduction, ensuring that facts are only true if they are minimally forced by the program's rules.
Early researchers recognized this structural alignment. In On the Relation Between Autoepistemic Logic and Circumscription, the authors introduced "MIN theories" to bridge autoepistemic logic and circumscription, explicitly constructing autoepistemic models that mirror the predicate minimization of circumscription. Concurrently, early foundational work in Compiling Circumscriptive Theories into Logic Programs: Preliminary Report demonstrated that specific circumscriptive axioms could be transformed into stratified logic programs using predicate renaming and resolution techniques.
Decades later, this theoretical link was fully operationalized. Heng Zhang et al. proved that circumscription can be embedded directly into stable model semantics without introducing auxiliary predicates. This demonstrated a fundamental compatibility between the two formalisms: the minimization policy of circumscription can be natively expressed by the negation-as-failure and minimality constraints of stable models. This relationship is bidirectional; Fangzhen Lin et al. showed that general logic programs can be mapped back into classical circumscribed formulas by using the "Logic of GK" (Knowledge and Justified Assumptions) as an intermediate step, providing a unified view of both paradigms.
+-----------------------------------+
| Circumscriptive Theory | <- Minimizes predicate extensions
+-----------------------------------+
|
| Compiled via exact semantic mapping
v
+-----------------------------------+
| Stable Model Semantics | <- Minimizes truth via rule justifications
+-----------------------------------+
|
| Executed by
v
+-----------------------------------+
| Modern ASP Solvers |
+-----------------------------------+
Operationalizing Action Theories
This compilation strategy is particularly valuable for classical action formalisms like the Event Calculus and the Situation Calculus. These frameworks use circumscription to solve the notorious frame problem—the challenge of representing what remains unchanged when an action occurs.
Instead of relying on slow, specialized first-order theorem provers to compute these effects, compilation allows us to hand the problem over to high-performance ASP engines:
- The Event Calculus: Tae-Won Kim et al. proved that the circumscriptive Event Calculus can be mapped to stable model semantics for specific classes of canonical formulas. This allowed modern ASP solvers to handle complex planning tasks and reason about indirect effects far more efficiently than older SAT-based methods.
- The Situation Calculus: Joohyung Lee 0002 et al. successfully reformulated classical first-order action theories in the Situation Calculus into logic programs under stable model semantics.
- Scaling Up: To make this practical for real-world optimization and diagnostics, Hai Wan et al. developed linear translations that compile general first-order parallel and prioritized circumscription into stable models. Their resulting solver,
cfo2lp, handles varying constants and priority hierarchies by converting theoretical nonmonotonic logic into concrete logic program rules.
Compiling Default Logic to SAT and Description Logic
Circumscription is not the only nonmonotonic formalism that benefits from compilation. Default logic—which uses rules with explicit justifications (e.g., "if $A$ is true, and it is consistent to believe $B$, then infer $C$")—can also be compiled down to standard operational frameworks.
The intuition here is that default rules act as conditional constraints. If we can analyze the dependencies between these rules, we can unroll them into classical logic. For example, Rachel Ben-Eliyahu et al. developed a polynomial-time mapping that transforms nonmonotonic default theories into standard propositional logic sentences. By using graph-based topological analysis to identify tractable subsets of the theory, they showed that finding a valid default extension can be reduced to a standard satisfiability (SAT) problem.
Alternatively, instead of compiling to propositional clauses, we can compile to standard logic programming execution. Grigoris Antoniou et al. designed a translation method called LogProg. They proved that by restructuring a default theory into a compatible logic program format, standard Prolog-style execution (SLDNF-resolution) is fully sound and complete for identifying the theory's extensions.
This reduction strategy even scales to the Semantic Web, where merging data from multiple open-world sources inevitably introduces contradictions. Rafael Kiesel et al. demonstrated that prioritized default rules can be translated directly into classical description logics. This allows inconsistent, messy datasets to be processed by highly optimized, off-the-shelf description logic reasoners, achieving near-linear performance for moderate-sized datasets without needing a specialized nonmonotonic inference engine.
Key Foundational Work
On the Relation Between Autoepistemic Logic and Circumscription (1989) — contributed 4 concept elements to this direction.
Compiling Circumscriptive Theories into Logic Programs: Preliminary Report (1988) — contributed 3 concept elements to this direction.