Answer set programming is a rule language for search and knowledge representation. Rules with an "or" in the head, such as $a \vee b \leftarrow c$, make it more expressive but also harder to solve: deciding whether such a disjunctive program has a solution sits one level higher in the polynomial hierarchy than for ordinary "normal" programs. Two lines of work respond to this gap from different directions. Program transformations remove the "or" so that fast normal solvers can be used. Modular translations compile each rule on its own, so a growing knowledge base never has to be recompiled from scratch. The transformations that correctly remove disjunction all inspect the whole program. The local transformation, shifting (turning $a \vee b \leftarrow c$ into $a \leftarrow c, \neg b$ and $b \leftarrow c, \neg a$), is wrong whenever head atoms support each other in a positive cycle.
This note proposes to treat the strongly connected component of the dependency graph, rather than the rule, as the unit of modular translation. Here a strongly connected component is a maximal group of atoms that can all reach one another through positive dependencies. We argue that strict rule-by-rule elimination is ruled out even for the single rule $a \vee b.$ Component-local elimination is the strongest modularity that remains available. We would build a compiler whose output for any rule depends only on the component containing its head. When a new rule arrives, only the components it merges or touches are recompiled. We would then measure whether this pays off on growing programs relative to native disjunctive solving and to rerunning global transformations after every change.
Core Claim
Existing work leaves two facts sitting side by side.
The first fact is an impossibility for strict locality. Eiter et al. prove that a disjunctive program has a strongly equivalent normal program exactly when its models in the logic of here-and-there are closed under "here-intersection." Strong equivalence means the two programs stay equivalent after adding any rules, which is precisely the guarantee a context-free rule translation needs. The fact $a \vee b.$ already fails this test: the model pairs $(\{a\},\{a,b\})$ and $(\{b\},\{a,b\})$ are both models, but their intersection $(\emptyset,\{a,b\})$ is not. So no rule-local translation without auxiliary atoms preserves stable models under arbitrary additions. This paper motivates the proposal because it shows the obvious goal is unattainable. It also constrains it: we inherit its worst-case exponential blowup and its coNP-hard test, and we make no claim to evade either.
The second fact is that the correct transformations are local in practice. Every obstruction to shifting is a head cycle, and head cycles live entirely inside one component. Restricted unfolding unfolds only the "culprit" atoms $HC(\Pi)$ that lie on head cycles, then shifts. The program classes of Ji, Wan and Xiao (head-weak-elementary-loop-free, HWEF, and head-proper-loop-free, HPF) are defined by loops that are also confined to components, and those loops can be checked in polynomial time. Both papers present their methods as whole-program analyses and never state or exploit this confinement.
The claim is that disjunction elimination under stable models can be made component-modular. The translation of a rule is a function of its head component, and adding a rule invalidates only the translations of components whose structure changes. On streams of rule additions, this turns the per-update cost from "recompile everything" into "recompile the merged components." The proposal differs from the closest work, restricted unfolding, in three ways: it gives a locality theorem, an incremental update procedure, and a hybrid fallback that leaves hopeless components disjunctive instead of blowing them up.
Research Program
Theory. The first task is to extend the Eiter et al. criterion to translations that may introduce fresh auxiliary atoms. This would establish whether the $a \vee b.$ counterexample survives when helper atoms are allowed. We conjecture it does, via a complexity argument about per-rule translations. The second task is to prove that restricted unfolding factors through components. Unfolding a culprit atom substitutes the bodies of that atom's defining rules, and those rules change only when a new rule defines an atom of the same component. We would prove that the unfolded, shifted program equals the union of per-component outputs.
Correctness would be stated as a new equivalence, which we call component-uniform equivalence: the original and compiled programs agree after adding any facts, or any rules whose heads lie in components not merged with existing ones. It sits between the uniform equivalence of Eiter et al., which holds for arbitrary facts, and strong equivalence. It plays the role that uniform persistence plays for forgetting in Gonçalves et al.. They weakened strong persistence to escape an impossibility result and left syntactic operators open. We supply a syntactic operator, for disjunction rather than forgetting.
Compiler. Each component is dispatched to one of four treatments:
- A head-cycle-free component is shifted, which is purely local.
- An HWEF or HPF component, identified with the polynomial checks of Ji, Wan and Xiao run on the component alone, is also shifted.
- A component whose culprit count $k$ is under a budget is restricted-unfolded, with output size $O(n \cdot m^{2k})$ for that component only, where $n$ is the number of rules and $m$ bounds rule size.
- Any other component is left disjunctive, so the solver sees a mostly normal program with small disjunctive islands.
A dependency index maintained incrementally, with union-find over components, tells the compiler which components a new rule merges. Only those components are recompiled.
Baselines
The naive reference point is plain rule-by-rule shifting applied to every rule. It is the only fully local method in the literature. Truszczynski and Woltran show it is exact for supported models, a weaker semantics that does not require atoms to have non-circular justifications. Under stable models it is unsound on head cycles. We would run it on identical rule streams and report its update cost, which is a lower bound for any method, together with the fraction of instances where its answer sets differ from the ground truth. A method that matches its update cost to within a small constant while making zero errors beats it.
The strongest existing transformation is global restricted unfolding. Ji et al. report that on rand_250_2200, clasp solves the rewritten program in 6.67 seconds, compared with 43.91 seconds for the original disjunctive program. In the streaming setting we would rerun it from scratch after every update, with the same grounder, solver version, time limit and hardware. Beating it requires two things. On static instances we must equal its solve time, since a static instance is effectively a single one-shot update. On streams we must show lower cumulative compile-plus-solve time.
The native reference is the disjunctive mode of clasp, re-invoked on the full program after each update. It uses the same solver family, so differences reflect the transformation rather than the engine. Fichte and Szeider's backdoor reduction is included on its own benchmark suite, where it reports backdoors of 0.69% of atoms on ConformantPlanning and close to 50% on RandomQBF.
Two ablations isolate the contribution. The first recompiles globally using our dispatch, which separates the gain from incrementality from the gain from better per-component choices. The second drops the HWEF/HPF branch, which isolates the value of the generalized shiftable classes.
Why not just…?
Why not just use a native disjunctive solver? This is the most serious alternative. Modern disjunctive solvers already treat head-cycle-free components cheaply and reserve expensive minimality checks for the rest, so our hybrid output may add nothing. The 6.67 versus 43.91 second gap from Ji et al. suggests compilation can win, but that is one dataset. If native solving matches us across the 63-program suite, the contribution shrinks to a correctness-and-locality result, and we would say so.
Why not just rerun restricted unfolding after every update? If unfolding time is negligible next to solving time, incrementality buys nothing. We will report the compile-versus-solve time split per update. We predict gains only on long streams of small additions over large programs. If the split shows compilation is always a small fraction, we concede this point.
Why not just shift everything locally? Shifting creates spurious answer sets whenever a head cycle exists, as established by Ji et al. and Truszczynski and Woltran. The spurious-model counts in our experiments quantify how often this happens on realistic streams.
Why not just use the backdoor reduction to SAT? Its detection step, a minimum vertex cover over the head dependency graph, is global. Its cost grows exponentially in backdoor size, which is near half the atoms on RandomQBF according to Fichte and Szeider. On structured domains it may beat us, and the comparison on their suite will show where.
Proposed Experiments
The static experiments use three suites. On the 63-program disjunctive suite (Sokoban, Mutex, Strategic Companies, qbf.cgs and others), Ji, Wan and Xiao report that 32% of the non-head-cycle-free qbf.cgs programs are HWEF*. We measure what fraction of components land in each dispatch branch, along with output size and solve time. The other two static suites are rand_250_2200 and the ASP-competition backdoor domains.
For streams, we order each program's rules along random and domain-natural orders, such as adding instance facts before problem rules and adding planning steps one at a time. We apply the rules incrementally, checking answer-set equality against native solving at every step. Metrics are the number of rules recompiled per update, cumulative compile-plus-solve time, output size, and number of timeouts.
The decisive checks are four:
- Zero answer-set mismatches, which verifies the locality theorem empirically.
- Recompiled volume that tracks merged-component size rather than program size.
- Cumulative time below the rerun-unfolding baseline on long streams.
- An honest per-domain verdict against native disjunctive solving.
As a secondary check, compiled normal components can be passed through the tightness transformation of Lin and Zhao, which makes positive loops disappear so a SAT solver can be used, to test whether component-local disjunction elimination composes with it. Their reported timeouts on the 2xp and 4xp instances warn that this step may hurt on structured inputs.
References
- Eliminating Disjunction from Propositional Logic Programs under Stable Model Preservation
- Eliminating Disjunctions in Answer Set Programming by Restricted Unfolding
- On Elementary Loops and Proper Loops for Disjunctive Logic Programs
- Forgetting in Modular Answer Set Programming
- Hyperequivalence of Logic Programs with Respect to Supported Models
- Backdoors to Normality for Disjunctive Logic Programs
- On Tight Logic Programs and Yet Another Translation from Normal Logic Programs to Propositional Logic