Counting Answer Sets of Recursive Programs Without Grounding

Answer set programming (ASP) writes knowledge as rules such as "x is infected if x was exposed, or if some contact of x is infected." A program's meaning is its set of stable models: truth assignments in which every true fact can be derived from the rules without circular reasoning. Probabilistic versions of ASP need the number of stable models, often weighted, over a domain of $n$ objects. Today that means grounding: replacing every variable with every constant, which yields $O(n^2)$ propositional atoms for a single binary relation, and then running a propositional counter. A separate line of work, weighted first-order model counting (WFOMC), counts models of first-order sentences in time polynomial in $n$. It does this without enumerating objects, but only when every sentence uses at most two logical variables. With three variables the problem becomes #P$_1$-complete. The difficulty is that "no circular reasoning" is a recursive condition. The standard way to express it modularly, a derivation order that must be transitive, needs three variables and falls off that cliff.

This note proposes a rule-by-rule translation from a class of recursive (non-tight) logic programs into two-variable counting logic plus one acyclicity axiom. The translation replaces the transitive ordering with a signed choice of supporters. Each derived atom picks a nonempty set of rule instances that justify it, and each pick carries a weight of $+1$ or $-1$ according to the size of the set. A single axiom then requires the chosen support relation to have no cycles. The signs are designed so that every stable model contributes exactly 1 and every circularly justified model contributes 0. If this holds in general, stable-model counting for this program class becomes polynomial in the domain size. It would also stay modular: adding a rule adds one local sentence and never requires recompiling the rest.

Core Claim

Take a normal logic program in which rules use at most two variables and each strongly connected component of positive recursion runs through a single unary predicate $p$, over an arbitrary extensional binary relation such as a contact graph $e$. The translation has three parts.

  1. Completion. Clark's completion states that each true atom has some applicable rule. It expresses exactly the "supported" models, which are the stable models plus those justified only by cycles.
  2. Signed supporter choice. Each true atom $p(x)$ whose support is recursive (it holds via a body atom $p(y)$ and not via a non-recursive rule) selects a nonempty set $T_x$ of such supporters $y$. This is encoded with a binary predicate $S(y,x)$ together with the negative-weight device from Skolemization for Weighted First-Order Model Counting. That paper removes existential quantifiers sentence by sentence while staying in two-variable logic, by giving auxiliary predicates weight $-1$ so that spurious models cancel. Here the weight makes a pick of size $|T_x|$ contribute $(-1)^{|T_x|+1}$.
  3. Acyclicity. The axiom $\mathrm{DAG}(S)$ forbids cycles in $S$. It comes from Weighted First Order Model Counting with Directed Acyclic Graph Axioms, which shows that two-variable counting logic ($C^2$) plus one DAG axiom remains polynomial in $n$ via inclusion–exclusion over sources.

The claimed identity is the following. For a model $M$ of the completion, let $R$ be the set of recursively supported true atoms. Then

$$\sum_{\substack{(T_x)_{x \in R} \text{ nonempty},\; S \text{ acyclic}}} \;\prod_{x\in R} (-1)^{|T_x|+1} \;=\; \begin{cases} 1 & M \text{ stable} \\ 0 & \text{otherwise.}\end{cases}$$

Without the acyclicity requirement, the sum over each atom's nonempty subsets is $\sum_{\emptyset\neq T\subseteq A}(-1)^{|T|+1}=1$ for a nonempty set $A$ of available supporters, which is why the signs are chosen this way. Acyclicity then removes the circular picks.

I checked the identity by hand on small cases:

  • a chain;
  • an atom with two alternative supporters;
  • a two-cycle that is unfounded, which gives 0;
  • two mutually recursive atoms that each also have an external supporter. Here five acyclic picks survive, with signs $+1+1-1+1-1=1$.

A general proof, most likely a sign-reversing involution that pairs cyclic contributions, is the first deliverable. If the proof fails, the fallback is to characterize exactly which dependency shapes satisfy the identity.

The key contrast is with On Tight Logic Programs and Yet Another Translation from Normal Logic Programs to Propositional Logic. That paper eliminates non-tightness modularly with an ordering predicate right(u,v), which is fine for SAT solving. Relationally, though, the ordering needs transitivity over three variables, and Weighted model counting beyond two-variable logic shows that this makes counting #P$_1$-complete. The proposed translation never asserts transitivity. It asserts only local choices plus one global structural axiom, the same design move that Lifted Inference with Tree Axioms used for spanning trees.

Research Program

Theory. Prove the signed-support identity for the unary-recursion class. Then show that the output lies in $C^2$ plus $\mathrm{DAG}(S)$, so that counting is polynomial in $n$ by the DAG-axiom result. The polynomial's degree grows with the number of 1-types, the $O(n^{2u})$ bound from that paper, where $u$ is the number of 1-types.

Modularity. Frame each rule's contribution as a def-module in the sense of First-Order Modular Logic Programs and their Conservative Extensions (Extended Abstract). That paper proves that replacing a module by a conservative extension over a larger signature preserves the whole program's stable models, but it performs rewritings by hand and never tracks variable count. Our contribution is an automated rewriting that is variable-bounded and weight-preserving. A second weighted variant should preserve the weighted count, so that soft rules in $LP^{MLN}$ carry over.

Engineering. Implement the compiler on top of a DAG-capable WFOMC solver. Where the DAG solver itself becomes the bottleneck, reuse the cell-graph machinery from Faster lifting for two-variable logic using cell graphs.

Limits to map honestly. Several cases fall outside the class, and each needs to be delimited:

  • Recursion through binary intensional predicates such as reach(x,y) produces a support graph over pairs of objects, not over objects, so it leaves the class.
  • Several unary predicates in one recursive component would need several interacting DAG axioms. The DAG paper supports only one.
  • Binary evidence breaks symmetry. It may be absorbable by combining with Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence, but that is a stretch goal.

Baselines

Naive reference: completion only. This drops parts 2 and 3 of the translation and counts models of Clark's completion alone, in plain two-variable logic. It is exact for tight programs, and it is the tempting shortcut. On recursive programs it counts supported models, so it overcounts. Measuring the size of that overcount across domain sizes shows how much the acyclicity machinery matters. It runs on the same lifted solver with no tuning.

Strongest exact competitor: grounding plus propositional counting. Ground the program and translate it modularly with Lin–Zhao ordering or with loop formulas (Loop Formulas for Circumscription). Then count with d4, and separately count by answer-set enumeration in clingo. This is the standard practice and the only exact alternative for recursive programs. All systems get the same machine, a single core, and the same per-instance timeout.

No reported result was found on Lacuna for stable-model counting on these programs. The nearest reported evidence is from bounded-treewidth WFOMC, where d4 and Forclift "failed before reaching a domain size of 100" while TD-WFOMC handled 300+ (Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence). On the lifted side, FASTWFOMC reached $n=150$ in under 6 seconds on 3-regular graphs (Faster lifting for two-variable logic using cell graphs). Beating this baseline means two things. First, both systems must give identical exact counts wherever both finish. Second, our system must scale to domain sizes at least several times larger than the largest instance d4 finishes, with runtime growing polynomially rather than exponentially in $n$.

Approximate competitor. Write the Lin–Zhao encoding relationally, as a three-variable sentence, and run ApproxWFOMC from Approximate Weighted First-Order Model Counting: Exploiting Fast Approximate Model Counters and Symmetry, which that paper shows keeps producing bounds on three-variable transitive models after exact solvers fail. We give it the same wall-clock time. It is beaten if our exact count arrives faster than ApproxWFOMC reaches a stated tolerance, for example a factor of 1.1.

Ablations isolating the key ingredient. The first ablation removes the signs, weighting every supporter choice by $+1$; this should overcount. The second removes $\mathrm{DAG}(S)$; this should reproduce the completion-only count. If either ablation also matches the ground truth, the mechanism is not doing what we claim.

Why not just…?

Why not just ground and count with d4 or clingo? On small domains this is the right tool, and we will use it as ground truth. The problem is that the number of ground atoms grows with $n$ and loop constraints multiply over cycles of the contact graph. The file's evidence that exact propositional compilers stall below $n=100$ on comparable relational counting problems (Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence) suggests the same wall here. The scaling experiment settles it directly. If d4 matches our growth curve on these programs, the proposal's practical value collapses to modularity alone, and we will report that.

Why not write the transitive ordering in first-order logic and approximate? Hashing-based approximation avoids the three-variable wall but still needs many SAT calls on large ground formulas. The ApproxWFOMC paper itself needs cardinality decomposition to control exponentially skewed weights. This alternative is a real threat when approximate answers suffice. The head-to-head time-to-tolerance comparison decides whether exactness costs us anything.

Why not encode derivation levels with unary predicates $L_1,\dots,L_k$ in $C^2$? A level mapping avoids transitivity, but a stable model may need up to $n$ levels. The number of predicates would then grow with the domain, and the number of cells grows exponentially in the number of predicates (Faster lifting for two-variable logic using cell graphs). That destroys polynomial scaling. We will include a fixed-$k$ level encoding to show where truncation starts producing wrong counts.

Why not pick one canonical parent per atom with the Tree axiom? Choosing a canonical supporter requires an order on objects, which reintroduces the ordering problem. Letting every parent choice count instead overcounts stable models by the number of spanning forests. The signed subset choice exists precisely to avoid needing a canonical choice.

Proposed Experiments

Programs. We will build a family of recursive programs that plays the same role for stable-model counting that transitive-smokers-mln plays for three-variable MLNs: recursive-influence smokers, epidemic spread over contacts, and "reachable from a seed set" over an unconstrained binary relation. Each has an $LP^{MLN}$ weighted variant. Weight semantics follow the linear modular translation of On the Relationship between P-log and LPMLN, restricted, as that paper is, to rules without disjunctive heads.

Decisive check 1: exactness. Counts must agree exactly with clingo enumeration and d4 on grounded Lin–Zhao encodings, for every $n$ where grounding finishes, with the target of $n$ up to about 8 to 10. This test comes first, because a single mismatch falsifies the core identity.

Decisive check 2: scaling. Plot runtime against $n$ for our system, d4, clingo, and ApproxWFOMC. The measured log–log slope of our curve must stay bounded as $n$ grows.

Decisive check 3: incremental updates. Add one rule at a time and compare the recompilation cost of our system with global recompilation. For our system the cost should be constant per added rule.

Boundary test. Run a program with a binary recursive predicate, which should fall outside the class. This documents where the method stops rather than hiding it.