Many logics describe how a reasoner draws tentative conclusions it may later retract. Default logic, autoepistemic logic, causal theories and logic programs are examples, and they are called nonmonotonic because adding information can remove conclusions. To use them, practitioners usually translate a theory into the input language of a fast solver such as an Answer Set Programming (ASP) engine. The most useful translations are modular: each rule is translated on its own, so adding a rule only appends its translation and never forces recompiling the rest. Two classic results say modularity is impossible for default logic in important cases. Defaults with prerequisites cannot be translated rule-by-rule into circumscription, and no faithful modular translation exists into standard autoepistemic logic. The only working compiler for a logic that unifies all of these, Lin and Shoham's logic of Grounded Knowledge, is explicitly non-modular.
This note proposes that the impossibility results come from the targets, not the sources. Circumscription and standard autoepistemic logic have no place to record the difference between "this was derived", "this is safely assumed" and "this has not been rejected". Recent six-valued semantics for non-flat assumption-based argumentation keep exactly those three facts as separate coordinates. In that argumentation setting, rules may conclude assumptions, and assumptions are defeated by deriving their designated opposite. We will build and test a two-stage pipeline. The first stage is a rule-local translation from default logic, logic programs, causal theories and autoepistemic logic into non-flat assumption-based argumentation. The second stage compiles that argumentation into ASP in a way that is itself rule-local. We will also establish where locality still fails.
Core Claim
Imielinski's barrier in Results on Translating Defaults to Circumscription is the "dynamic gatekeeper". A prerequisite must be derived before a default fires, and a fixed minimization order over models cannot express that. Etherington confirms the same boundary in Relating Default Logic and Circumscription, and Gottlob proves the autoepistemic analogue in The Power of Beliefs or Translating Default Logic into Standard Autoepistemic Logic.
In the SIX labeling of Semantics for Non-Flat Assumption-Based Argumentation, Revisited, every assumption carries three binary coordinates: inferred, defended and unrejected. The "inferred" coordinate is exactly a derivability record. Our claim has two parts.
The first part is that a translation can map each source rule to a bounded set of argumentation rules plus fixed, theory-independent clauses, and still preserve the intended conclusions. This holds for normal and general defaults, stable logic programs, and Bochman's causal production rules, which his paper shows are equivalent to attacks on sets of propositions. It also holds, we conjecture, for the fragment of autoepistemic logic whose belief atoms appear only in rule bodies and heads.
The second part is a concrete prediction about which sources need non-flat rules. Default logic, logic programs and causal theories should land in flat argumentation, where no rule concludes an assumption. Autoepistemic introspection derives belief atoms, which act as assumptions. It should therefore force non-flat rules, and the six-valued semantics earns its cost exactly there. If flat argumentation turns out to suffice everywhere, the second half of the claim is wrong and the project reduces to a cleaner engineering result.
Relation to Prior Work
Three works motivate the gap.
- Implementing Default and Autoepistemic Logics via the Logic of GK compiles pure Grounded Knowledge formulas into disjunctive ASP with the
gk2dlptool. Its global witness formulas and whole-theory minimization make it non-modular by the authors' own account, and its solving time scales exponentially on their fair-division benchmark. - Learning Brave Assumption-Based Argumentation Frameworks via ASP encodes assumption-based argumentation in ASP, but only for flat frameworks and only for static theories.
- Heyninck and Arieli supply the six-valued semantics that makes non-flat frameworks well behaved. They guarantee a unique grounded labeling, which is polynomial for Horn rules, but they give no solver encoding.
Two works supply methods we reuse.
- A Logic Program Characterization of Causal Theories shows that a rule-by-rule translation into ASP is possible for causal theories. Its techniques are auxiliary-atom clausification and prepending double negation (
not not) to rule bodies, and we borrow both for the second stage. - On Tight Logic Programs and Yet Another Translation from Normal Logic Programs to Propositional Logic shows that the loop structure of an encoding decides solver speed. It supplies the analysis of strongly connected components that we apply to our own output.
Propositional Argumentation and Causal Reasoning establishes, proof-theoretically, that argumentation over sets of propositions subsumes defaults, stable programs and causal rules. It builds no pipeline and makes no claim about incrementality; we turn that subsumption into a compiler and test whether it is local.
Two works constrain the design.
- On Structural Properties of Argumentation Frameworks: Lessons from ICCMA found that about 23% of ICCMA 2017 frameworks went unsolved by every participating solver within 600 seconds. It also found that layered component structure drives failure. For these reasons we avoid materializing abstract argument graphs.
- ABA+: Assumption-Based Argumentation with Preferences shows that preferences change the attack relation. We leave preferences out of scope, because reversed attacks may break locality.
Research Program
Theory. The first theoretical task is to define modularity precisely for a two-stage pipeline. A translation counts as modular if the output for a theory T is the union of a fixed layer independent of T and the per-rule images of T's rules, and if adding a rule adds only that rule's image. Under this definition a pure meta-interpreter is trivially modular. The substantive requirements are therefore two:
- the per-rule images must be faithful, meaning extensions correspond under the stated semantics;
- the fixed layer must be small and loop-benign.
The second theoretical task is to prove faithfulness for defaults, stable programs and causal theories under stable semantics, where known correspondences suggest this is achievable. The third is to attempt the autoepistemic fragment under a stable-style SIX labeling.
That third step is genuinely open. Heyninck and Arieli settle only grounded semantics, and grounded labelings give only skeptical conclusions, which differ from autoepistemic expansions. We will define a candidate stable labeling in SIX and check it against brute-force enumeration of expansions on all small theories. If it diverges, we will characterize the divergence rather than paper over it. We also expect to prove a negative result: Grounded Knowledge's minimization over the knowledge operator does not admit a local image. That would mark exactly where gk2dlp's global structure is necessary.
System. The second stage compiles the three SIX coordinates into ASP predicates. Each argumentation rule contributes local clauses for the inferred, defended and unrejected coordinates, following Ferraris's double-negation pattern. Contraries contribute local attack clauses. The fixed layer defines the six labels and the chosen semantics. We run it on Clingo, which the argumentation-learning paper uses, and handle updates by incrementally adding program parts to a running solver instead of restarting.
Baselines
Global recompilation with the unifying compiler. The strongest existing competitor for the unified logics is gk2dlp with the claspD-2 back end from Ji and Strass. It is the only system in the file that handles default and autoepistemic logic together. It is also exactly the non-modular design we claim to improve on, so it is the natural target.
We will run it on the same theories with the same update streams, recompiling after each update, on identical hardware with the same time limit. Ji and Strass report only that solving time "scales exponentially with the size of the default theory" on fair division. The file contains no numeric value for this: no reported result found on Lacuna for gk2dlp runtimes. We will therefore regenerate their curve ourselves. Beating it means lower cumulative latency over an update stream, with solve-time curves no worse on single-shot instances.
Recompile from scratch with our own translation. This is the do-nothing reference point for modularity. It uses the same encoding, but the solver restarts after every update. It isolates how much of any gain comes from locality itself rather than from a better encoding.
Direct native encodings of individual logics. For stable logic programs, the relevant comparison is Lin and Zhao's work. There, on instance nv60a540, the SAT-based ASSAT solver dropped from 3664.8 seconds with the old encoding to 5.6 seconds with the inherently tight encoding. The same paper also reports the new encoding exceeding the two-hour limit on the hard instances 2xp and 4xp. For causal theories, the comparison is Ferraris's translation.
We will run these baselines on the Hamiltonian-circuit families nvXaY, 2xp and 4xp, and on causal action domains. A detour through argumentation should not be dramatically slower than a logic's own best encoding. Matching it within a small constant factor counts as success, since our advantage lies in coverage and incrementality.
Flat-only ablation. This drops non-flat rules and the six-valued fixed layer, and uses a three-valued encoding in the style of the argumentation-learning paper. That flat pipeline reports 16.32 seconds on breast-w, with more than 6,000 background rules, where ILASP timed out at 15 minutes. The ablation isolates our key ingredient. It should match the full system on default logic, logic programs and causal theories. It should fail to be faithful on autoepistemic theories with introspection, and if it does not fail there, our second claim is refuted.
Why not just…?
Why not just recompile globally, since polynomial translations already exist? This is the most serious threat. If compilation is cheap relative to solving, recompilation costs little, and the only benefit of locality is that the solver keeps what it has learned across updates. We will report compile time and solve time separately under both regimes. If incremental solving yields no reduction in cumulative latency on update streams, we will say that modularity's value is conceptual and narrow the claim to coverage and faithfulness. Gottlob's grounding formula being quadratic and needing full rebuilding suggests the gap will grow with theory size, but that is a hypothesis to measure, not a given.
Why not just compile everything to abstract Dung frameworks? Dung's On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning and Logic Programming shows the unification works semantically. Building arguments explicitly is not local, however: one new rule can create many new arguments and attacks. The ICCMA analysis also ties layered structure to near-total failure; for instance, SemBuster instances went unsolved 93.75% of the time. We will test this directly on the fair-division and UCI-derived theories. We will count the arguments generated per added rule and compare runtime against our structured encoding.
Why not just use a generic meta-interpreter that reads rules as facts? It is modular for free, and we treat it as the limiting case of our design. The question is whether it pays for its generality. We will compare it against our specialized per-rule clauses, which ground more tightly, on identical theories. If the meta-interpreter is equally fast, we will adopt it and say so. The theoretical contribution, meaning which per-rule images into argumentation are faithful, remains either way.
Why not just stay flat? The flat-only ablation answers this. For default logic and logic programs we expect flat argumentation to suffice. The non-flat machinery is justified only if introspective autoepistemic theories demonstrably need it.
Proposed Experiments
Correctness. We will enumerate all small default, program, causal and autoepistemic theories up to a bounded number of atoms and rules. For each, we compare extensions from our pipeline against brute-force reference semantics and against gk2dlp. Any mismatch counts as a failure of the faithfulness proofs.
Update streams. We will use Ji and Strass's fair-division default theories, the classic flies, innocent and nixon_diamond examples, and the acute, autism and breast-w rule sets from the argumentation-learning paper. Each theory is presented one rule at a time. At every step we record per-update and cumulative latency, translation size, and agreement with the reference.
Loop structure. We will run Hamiltonian-circuit programs through both our pipeline and Lin and Zhao's encodings. For every output we measure the strongly connected components of the positive dependency graph. This tests whether the fixed layer introduces artificial loops of the kind that made the tight encoding blow up on 2xp and 4xp, and whether component size predicts runtime as it did at ICCMA.
Decisive checks. Three outcomes decide the project's standing:
- whether the flat ablation breaks exactly on introspective autoepistemic theories;
- whether incremental solving beats both kinds of recompilation over update streams;
- whether the candidate stable SIX labeling matches autoepistemic expansions on the exhaustive small-theory suite.
A negative answer on the third check would still yield a characterized boundary, joining Imielinski's and Gottlob's, of where rule-local translation of unified nonmonotonic logics stops.
References
- Results on Translating Defaults to Circumscription
- Relating Default Logic and Circumscription
- The Power of Beliefs or Translating Default Logic into Standard Autoepistemic Logic
- Semantics for Non-Flat Assumption-Based Argumentation, Revisited
- Implementing Default and Autoepistemic Logics via the Logic of GK
- Learning Brave Assumption-Based Argumentation Frameworks via ASP
- A Logic Program Characterization of Causal Theories
- On Tight Logic Programs and Yet Another Translation from Normal Logic Programs to Propositional Logic
- Propositional Argumentation and Causal Reasoning
- On Structural Properties of Argumentation Frameworks: Lessons from ICCMA
- ABA+: Assumption-Based Argumentation with Preferences
- On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning and Logic Programming