Lazy-Grounding for Answer Set Programs with External Source Access

1 Introduction

HEX-programs [Eiter et al., 2005; 2016a] enrich answer set programs [Gelfond and Lifschitz, 1991] with the possibility to exchange information with external sources in a bidirectional way. This greatly increases the problem solving capacity of Answer Set Programming (ASP) [Brewka et al., 2016], as in the plugin-architecture of HEX-solvers like DLVHEX, arbitrary sources can be accessed via an API style interface called external atom. For example, an external atom &prop[config](P) might be used in a configuration problem to retrieve from a property checker each property P of a candidate solution, given by selected components in the predicate config. External atoms have been fruitfully exploited for a wide range of applications (see [Erdem et al., 2016; Eiter et al., 2016d]).

Efficient evaluation of HEX-programs is challenging, due to the generic (sometimes black-box) nature of external atoms and value invention, i.e., the import of new constant symbols from the sources into the program. Advanced algorithms have been developed [Eiter et al., 2016a] which roughly speaking rewrite a given HEX-program into an ordinary ASP program, solve the latter using an ASP solver, and finally check whether the obtained answer sets are compatible with the external sources.

∗This research has been supported by the Austrian Science Fund (FWF) projects P27730 and W1255-N23.

By this approach, HEX-programs inherit the well-known grounding bottleneck of state-of-the-art ASP solving (as e.g. by CLINGO [Gebser et al., 2011a]) which may show up in the grounding phase, i.e. during the computation of a propositional program equivalent to the input program, and can cause an exponential blowup. This makes ASP and likewise HEX incapable of solving a number of real-world problems with larger data volume. To mitigate this problem, several advanced optimization methods and techniques have been developed, cf. [Kaufmann et al., 2016], but the grounded program can still be (too) large. For HEX-programs, grounding is due to external atoms an even bigger challenge, which has been tackled with sophisticated program decomposition and component grounding techniques [Eiter et al., 2016a]. However, decomposition has a trade-off with efficient solving, and without decomposition exponentially many inputs to an external atom may have to be considered during grounding, e.g. for the external atom&prop[config](P) from above, if properties nonmonotonically depend on the input configuration. Hence, novel evaluation algorithms are an issue.

To overcome the grounding bottleneck of ASP, lazygrounding algorithms were devised, that ground rules on-thefly [Pal`u et al., 2009; Lef`evre and Nicolas, 2009a; 2009b; Dao-Tran et al., 2012; Lef`evre et al., 2017]. In an interleaved grounding and solving process, only rules are grounded that are currently useful and thus space explosion is avoided. In this way, problems can be solved that traditional ASP solving cannot handle. Recent advances in lazy grounding, available in prototype solvers, suggest to explore this approach for evaluating HEX-programs. However, an extension to this setting is non-trivial, due to nonmonotonic dependencies of external atoms on absent information, and in particular due to unknown constants from value invention.

Our main contributions are briefly summarized as follows:

• we introduce a novel external source interface to incrementally extend a HEX-program grounding, where new output terms may appear during solving (Sec. 3);
• we give a novel evaluation algorithm for HEX-programs that exploits a lazy-grounding ASP solver (Sec. 4); and

• we show experimental results which confirm the benefit of the new algorithm on illustrative benchmarks (Sec. 5).

The unprecedented integration of lazy-grounding, external source evaluation and value invention is a new perspective to

make HEX and ASP more suitable for real-world applications. An extended version of this paper containing proofs of the technical results is available [Eiter et al., 2017].

2 Preliminaries

We assume a finite set P of predicate symbols, a finite set C of constant symbols and a set V of variables. Atoms a are of the form p(t) with p ∈ P and t = t1, . . . , tn a list of terms ti ∈ C ∪ V; a is ground if each ti is in C. A (signed) literal is a positive or a negated ground atom Ta (intuitively, a is true) or Fa (a is false). A nogood is a set {L1, . . . ,Ln} of literals Li of type Ta or Fa. A partial assignment A over the Herbrand Base HB of all ground atoms is a set A of signed literals of kind Ta, Fa and Ua (intuitively, a is unassigned) such that for every a ∈ HB, |A∩ {Ta,Fa,Ua}| = 1. We call A complete, if no Ua occurs in it.

HEX-programs [Eiter et al., 2005; 2016a] extend ordinary ASP programs by external atoms of the form &g [p](t), which enable a bidirectional interaction of a program and external computation sources. Here &g is an external predicate name, p = p1, . . . , pk is an input list of input parameters (predicate names wlog.), and t = t1, . . . , tℓ ∈ C∪V are output terms; we write p ∈ p if p = pi for some 1 ≤ i ≤ k and analogous for t ∈t. An external atom is ground, if t consists of constants.

We consider normal HEX-programs Π, i.e., sets of rules r

where a is an (ordinary, potentially absent) atom and each bj is either an ordinary or an external atom. The body of r is B(r)= {b1, . . . , bm, not bm+1, . . . , not bn} and the positive body is B+(r)={b1, . . . , bm}. A rule r is safe, if each variable occurring in r also occurs in B+(r). Every rule r in a HEX-program Π must be safe. Moreover, to ensure external atoms introduce only finitely many new constants, we assume Π is liberal domain-expansion (lde) safe. The notion of ldesafety allows to modularly combine syntactic and/or semantic safety criteria to guarantee that a HEX-program is finitely groundable (cf. [Eiter et al., 2016b] for more details), and it is the most liberal safety notion that has been considered wrt. the HEX formalism. The grounding grd(r) of r is the set of all possible rules rσ that result from r by applying a (ground) substitution σ : V →C; the grounding of program Π is grd(Π) = ⋃r∈Π grd(r).

Semantics. We follow [Eiter et al., 2016c] for semantics based on partial assignments. The semantics of a ground external atom &g[p](c) with k input and ℓ output parameters wrt. a partial assignment A is given by a 1+k+ℓ-ary three-valued oracle function f&g that is defined for all possible values of A, p and c. Thus, &g[p](c) is true, false or unassigned relative to A, if the value of f&g(A, p, c) is T, F or U, respectively. Moreover, if A is complete, then f&g(A, p, c) ̸=U holds and as usual, f&g(A, p, c) depends only on the extension (in A) of predicates p ∈ p.

A partial assignment A satisfies (or models) a ground atom a, denoted A |= a, if Ta ∈ A; and it models a ground external atom &g[p](c) if f&g(A, p, c) = T. Satisfaction of ordinary rules and ASP programs [Gelfond and Lifschitz, 1991] wrt. complete assignments is naturally extended to HEX-rules and programs. The answer sets of a ground HEX-program Π are defined as follows. Let the FLP-reduct of Π wrt. a complete assignment A be the set fΠA = {r ∈ Π | A |= b, for all b ∈ B(r)} of all rules whose body is satisfied by A, and let for partial assignments A1, A2 denote A1 ≤ A2 that {Ta ∈ A1} ⊆ {Ta ∈ A2}. Then,

Definition 1. A complete assignment A is an answer set of a ground HEX-program Π, if A is a ≤-minimal model of fΠA. 1

The answer sets of a non-ground HEX-program Π are those of grd(Π).

Example 1. Consider the program Π = {← &size[p](0); p(X)←d(X); a← not d(c); d(c)← not a} where the external atom &size[p](Z) computes the cardinality of p, i.e., f&size(A, p,Z) = U if Up(X) ∈ A for some X, f&size(A, p,Z) = T if |{p(X) |Tp(X) ∈ A}| = Z, and f&size(A, p, Z) = F otherwise. The single answer set of Π is {d(c), p(c)}, because it satisfies the first rule, which expresses that the extension of predicate p must not be 0.

3 Evaluation of External Sources Based on Partial Groundings

Lazy-grounding means that the grounding grd(Π) of a program Π is computed lazily, i.e., only ground rules deemed necessary are computed. In the following, let GΠ ⊆ HB denote the set of all atoms occurring in the grounding of Π. Then, partial assignments in the case of lazy-grounding are given with respect to a set of ground atoms A ⊆ GΠ ⊆ HB.

Definition 2. A partial assignment over a set A ⊆ HB of atoms is a set AA of signed literals Ta, Fa, and Ua with a ∈ A s.t. for every a ∈ A, |A∩ {Ta,Fa,Ua}| = 1; it is complete (wrt. A), if no Ua occurs in it.

For partial assignments AA, A′A′ we call A′A′ an extension of AA, denoted A′A′ ⪰ AA, if {Ta ∈ AA}∪{Fa ∈ AA} ⊆ A′A′ and A ⊆ A′ , i.e., some atoms a ∈ HB not present in AA may be present in A′A′ and some unassigned atoms in AA may be flipped to true or false.

Lazy-grounding ASP solving is founded in the notion of a computation sequence (cf. [Lef`evre and Nicolas, 2009a]), which is a monotonically growing sequence (A0, . . . ,An) of partial assignments such that whenever a (lazily grounded) rule of the input program fires at Ai, it is guaranteed to fire in all later assignments Aj, i.e., 0 ≤ i ≤ j ≤ n. Furthermore, a grounded rule r only fires in Ai if it is applicable, which means that its positive body B+(r) is completely true, i.e., B+(r) ⊆ Ai. Given that ordinary ASP rules are safe, the whole negative body of a ground rule is known once it fires, such that focusing on positive rule bodies is sufficient for completeness of solving under lazy-grounding. For example, if the rule p(a) ← q(a), not r(a) fires in a computation sequence at Ai, then {Tq(a), Fr(a)} ⊆ Ai and monotonicity guarantees the same for all later Aj, i ≤ j.

1 For ordinary Π, these are Gelfond & Lifschitz's answer sets.

For (ground) external atoms, it is much harder to ensure that once an output becomes true, it will stay true even for larger input. Eiter et al. [2016c] introduced the notion of assignment-monotonic oracle-function to ensure this in the case where the grounding of a program is generated prior to solving. Formally, a three-valued oracle function f&g is assignment-monotonic, if f&g(AGΠ , p, c) = X, X∈{T,F}, implies f&g(A′GΠ , p, c)=X for all partial assignments A′GΠ ⪰AGΠ . Intuitively, this guarantees that the oracle-function cannot treat Ta /∈ AGΠ as being equivalent to Fa ∈ AGΠ . Observe that all atoms a ∈ HB \ GΠ must be false in every answer set, simply because there is no rule in the grounding of Π whose head is a. As all assignments for the latter program are over GΠ, it is thus guaranteed that each atom a relevant for the external source also occurs in AGΠ , either as Ta, Fa, or Ua. For an AA with A ⊂ GΠ and a ∈ GΠ \A, however, an oracle-function treats a as false, i.e., AA equals (A∪{Fa})A∪{a} from the perspective of any oracle-function, even for assignment-monotonic ones.

As oracle-functions are black-boxes, HEX cannot determine the relevant input of an assignment-monotonic oraclefunction, i.e.: if f&g(AA, p, c)=T for an assignment AA, then, without knowing the set of ground atoms GΠ that occur in the grounding of a HEX-program Π, we cannot determine whether some atom a ∈ GΠ \ A exists s.t. f&g((A ∪ {Ua})A∪{a}, p, c) ̸= T.

Example 2. Reconsider Π from Example 1. Assume that Ta is guessed, before grounding the second rule. Then, &size[p](0) is true under AA = {Fd(c),Ta} with A = {d(c), a}. However, guessing Td(c) and grounding the second rule for X=c, yields A′A′ = {Td(c),Fa,Tp(c)} with A′ = A∪{p(c)}. Thus, f&size(A′A′ , p, 0) = F, which shows that AA was insufficient for deciding the value of &size[p](0).

To address this issue, we must ensure that external atoms are evaluated only with assignments being complete for their input predicates. Intuitively, an assignment is input-complete for a program, if it contains all relevant input to every external atom; a ground atom that occurs in no answer set and is not an input-predicate of any external atom is irrelevant for the truth of external atoms and thus ignored. For a partial assignment AA, let its completion wrt. HB be ˆAA = (A∪ {Fa | a ∈ HB \ A})HB. Then input-completeness is as follows:

Definition 3. A partial assignment AA is input-complete for an external atom &g[p](c) occurring in a ground HEXprogram Π, if f&g(ˆAA, p, c)=T only if every answer set A′HB of Π s.t. A′HB ⪰Arel fulfills f&g(A′HB , p, c)=T, where Arel = {Xa ∈AA | a has predicate p ∈ p} is the relevant input to &g. A partial assignment AA is input-complete wrt. a HEX-program Π, if it is input-complete for each external atom &g[p](c) occurring in grd(Π).

Without restriction to answer sets, in Example 2 no inputcomplete assignment AA on A⊂HB for &size[p](0) would exist with f&size(A, p, 0)=T, as infinitely many constants could be added to p′ s extension if the grounding is extended.

Example 3 (cont'd). There is no partial assignment defined over {d(c), a} that is input-complete for Π, but the partial assignment {Td(c), Fa, Tp(c)} is input-complete for Π.

In the following, we characterize syntactically sets of ground atoms that are sufficient for input-completeness, resorting to nonmonotonic inputs to external atoms; monotonic input cannot cause issues with atoms a∈HB \ A that do not yet occur in an assignment AA. Formally, an input predicate p∈p of an external atom &g[p](c) is monotonic, if f&g(AA, p, c)=T implies f&g(A′A′ , p, c)=T for any A′A′ ⪰ AA that augments a given AA only by atoms with predicate p (cf. [Eiter et al., 2016b]). Then the following proposition can be shown.

Proposition 1. Let &g[p](c) be an external atom occurring in a ground HEX-program Π and let each p∈p be monotonic. Then, any partial assignment AA is input-complete for &g [p](c).

Many external atoms have only monotonic input (e.g., string concatenation, dl-atoms, and the RDF atom in the DLVHEX library). Regarding nonmonotonic input, the set pm(Π) contains all predicates occurring as not monotonic input to some external atom in program Π, i.e., pm(Π) = {p ∈ P | &g[p](c) occurs in Π, p ∈ p, p is not monotonic}.

Definition 4. For a HEX-program Π, a (finite) set A⊆HB of ground atoms is an input-safe domain of Π, if it contains each atom p(X) where p ∈ pm(Π) and Tp(X) ∈ A for some answer set A of Π.

Proposition 2. A partial assignment AA is input-complete wrt. a HEX-program Π, if A is an input-safe domain of Π.

Notably, Definitions 4 and 3 are in semantic terms, relying on answer sets of a given program. We capture those notions syntactically by the relevant grounding G∞relΠ(p,∅) (∅) for a not monotonic input predicate p of some external atom. To this end, we compute a partial grounding of a given HEXprogram by only considering the subset of (non-ground) rules that is relevant for obtaining all ground instances of p.

Definition 5. Given a predicate name p, a HEX-program Π, and a set S of predicate names, the relevant rules of Π wrt. p and S are relΠ(p, S) = ⋃r∈Πp {r} ∪ {r′ ∈ relΠ(p′ , S′ ) | p′ ∈ PB+(r), p′ ̸∈ S′ } where S′ = S ∪ {p}, Πp contains all rules of Π where p occurs in the head, and PB+(r) consists of all predicate names that occur in B+(r) either as ordinary atom predicate or as an input to an external atom. Furthermore, the relevant rules of Π wrt. p are defined by relΠ(p, ∅).

In order to obtain all instances of a predicate possibly true in some answer set of a program, we employ the following monotone grounding operator GΠ from [Eiter et al., 2016b]:

where rθ is the ground instance of r under variable substitution θ : V → C, ˆ I = {Ta | a ∈ I} ∪ {Fa | a ∈ HB \ I}, and A(Π′ ) is the set of all ordinary ground atoms occurring in Π′ . The least fixpoint of G∞Π (∅) contains all atoms that are true in some answer set of Π.

Example 4 (cont'd). We have G∞relΠ(p,∅)(∅)={d(c)← not a; p(c)←d(c)}, and a partial assignment AA is input-complete wrt. Π, if A ⊇ {p(c)}. Note that in general, G∞relΠ(p,∅) (∅) would not contain further rules on which p does not depend.

The rules in G∞relΠ(p,∅) (∅) contain all ground instances over p that occur in the grounding grd(Π) of Π. Since all atoms that occur in some answer set of Π also occur in grd(Π), the relevant grounding thus indicates all such atoms.

Proposition 3. Let Π be a HEX-program. If Tp(X) ∈ A, for some answer set A of Π, then p(X) occurs in G∞relΠ(p,∅) (∅).

Considering the relevant grounding of those predicates p that occur in Π as a not monotonic input to some external atom, i.e., considering the relevant grounding of all p ∈ pm(Π), we can obtain an input-safe domain of Π and thus obtain input-complete partial assignments. More formally,

Theorem 1. A partial assignment AA is input-complete wrt. a HEX-program Π if for all p ∈ pm(Π) it holds that p(X) ∈ A whenever p(X) occurs in G∞relΠ(p,∅) (∅).

4 Lazy-Grounding HEX-Evaluation Algorithm

In this section, we present the new evaluation algorithm that interleaves the steps taken by a lazy-grounding solver with the evaluation of external sources, which incrementally introduce new output constants into the program.

Given an input-safe domain A, the algorithm operates on top of a transformation from a HEX-program Π to an ordinary logic program α(Π, A), such that an ordinary lazy-grounding solver for ASP can be employed as a host to incrementally ground the rules in α(Π,A). Moreover, via a novel interface to external sources, lazy-grounding may import input-output relations over external atoms in form of additional rules.

In the program transformation α(Π, A), external atoms are replaced by ordinary atoms, and the program is extended by rules that allow to explicitly derive the negative extension of a given input-safe domain of Π.

Definition 6. Given a HEX-program Π and an input-safe domain A of Π, the ordinary program α(Π,A) results from Π by replacing each (non-ground) external atom &g[p](t) with an ordinary (non-ground) replacement atom e&g[p](t), and by adding for each p ∈ pm(Π) the rule

and for each p(X) ∈ A a domain fact pd(X) ←.

Without loss of generality, we assume that atoms of form e&g[p](t), p(X) and pd(X) do not occur in Π, i.e. they are fresh atoms.

The purpose of the program extension is twofold. On the one hand, it ensures that each atom p(X) in A is either derived to be true or explicitly false (via p(X)), so that in the end, nonmonotonic external atoms are always evaluated under complete assignments. On the other hand, enabling guessing the values of atoms in A early during the solving process potentially allows that outputs of nonmonotonic external atoms are derived earlier during search.

Example 5 (cont'd). Reconsider Π from Example 1. Given A = {p(c)}, the first rule is replaced by ← e&size[p](0) in α(Π, A), and we add {p(X) ← pd(X), not p(X); pd(c) ←}.

For interleaving the solving algorithm with the evaluation of external sources, we first define a means for constructing a partial assignment which is input-complete wrt. the given program, from an assignment A derived by the ASP solver.

Values of atoms that are true wrt. A are taken directly and false atoms are based on atoms of form p(X), which represent falsity of p(X) according to Definition 6. All other atoms in the domain are considered unassigned. Formally:

Definition 7. Given a partial assignment A and a domain A, the corresponding external input assignment is the set

Intuitively, the construction of an external input assignment from a given solver assignment ensures that atoms which have not been assigned a truth value during solving but which are in the given input-safe domain, are explicitly declared to be unassigned whenever an external source is queried. This is necessary because the external source requires information about all atoms which can potentially become true in the search later on, in order to only yield outputs that remain correct when the grounding is extended.

Note that if there is no atom p(X) s.t. Tp(X) ∈ A and Tp(X) ∈ A, then i(A,A) is a partial assignment. We assume that the previous holds for all external input assignments used in the following.

Example 6. Consider the partial assignment A = {Ta,Ub,Fc,Fd,Te} and domain A = {d, e, f}. The corresponding external input assignment is i(A,A) = {Ta,Ud,Fe,Uf}. Observe that i(A,A) only depends on the T-part of A and that i(A, A) is an assignment.

The external source interface amounts to a function that yields rules representing the corresponding input-output relations of external atoms. These rules are added to the input program processed by the solver. Accordingly, whenever an output value is obtained based on a solver assignment, a rule is generated that implies the ground replacement atom representing the respective output value relative to the current assignment of the relevant input atoms.

Definition 8. Given &g[p], a partial assignment A and a domain A, the external evaluation function η yields

where BA,p = {p′ (X) | Tp′ (X) ∈ A, p′ ∈ {p, p}, p ∈ p} is a rule body corresponding to the external atom's input.

We denote all possible such evaluations by η(Π) = {r | ∃A s.t. r ∈ η(&g[p], i(A,HB)), &g[p] occurs in Π}.

Example 7. Consider Π from Example 1 again. For inputsafe domain A = {p(c)} and A = {Td(c),Fa}, the external input assignment i(A,A) = {Td(c),Up(c)} is input-complete for Π, and η(&size[p], i(A,A))=∅. For the partial assignment A′={Td(c),Fa,Tp(c)}, we obtain i(A′ , A)={Td(c), Fp(c)} and η(&size[p], i(A′ , A)) = {e&size[p](0) ← p(c)}.

Algorithm 1 allows us to evaluate a HEX-program using lazy grounding. It is based on the lazy-grounding ASP solver ALPHA, which incorporates ideas from OMIGA [Dao-Tran et al., 2012; Weinzierl, 2017]. The algorithm combines conflictdriven nogood-learning (CDNL) search [Gebser et al., 2012] with lazy-grounding. CDNL applies techniques from SAT solving to ASP, by translating a ground program into a set of nogoods, corresponding to clauses in SAT solving, and running a DPLL-style search algorithm. In every iteration of the CDNL search procedure, deterministic consequences are propagated first, and in case some nogood is violated, a conflict nogood is added to the nogood store to avoid running into the same conflict again and backjumping is performed. Whenever no deterministic assignments are possible during CDNL search, but the solver assignment is still incomplete, an unassigned atom is guessed to be true or false.

Algorithm 1 receives as input an ordinary program constructed according to Definition 6 from a HEX-program Π and an input-safe domain of Π. In practice, we obtain an input-safe domain based on Definition 4 and Proposition 3, by computing G∞relΠ(p,∅) (∅) for all p ∈ pm(Π). Note that requesting an input-safe domain of the input program is not a severe restriction on the class of programs that our approach can handle, as an input-safe domain can be obtained for any HEX-program. After initializing, Algorithm 1 explores the search space in one loop, where the first step at each iteration is propagation from the currently known nogoods ∇ and the current assignment A in (a). If some nogood δ is violated, in (b), a new nogood is learned from the conflict and backjumping is done. If propagation at (a) derived new assignments, lazy-grounding of the input program is done in (c).

In (d), all external sources are queried, employing external evaluation functions and external input assignments. Note that, at this point, it cannot be the case that Tp(X) ∈ A and Tp(X) ∈ A both hold for any atom p(X), because atoms of the form p(X) are only defined by the rules added in the program transformation of Definition 6 and those rules only fire if Tp(X) ̸∈ A. In (e), guessing is done, which is different from ordinary CDNL-based guessing: due to the lazy-grounding, not all atoms may be guessed upon but only those corresponding to ground instances of applicable rules (cf. Sec. 3). Heuristics may be employed for selecting good guesses. Upon reaching (f), the iterations of lazy-grounding, guessing, and propagating do not yield any more information, i.e., a fixpoint has been reached. In order to complete the assignment (wrt. known atoms), all atoms being unassigned in A are assigned to false. In (g), the assignment is tested for only containing true or false assignments. This is necessary, because the ALPHA solver internally works with must-be-true as additional truth value for increased efficiency. For evaluation of external atoms, must-be-true is treated as true. If the check succeeds, then the current assignment is an answer set of the HEX-program and recorded as such. 2 If the check

2 In the implementation, false atoms of an answer set ˆA are not stored explicitly.

Algorithm 1: Lazy-Grounding HEX-Evaluation

fails, some must-be-true remained and the current assignment is not an answer set, hence backtracking occurs in (h).

If an external input-cycle would exist, i.e., an input predicate of an external atom depends on the atom itself (cf. [Eiter et al., 2014]), an additional minimality-check is required in (g), which is outside the scope of this work. Hence, in the following we assume programs Π do not have such cycles.

Algorithm 1 returns the answer sets of the program transformation together with all rules encoding possibly relevant input-output relations of external atoms:

Proposition 4. For HEX-program Π and input-safe domain A of Π, Algorithm 1 yields the answer sets of α(Π, A)∪η(Π).

Given a HEX-program Π and an input-safe domain A of Π, if Algorithm 1 returns an answer set of α(Π,A)∪η(Π), we obtain an answer set of Π by using for ordinary atoms occurring in Π the respective truth value and by setting all other atoms in HB to false. Observe that the resulting assignment maps all atoms of the form e&g[p](t), p(X) or pd(X) to false as they do not occur in Π. Moreover, each answer set of Π is obtained this way.

Theorem 2. For a HEX-program Π and an input-safe domain A of Π, the answer sets returned by Algorithm 1 correspond exactly to the answer sets of Π.

To show this result, we rely on the correctness and completeness of ordinary lazy-grounding ASP solving (cf. Theorem 1 in [Weinzierl, 2017]), which needs to be extended to also take external evaluations into account. As external atoms are evaluated under input-complete assignments only, it is ensured that input-output relations returned by the external evaluation function at any point during search are not contradicted by later external evaluations. Since no cyclic dependencies involving external atoms are allowed, their evaluation only depends on a subprogram that does not contain the respective external atom itself. Because of this, the Splitting

Figure 1: Consistent Preferences Rules

Theorem from [Eiter et al., 2016a] can be applied for proving correctness of Algorithm 1. Completeness intuitively follows from completeness wrt. ordinary programs and the fact that the truth values computed for replacement atoms by Algorithm 1 coincide with the outputs of the respective oracle functions, given identical assignments to ordinary atoms.

5 Implementation and Evaluation

To evaluate the performance of the new HEX-algorithm, we have integrated the ALPHA lazy-grounding solver, which is freely available, with the DLVHEX reasoner [Redl, 2016]. The two components communicate via the interface in Section 4, where DLVHEX bridges to external sources and handles program decomposition, while ALPHA acts as ordinary ASP solver. The program transformation in Definition 6 allows us to omit the usual guessing program [Eiter et al., 2016a] in the implementation. For comparison, we used DLVHEX with GRINGO and CLASP [Gebser et al., 2011b] as backends.

The tests were performed on a Linux machine with two 12core AMD Opteron 6176 SE CPUs and 128 GB RAM. The timeout for each run was 300 secs and the memory limit 12 GB. We used the HTCondor load distribution system 3 to ensure a stable environment that minimizes runtime variations between runs on the same problem instance.

Average runtimes of 10 instances per size (resp. 30 for benchmark #3) are reported in secs for computing all answer sets and one answer set (n=1); timeouts are in parentheses.

Benchmark Configurations. We compared three configurations: · splitting: the program is decomposed into independently groundable components, which are processed by an ordinary solver; · monolithic: a grounding of the complete program is generated, and an ordinary solver is run; · alpha: no program splitting happens and the novel algorithm using ALPHA is applied.

We expected alpha to perform better (i) than splitting, in case many guesses violate constraints and decomposition splits the latter from the guessing part; and (ii) better than monolithic, if generating the respective grounding before solving needs a lot of resources due to nonmonotonic external atoms. Furthermore, we hypothesized that lazy-grounding is beneficial if many constants are imported by value invention but only few of them occur simultaneously in an answer set.

3 http://research.cs.wisc.edu/htcondor

Consistent Preferences. This benchmark considers a problem where many new constants are imported by an external atom based on a guess, which obstructs intelligent grounding techniques. A HEX-program selects a subset P ′ of a pool P of persons p and checks if the union of individual preferences pref(p, I) ⊆ I×I over items I is consistent (i.e. acyclic). The answer sets of the rules from Figure 1 plus the facts {person(p) | p ∈ P} correspond to all P ′ ⊆ P where this holds. The item set I and the preferences pref(p, I) are not part of the HEX-program, but imported via an external atom &prefs[sel](X, Y ) for the selected persons. Its oracle function evaluates to true wrt. a partial assignment A and output (i, i′ ), if some p fulfills Tsel(p) ∈ A and (i, i′ ) ∈ pref(p, I); to false, if Fsel(p) ∈ A holds for all p s.t. (i, i′ ) ∈ pref(p, I); and to unassigned otherwise. Thus, the input parameter sel is monotonic, but evaluating the external atom under its maximal extension may cause a large amount of constants to be imported into the program.

We ran tests for randomly generated instances with n = 4, . . . , 24 persons and 2n items, where each individual preference (i, i′ ) uniformly occurs with 5% probability (Table 1). Generic Configuration. Using ASP for configuration has a long tradition (e.g. [Soininen et al., 2001] considered product configuration and more recently [Gebser et al., 2015] the railway domain). Here, we address a generic setting 4 that is likely to occur in real-world scenarios as those mentioned.

A configuration is a subset C ′ of a set C of components, which has an associated set m(C ′ ) ⊆ P of properties from a set P. An admissible C ′ must fulfill a set R of requirements (e.g. costumer demands) of the form (R+,R-) ∈ 2P ×2P , which means that R+ ⊆m(C ′ ) and R- ∩m(C ′ ) = ∅ holds.

In the HEX-program, we guess a configuration C ′ ⊆ C in a predicate config and compute its properties with an external atom &prop[config](P). As config is a nonmonotonic input parameter, traditional grounding must evaluate it for all possible inputs. For a partial configuration C ′ and property p, the oracle function is true, if p ∈ m(C ′′ ) for every C ′′ ⊇ C ′ ; false, if p /∈m(C ′′ ) for every C ′′ ⊇C ′ ; and unassigned else.

4 We exploit the benchmark implementation from https://github.com/ hexhex/core/tree/master/benchmarks/genericmapping.

We tested random instances with n = 10, . . . , 30 components, n/5+1 properties and up to 2n requirements, where a property occurs in a requirement with probability 30% and depends on a component with probability 10%; each property and requirement was added with probability 50% (Table 2).

Failure Diagnosis. Another classical use-case of logic programs is abduction-based diagnosis [Kakas et al., 1992]. Suppose possible causes of a machine failure should be given from certain (Boolean) measurement values that are only partially available. The task is to compute, respecting the open measurement values, all necessary causes that entail the measurement values. In that, information about combinations of failure causes that can be excluded is available.

This problem can be modeled 5 using sets M and M ′ of known resp. unknown measurements, a set H of possible causes, a logic program P relating measurements and possible causes, and a set C of constraints that exclude specific combinations of causes. We want to compute the intersection D of all possible diagnoses D ⊆ H wrt. measurement values M = M∪M ′′ with M ′′ ⊆ M ′ , s.t. D ̸⊆ C for all C ∈ C. For this, we guess M ′′ ⊆ M ′ in the HEX-program and employ a nonmonotonic external atom&diags[P,M](D) to obtain the necessary failure causes.

In the tests, we used random instances with n = 5, . . . , 50 measurement values, each available at 20% (e.g. due to unfinished measurements), and up to 2n constraints to exclude combinations of causes, where each occurs in a constraint with probability 30%. The results are shown in Table 3.

Findings. In all three benchmarks, lazy-grounding (setting alpha) exhibits a significant advantage in runtime over splitting and monolithic. This matches our hypotheses (i) and (ii) as under monolithic, the external atom must be grounded for exponentially many input combinations in the last two benchmarks, and under splitting, the search space cannot be pruned effectively due to the separation of guesses and constraints. We observe that splitting outperforms monolithic for Failure Diagnosis because computing the diagnoses is resource-intense and must be executed for every input during the grounding step. Here, this outweighs the costs related to less search space pruning in splitting. Note that in general, alpha finds the first answer set much faster than the other configurations, and notably, was very fast when no answer set exists. However, in computing all answer sets it often timed out when instances have a large number of solutions. Hence, with increasing instance size, the number of instances with many solutions has a stronger impact on the average runtimes for alpha. Methodologically, this suggests to restrict the solution space of a problem by adding further constraints when using lazy-grounding.

5 We adopt the setting implemented at https://github.com/hexhex/core/ tree/master/benchmarks/diagnosis.

Somewhat surprising, alpha outperformed monolithic for Consistent Preferences, despite feasible grounding for the instance sizes. Our analysis explains this by the large number of guesses usually added for evaluation of external atoms in HEX during grounding. Hence, considerably more time is required for solving. In contrast, no additional guesses must be introduced in our program transformation (Def. 6) as here the external atom only has monotonic input parameters and new constants can be imported on-the-fly.

The benchmark instances and all results are available at http://www.kr.tuwien.ac.at/research/projects/inthex/lazyhex.

6 Discussion and Conclusion

Related Work. Our work builds on partial evaluation of external atoms [Eiter et al., 2016c], and on the recently developed ALPHA solver [Weinzierl, 2017]. It is the first time that lazy-grounding has been considered for the HEX framework. We are not aware of similar approaches for related systems, such as CLINGO, which however, supports no value invention based on the respective answer set as HEX. Lazygrounding ASP solvers like ASPERIX [Lef`evre and Nicolas, 2009b], GASP [Pal`u et al., 2009], and OMIGA [Dao-Tran et al., 2012] could in theory be employed, but likely result in worse performance, as they are not based on CDNL-search.

Summary. We have introduced a new algorithm for HEXprograms that interleaves external evaluation plus value invention with lazy-grounding ASP solving. It employs a tailored interface between the two components with a program transformation based on input-safe domains and a novel evaluation function that adds rules for input-output relations over external atoms to the program. Monotonic external atoms are directly evaluated on partial groundings, with the benefit that no additional guesses are needed. Due to the black-box nature of external atoms, computing a restricted grounding wrt. not monotonic inputs is necessary; however, this usually involves only a small subset of the complete grounding.

The benchmark results of our prototype implementation are promising, and show the potential of the new algorithm based on the ALPHA solver. In the special setting of HEXprograms, lazy-grounding exhibits a significant benefit already for relatively small instances since program splits and guessing for monotonic external atoms can be avoided.

Outlook. We plan to integrate an advanced minimality-check into the algorithm, so that cycles over nonmonotonic external atoms can be treated. Moreover, an evaluation mixing full grounding and lazy-grounding, each for a different component of a given program, may increase overall performance.