Many reasoning problems minimize the unexpected. A diagnosis should blame as few components as possible, and a model of actions should assume that nothing changes unless something causes it. The standard logic for this is circumscription: keep only the models in which certain "abnormal" predicates are as small as possible. Over the past fifteen years, circumscription has become practical by compiling it into answer set programming (ASP), a logic-programming language whose solvers search for minimal, self-justifying models. The catch is that every one of these compilers assumes a finite universe of objects. Real diagnosis and action problems involve gate delays, fluid levels, and trajectory heights, which are real numbers. Today those values get rounded onto an integer grid, and the reasoning is then only as good as the grid.
Description logics solved a structurally similar problem decades ago through concrete domains. A concrete domain is a fixed numeric structure, such as the reals with comparisons, attached to logical individuals through functional "features" such as hasDelay. It is handed to an external solver under one condition: conjunctions of its constraints must have a decidable satisfiability test that is closed under negation. This note proposes to bring that discipline into circumscription compilation. The abstract objects stay finite and are handled by an ASP solver. The real-valued features stay real and are handled by a constraint solver. The new piece is a minimality check that ranges over all real values, and it turns out to be exactly the kind of query that the concrete-domain admissibility conditions make decidable.
Core Claim
Take a first-order circumscriptive theory over a finite set of abstract individuals, extended with concrete features into an admissible domain $\mathcal{D}$ such as linear real arithmetic. Its circumscribed models can be computed exactly, with no discretization, by a constraint-ASP encoding combined with a counterexample-guided minimality oracle.
The encoding is direct when the concrete features are fixed during minimization. Fixed features are values that come from observations, so constraints over them act as tests. The harder case is when concrete features vary, which is the normal situation in diagnosis and physics. Then a candidate model is minimal only if no interpretation with a strictly smaller abnormality set satisfies the theory under any assignment of real values. That is an exists–forall question over reals, and plain constraint ASP cannot express it, because its constraint atoms are evaluated against one fixed numeric assignment.
The method has two parts. The ASP side guesses a candidate abnormality set. A single satisfiability query over $\mathcal{D}$ then asks whether a smaller set is consistent. Each counterexample becomes a purely Boolean nogood, a learned constraint that rules out a set of abnormality assignments. Two facts make this sound, complete, and terminating:
- Admissibility guarantees that the query is decidable.
- The Boolean space of abnormality sets is finite.
The abstract recursion, such as frame persistence or reachability, stays inside ASP's native unfounded-set reasoning. This means non-tight programs are covered, which is where the existing equivalence between constraint ASP and satisfiability modulo theories (SMT) stops.
Relation to Prior Work
The method builds on two compiler lines. Computing General First-Order Parallel and Prioritized Circumscription gives linear translations of parallel and prioritized circumscription into stable-model programs (cfo2lp, solved by clasp). Translating First-Order Theories into Logic Programs gives an auxiliary-free embedding and an existential-elimination translation (T2LP). We reuse their translation of the abstract part.
Both require finite ordered domains. T2LP's existential elimination walks a successor relation that does not exist on the reals, and this is the constraint our design has to escape. The escape comes from A Scheme for Integrating Concrete Domains into Concept Languages, which fixes concrete values to individuals through functional features. Under that scheme, an existential over a concrete value is witnessed by a feature term. Since there are finitely many individuals, there are finitely many such terms, and each becomes one constraint variable instead of a grounded range. We also borrow the cluster strategy of Reasoning with Concrete Domains, which checks feature-connected groups of constraints independently. Here it splits each minimality query into small independent sub-queries.
Two further lines of work constrain what we attempt:
- NExpTime-complete Description Logics with Concrete Domains shows that inverse roles combined with feature agreements cause undecidability. We therefore exclude feature agreements across inverse relations from the input language.
- Constraint Answer Set Programming versus Satisfiability Modulo Theories proves that constraint-ASP and SMT answers coincide only for tight programs. That result motivates keeping the abstract minimality inside ASP rather than translating everything to SMT.
The applications motivate the work. Circumscriptive Event Calculus as Answer Set Programming compiles a circumscriptive action calculus to ASP but discretizes continuous fluents. On the planning side, PDDL+ Planning via Constraint Answer Set Programming and Planning for Hybrid Systems via Satisfiability Modulo Theories handle continuous dynamics exactly, but they have no minimization of abnormal events. We combine the minimization of the first with the exact numerics of the other two.
Research Program
The input language is many-sorted first-order logic. It has a finite abstract sort, concrete features into $\mathcal{D}$, and predicate restrictions $P(u_1,\dots,u_n)$ over feature paths in the style of Baader and Hanschke. On top of that sits $CIRC(T; P; Z)$, where $T$ is the theory, $P$ is the set of minimized predicates, and $Z$ is the set of varying symbols. A feature listed in $Z$ is a varying concrete feature; any feature not in $Z$ is fixed.
The theoretical work has three parts:
- Correctness of the fixed-feature translation. We will prove that extending cfo2lp's translation with constraint atoms yields stable models of a constraint-ASP program that correspond one-to-one with circumscribed models. Constraint atoms are treated as non-minimized, so negation closure of $\Phi^\mathcal{D}$ lets negated restrictions become constraint atoms again.
-
Correctness and termination of the varying-feature loop. For a candidate abnormality set $A$, the oracle decides $$\exists A' \subsetneq A,\ \exists \text{abstract interpretation } I',\ \exists v' \in \Delta^{\mathcal{D}} : I', v' \models T,$$ where $A'$ is a smaller abnormality set, $I'$ is an interpretation of the remaining abstract symbols, and $v'$ assigns real values to all feature terms. Once the abstract part is fixed, this is a finite conjunction-and-disjunction over $\Phi^\mathcal{D}$, so admissibility makes it decidable. The loop terminates because each counterexample removes at least one Boolean abnormality pattern, and there are finitely many.
-
Prioritized circumscription. We will extend the loop using cfo2lp's decomposition of priorities into parallel circumscriptions.
The implementation will sit on clingo with a numeric-constraint backend (linear real arithmetic through an SMT solver). The minimality oracle will be implemented as a propagator, a solver plug-in that adds the learned nogoods during search. This way the counterexamples prune the search as it runs, instead of restarting it.
Baselines
The naive reference is discretize-then-compile. Real values are scaled onto integer grids at several resolutions, and the resulting theory is run through unmodified cfo2lp, or through ECASP for the action-calculus benchmarks. This is what practitioners do today. We will run it at resolutions from coarse to the finest that grounds within the time limit, using the same machine, the same timeout, and default solver settings for both systems. Beating it means two things:
- Our method returns the exact set of minimal diagnoses where every grid that fits within the limit returns spurious or missed diagnoses.
- Our method matches or beats the time of the finest grid that is still correct.
For reference on the original finite benchmarks, cfo2lp solves the 40-gate circuit diagnosis instance in about 0.4 seconds, against nearly 10 seconds for circ2dlp, which also times out at 80+ gates (Computing General First-Order Parallel and Prioritized Circumscription). ECASP solves all 14 Event Calculus problems and finishes Falling w/ AntiTraj in 0.08 seconds, against 270.2 seconds for the DEC reasoner (Circumscriptive Event Calculus as Answer Set Programming). Our method should stay within a small constant factor of these numbers when the concrete features are absent or fixed.
The strongest exact competitor is a direct exists–forall SMT encoding. Because the abstract domain is finite, circumscription can be written as one quantified formula over Booleans and reals and handed to a solver with quantifier support for linear real arithmetic. It is exact and needs no ASP, so it is the real threat. It gets the same time limit, and we will tune its quantifier-instantiation settings with the same small budget we spend tuning our own system. Beating it means solving more instances, or the same instances faster, especially on non-tight instances with recursion.
The key-ingredient ablations are two. The first replaces the incremental oracle with a one-shot check after each complete answer set, which isolates the value of learning nogoods during search. The second turns off cluster decomposition. A third reference point is the fixed-feature encoding run with only observed values, which shows how much the varying-feature case costs.
Why not just…?
Why not just discretize and use cfo2lp or ECASP? Grounding is already the documented bottleneck of cfo2lp. The planning literature reports that discretized planners miss invariant violations between time points or exhaust memory (Planning for Hybrid Systems via Satisfiability Modulo Theories). Whether diagnosis inherits these problems is an empirical question, not something we can assume. The resolution sweep in our first experiment answers it. If a modest grid is always exact on realistic instances, the case for our method reduces to the non-tight and prioritized settings, and we will report that.
Why not just encode circumscription as a quantified SMT formula? This is a genuine competitor, and we run it as the main exact baseline. Our expectation that it falls short has two sources. First, quantified reasoning over Booleans and reals relies on heuristic instantiation. Second, recursive abstract definitions must either be unrolled or supported by loop formulas. Lierler and Susman's equivalence covers only tight programs, and the completion-based DEC reasoner failed on Commuter and BusRide. If the SMT encoding matches us on non-tight instances, the contribution shrinks to the correctness theory, and we will say so.
Why not just call external numeric procedures from ASP? Opaque calls of this kind cannot produce nogoods over constraints. Lierler's transition-system analysis (On the Relation of Constraint Answer Set Programming Languages and Algorithms) attributes constraint-ASP performance precisely to propagation in both directions between the logic solver and the numeric solver. More fundamentally, such calls evaluate a constraint at one assignment. They cannot answer the "for all real values" question that minimality requires. Our one-shot ablation measures how much the integrated propagation actually buys.
Proposed Experiments
The first experiment is timed circuit diagnosis. We extend the ripple-adder circuit diagnosis problem from the cfo2lp paper with real-valued gate delays. Delays are varying features with interval constraints, observations are output arrival times, and prioritized abnormality comes from the original failure ordering. We construct instances where the correct diagnosis depends on delays falling between grid points. Ground truth is computed by the SMT baseline at small sizes and checked for agreement across systems. No reported result found on Lacuna for this timed variant, since we create it. The untimed original serves as the regression check against the 0.4-second figure. Metrics are diagnosis-set precision and recall against ground truth, wall-clock time, grounded program size, and the number of oracle calls.
The second experiment uses the 14-problem Event Calculus suite. We take the problems with continuous fluents, chiefly Falling w/ AntiTraj, and re-encode them with real-valued time and heights under linear trajectories. We then compare against ECASP at several discretizations. Coverage of all 14 problems must be preserved.
The third experiment is a fault-augmented PDDL+ domain. We take the Generator domain and add an abnormal leak predicate to be minimized. The questions are whether the planners in PDDL+ Planning via Constraint Answer Set Programming and Planning for Hybrid Systems via Satisfiability Modulo Theories can represent minimal-fault explanations at all, and how our method scales. Those papers give no numeric times on Lacuna, so we report only our own runs. The Torricelli dynamics there are non-linear, so this experiment uses a polynomial domain and is explicitly marked as beyond the admissible linear fragment.
The decisive checks are three:
- Exactness where discretization provably errs.
- Scaling at least comparable to the quantified SMT baseline on non-tight instances.
- A measured termination profile, giving oracle calls as a function of the number of abnormality atoms.
If the third grows exponentially on realistic instances, the counterexample loop is the wrong design, and generalizing nogoods will become the next research question.
References
- Computing General First-Order Parallel and Prioritized Circumscription
- Translating First-Order Theories into Logic Programs
- A Scheme for Integrating Concrete Domains into Concept Languages
- Reasoning with Concrete Domains
- NEXPTIME-Complete Description Logics with Concrete Domains
- Constraint Answer Set Programming versus Satisfiability Modulo Theories
- Circumscriptive Event Calculus as Answer Set Programming
- PDDL+ Planning via Constraint Answer Set Programming
- Planning for Hybrid Systems via Satisfiability Modulo Theories
- On the Relation of Constraint Answer Set Programming Languages and Algorithms