In artificial intelligence and formal logic, we often find ourselves with a proliferation of languages. One framework might excel at representing causal relationships, another at handling default assumptions, and a third at rapid computation via high-performance solvers. To avoid reinventing the wheel for every language, researchers build mathematical bridges—translations that map theories from a source logic into a target logic.
But not all translations are created equal. If a translation requires a holistic, global re-evaluation of the entire knowledge base every time a single new fact is introduced, it becomes computationally useless in dynamic environments. The gold standard for interoperability is modular translation.
The Intuition of Modularity
What does it mean for a translation to be modular? Imagine a knowledge base as a collection of individual rules or sentences. A modular translation operates on a "plug-and-play" or rule-by-rule basis.
Formally, a translation is modular if it satisfies two core properties:
- Locality: You can translate each rule or sentence in isolation, independent of the rest of the theory.
- Incremental Updates: If you add a new fact or rule to your original knowledge base, you do not need to recompute the translation of the existing rules. You simply translate the new piece and append it to the target theory.
This concept underpins many successful bridges in automated reasoning. For instance, Paolo Ferraris demonstrated in A Logic Program Characterization of Causal Theories that causal theories can be translated into logic programs rule-by-rule. This modularity preserves the local structure of the knowledge base, allowing developers to use optimized Answer Set Programming (ASP) solvers to compute models for complex causal theories without global overhead.
Similarly, when translating normal logic programs to propositional logic to leverage powerful SAT solvers, Fangzhen Lin et al. showed in On Tight Logic Programs and Yet Another Translation from Normal Logic Programs to Propositional Logic that a modular approach keeps structural constraints valid even as input facts frequently change.
In probabilistic logic programming, Evgenii Balai et al. achieved a linear-time modular translation between $LP^{MLN}$ and P-log in On the Relationship between P-log and LPMLN, enabling incremental rule additions without re-evaluating the existing model structure. Even in first-order probabilistic inference, Guy Van den Broeck et al. utilized a modular transformation for Skolemization in Skolemization for Weighted First-Order Model Counting, processing specific sentences independently to ensure scalability.
Why Modularity Fails: The Nonmonotonic Hurdle
If modularity is so beneficial, why isn't every translation modular? The obstacle lies in the nature of nonmonotonic reasoning—where drawing a conclusion depends not just on what is explicitly stated, but also on what is absent or minimized.
When rules are interconnected, a local change can have global side effects. This tension becomes explicitly clear when trying to translate between the heavyweights of nonmonotonic logic: Reiter's Default Logic, McCarthy's Circumscription, and Moore's Autoepistemic Logic (AEL).
Consider translating Default Logic into Circumscription (a minimality-based framework). In Results on Translating Defaults to Circumscription, Tomasz Imielinski proved a fundamental impossibility result: normal default rules with prerequisites cannot be modularly translated into circumscription. As elaborated in the companion paper Results, this limitation arises because no static partial order (which circumscription uses to minimize abnormalities) can fully capture the dynamic behavior of default prerequisites without depending on the specific facts at hand. If new facts arrive, the entire order relation and abnormality formulas must be recomputed from scratch.
David W. Etherington echoed this in Relating Default Logic and Circumscription, noting that rule-by-rule mapping is only possible when defaults are stripped of prerequisites and kept extremely simple. To bypass this in specific domains like action formalizations, researchers like G. Neelakantan Kartha et al. had to confine circumscription within localized, nested logical blocks (A Simple Formalization of Actions Using Circumscription) to prevent the complexity of reasoning about change from breaking global manageability.
The Expressive Power of Global Translations
The limits of modularity are even more stark when bridging Default Logic and Autoepistemic Logic. Early on, Kurt Konolige established a bidirectional connection between them in On the Relation Between Default Theories and Autoepistemic Logic by introducing "strongly grounded" extensions, showing they could be treated as two sides of the same coin under certain local translation conditions.
However, when attempting a general, faithful translation from Default Logic into standard Autoepistemic Logic, modularity hits a mathematical wall. In The Power of Beliefs or Translating Default Logic into Standard Autoepistemic Logic, Georg Gottlob proved that a faithful modular translation between these two systems is completely impossible (a finding mirrored in the parallel text The Power of Beliefs or Translating Default Logic).
Why does it fail? Default logic rules dictate how to derive new conclusions based on the inability to derive their negations. Standard AEL, on the other hand, reasons about self-referential beliefs. The holistic interactions between default rules and self-referential beliefs cannot be uncoupled into independent components.
To overcome this, Georg Gottlob introduced a non-modular polynomial-time translation. Instead of mapping rules individually, this approach transforms the entire set of premises into a single, unified logical structure. The trade-off is severe: because the translation is non-modular, any update or new observation forces a complete re-translation of the entire theory. Yet, this impossibility result revealed something profound about the logics themselves: standard AEL is strictly more expressive than Default Logic, proving that explicit beliefs about groundedness add computational and representational power that a purely local, rule-by-rule mapping can never capture.
Key Foundational Work
Results on Translating Defaults to Circumscription (1985) — contributed 5 concept elements to this direction.
Results on Translating Defaults to Circumscription (1985) — contributed 4 concept elements to this direction.
Relating Default Logic and Circumscription (1987) — contributed 1 concept elements to this direction.