selp: A Single-Shot Epistemic Logic Program Solver

2020·Arxiv

Abstract

Abstract

Epistemic Logic Programs (ELPs) are an extension of Answer Set Programming (ASP) with epistemic operators that allow for a form of meta-reasoning, that is, reasoning over multiple possible worlds. Existing ELP solving approaches generally rely on making multiple calls to an ASP solver in order to evaluate the ELP. However, in this paper, we show that there also exists a direct translation from ELPs into non-ground ASP with bounded arity. The resulting ASP program can thus be solved in a single shot. We then implement this encoding method, using recently proposed techniques to handle large, non-ground ASP rules, into the prototype ELP solving system “selp”, which we present in this paper. This solver exhibits competitive performance on a set of ELP benchmark instances.

1 Introduction Epistemic Logic Programs (ELPs), as deﬁned in (Shen and Eiter 2016), are an extension of the well-established formalism of Answer Set Programming (ASP). ASP is a generic, fully declarative logic programming language that allows us to encode problems in such a way that the resulting answers (called answer sets) directly correspond to solutions of the encoded problem (Brewka et al. 2011). Negation in ASP is generally interpreted according to the stable model semantics (Gelfond and Lifschitz 1988), that is, as negation-as-failure or default negation. The default negation ¬a of an atom a is true if there is no justiﬁcation for a in the same answer set, making it a “local” operator in the sense that it is deﬁned relative to the same answer set. ELPs, on the other hand, extend ASP with the epistemic negation operator not that allows for a form of meta-reasoning, that is, reasoning over multiple answer sets. Intuitively, an epistemically negated atom nota expresses that a cannot be proven true, that is, it is false in at least one answer set. Thus, epistemic negation is deﬁned relative to a collection of answer sets, referred to as a world view. The main reasoning task for ELPs, checking that a world view exists, is

Epistemic negation has long been recognized as a desired construct for ASP (Gelfond 1991; Gelfond 1994). In these works, Michael Gelfond introduced the modal operators K (“known” or “provably true”) and M (“possible” or “not provably false”), in order to address this need. Given an atom a, Ka and Ma stand for ¬nota and not¬a, respectively. Example 1 A classical example for the use of epistemic negation is the presumption of innocence rule innocent(X) ← notguilty(X), namely: a person is innocent if they cannot be proven guilty.

2 M. Bichler, M. Morak, and S. Woltran Renewed interest in recent years has revealed several ﬂaws in the original semantics, and several approaches (cf. e.g. (Gelfond 2011; Truszczynski 2011; Kahl 2014; del Cerro et al. 2015; Shen and Eiter 2016)) aimed to reﬁne them in such a way that unintended world views are eliminated. In this work, we will settle on the semantics proposed in (Shen and Eiter 2016). The ﬂurry of new research also led to the development of ELP solving systems (Kahl et al. 2015; Son et al. 2017). Such solvers employ readily available, highly efﬁcient ASP systems like clingo (Gebser et al. 2012; Gebser et al. 2014) and WASP (Alviano et al. 2013), especially making use of the former solver’s multi-shot solving functionality (Gebser et al. 2019). However, these ELP solving systems rely on ground ASP programs when calling the ASP solver, which, for reasons rooted in complexity theory, generally requires multiple calls in order to check for world view existence. The main aim of our paper is to present techniques and a system for solving ELPs that is able to utilize an ASP solver in such a way that the ELP can be solved in a single shot. Contributions. Our contributions in this paper are twofold: • We propose a novel translation from ELPs to ASP programs using large non-ground ASP rules, such that the ELP can be solved by an ASP solving system in a single shot. This is done via a recently proposed encoding technique (Bichler et al. 2016b) that uses large ASP rules to formulate complex checks. This technique builds on a result from (Eiter et al. 2007) that states that evaluating non-groundASP programs with bounded pred-

posed translation is therefore optimal from a complexity-theoretic point of view. From a practical point of view, such an encoding avoids multiple calls to the ASP solver. State-of-the-art systems use sophisticated heuristics and learning, and multiple calls might result in a loss of knowledge about the problem instance, which the solver has already learned. • We further discuss how our encoding needs to be constructed in order to be useful in practice. In particular, in current ASP systems, non-ground ASP programs ﬁrst need to be grounded, that is, all variables need to be replaced by all allowed combinations of constants. Since our encoding makes use of large non-ground rules, a naive grounding will often not terminate, since there may be hundreds or thousands of variables in a rule. However, as proposed in (Bichler et al. 2016b), we make use of the lpopt rule decomposition tool (Bichler et al. 2016a) that splits such large rules into smaller ones that are more easily grounded, by making use of the concept of treewidth and tree decompositions (Bodlaender 1993). To use this tool to its full potential, the large rules we use in our encoding must be constructed carefully, in order for lpopt to split them up optimally. • Finally, we present a prototype implementation of our ELP-to-ASP rewriting approach and combine it with the state-of-the-art ASP solving system clingo (Gebser et al. 2014) in order to evaluate its performance. We compare our system against EP-ASP (Son et al. 2017) on different benchmarks found in the literature. Our system shows competitive performance on these benchmarks, in particular on instances with good structural properties. The remainder of the paper is structured as follows: in Section 2 we introduce the formal background of ASP, ELPs, and tree decompositions; Section 3 states our reduction from ELPs to ASP, including practical considerations and a discussion of related work; Section 4 presents how QBF formulas can be encoded as ELP programs; Section 5 introduces our ELP solver; Section 6 presents our benchmark results, making use of results from Section 4; and ﬁnally Section 7 closes with some concluding remarks.

Theory and Practice of Logic Programming 3 This paper is an extended versions of (Bichler et al. 2018a; Bichler et al. 2018b). Additional material includes a full correctness proof for our reduction in Section 3 and a formalized and detailed description of the adaptations needed to make the reduction workable in practice. Further, Section 4 describes in detail how our QBF benchmarks, used in Section 6, are constructed. 2 Preliminaries Answer Set Programming (ASP). A ground logic program (also called answer set program, ASP program, or simply program) is a pair Π = (A ,R), where A is a set of propositional (i.e. ground) atoms and R is a set of rules of the form a1 ∨···∨al ← al+1,...,am,¬am+1,...,¬an; (1) where the comma symbol stands for conjunction, n ≥ m ≥ l ≥ 0 and ai ∈ A for all 1 ≤ i ≤ n. Each rule r ∈ R of form (1) consists of a head H(r) = {a1,...,al} and a body given by B+(r) = {al+1,...,am} and B−(r) = {am+1,...,an}. A literal ℓ is either an atom a or its (default) negation ¬a. A literal ℓ is true in a set of atoms I ⊆ A if ℓ = a and a ∈ I, or ℓ = ¬a and a ̸∈ I; otherwise ℓ is false in I. A set M ⊆ A is a called a model of r if B+(r) ⊆ M together with B−(r) ∩ M = /0 implies that H(r) ∩ M ̸= /0. We denote the set of models of r by models(r) and the models of a logic program Π = (A ,R) are given by models(Π) = �r∈R models(r). The GL-reduct ΠI of a ground logic program Π with respect to a set of atoms I ⊆ A is the program ΠI = (A ,{H(r) ← B+(r) | r ∈ R,B−(r) ∩I = /0}). Deﬁnition 2 (Gelfond and Lifschitz 1988; Gelfond and Lifschitz 1991) M ⊆ A is an answer set of a program Π if (1) M ∈ models(Π) and (2) there is no subset N ⊂ M such that N ∈ models(ΠM). The set of answer sets of a program Π is denoted AS(Π). The consistency problem of ASP

General non-ground logic programs differ from ground logic programs in that variables may occur in rules. Such rules are ∀-quantiﬁed ﬁrst-order implications of the form H1 ∨ ··· ∨ Hk ← P1,...,Pn,¬N1,...,¬Nm where Hi, Pi and Ni are (non-ground) atoms. A non-ground atom A is of the form p(t) and consists of a predicate name p, as well as a sequence of terms t, where each term t ∈ t is either a variable or a constant from a domain ∆, with |t| being the arity of p. Let var(A) denote the set of variables X in a non-ground atom A. This notation naturally extends to sets. We will denote variables by capital letters, constants and predicates by lower-case words. A non-ground rule can be seen as an abbreviation for all possible instantiations of the variables with domain elements from ∆. This step is usually explicitly performed by a grounder that transforms a (non-ground)logic program into a set of ground rules of the form (1). Note that, in general, such a ground program may be exponential in the size of the non-ground program. For non-ground programs of bounded arity, the consistency problem is Σ3P-complete (Eiter et al. 2007). Epistemic Logic Programs. A ground epistemic logic program (ELP) is a pair Π = (A ,R), where A is a set or propositional atoms and R is a set of rules of the following form:

where each ai is an atom, each ℓi is a literal, and each ξi is an epistemic literal, that is, a formula notℓ, where not is the epistemic negation operator, and ℓ is a literal. W.l.o.g. we assume that

4 M. Bichler, M. Morak, and S. Woltran no atom appears twice in a rule1. Let elit(r) denote the set of all epistemic literals occurring in a rule r ∈ R. This notation naturally extends to programs. Let H(r) = {a1,...,ak}. Let B(r) = {ℓ1,...,ℓm,ξ1,...,ξj,¬ξj+1,...,¬ξn}, that is, the set of elements appearing in the rule body. In order to deﬁne the main reasoning tasks for ELPs, we recall the notion of the epistemic reduct (Shen and Eiter 2016). Let Φ ⊆ elit(Π) (called a guess). The epistemic reduct ΠΦ of the program Π = (A ,R) w.r.t. Φ consists of the rules {r¬ | r ∈ R}, where r¬ is deﬁned as the rule r with all epistemic literals notℓ in Φ (resp. in elit(Π)\Φ) replaced by ⊤ (resp. ¬ℓ). Note that ΠΦ is a logic program without epistemic negation2. This leads to the following, central deﬁnition. Deﬁnition 3 Let Φ be a guess. The set M = AS(ΠΦ) is called a candidate world view of Π iff 1. M ̸= /0, 2. for each epistemic literal notℓ ∈ Φ, there exists an answer set M ∈ M wherein ℓ is false, and 3. for each epistemic literal notℓ ∈ elit(Π)\Φ, it holds that ℓ is true in each answer set M ∈ M . Example 4 Let Π be the following ELP, with R = {r1,r2}: r1 : p ← notq r2 : q ← not p ELP Π has two candidate world views: (1) Φ = {notq} with AS(ΠΦ)={{p}}; (2) Φ = {not p} with AS(ΠΦ)={{q}}. □ The main reasoning task we treat in this paper is the world view existence problem (or ELP consistency), that is, given an ELP Π, decide whether a candidate world view exists. This problem

Tree Decompositions. A tree decomposition of a graph G = (V,E) is a pair T = (T,χ), where T is a rooted tree and χ is a labelling function over nodes t, with χ(t) ⊆ V, such that the following holds: (i) for each v ∈ V there is a node t in T such that v ∈ χ(t); (ii) for each {v,w} ∈ E there is a node t in T such that {v,w} ⊆ χ(t); and (iii) for all nodes r, s, and t in T, where s lies on the path from r to t, χ(r)∩ χ(t) ⊆ χ(s). The width of a tree decomposition T is deﬁned as the maximum cardinality of χ(t) minus one, over all nodes t of T . The treewidth of a graph G is the minimum width over all tree decompositions of G. Trees have treewidth 1, cliques of size k have treewidth k. Finding a tree decomposition of minimal width is NP-hard in general. 3 Single-Shot ELP Solving In this section, we provide our novel translation for solving ELPs via a single call to an ASP solving system. The goal is to transform a given ELP Π to a non-ground ASP program Π′ with

Theory and Practice of Logic Programming 5 predicates of bounded arity, such that Π is consistent (i.e. it has a candidate world view) iff Π′ has at least one answer set. A standard ASP solver can then decide the consistency problem for the ELP Π in a single call, by solving Π′. 3.1 Reducing ELPs to ASP Programs The reduction is based on an encoding technique proposed in (Bichler et al. 2016b), which uses large, non-ground rules. Given an ELP Π, the ASP program Π′ will roughly be constructed as follows. Π′ contains a guess part that chooses a set of epistemic literals from elit(Π), representing a guess Φ for Π. Then, the check part veriﬁes that, for Φ, a candidate world exists. In all, the ASP program Π′ consists of ﬁve parts:

part of the program that checks Condition i of Deﬁnition 3. We now proceed to the construction of the program Π′. Let Π = (A ,R) be the ELP to reduce from. To ease notation, let A =

facts, and is given as: • atom(a), for each atom a ∈ A ; • elit(ℓ), for each epistemic literal notℓ ∈ elit(Π)3; • leq(0,0), leq(0,1), and leq(1,1), representing the less or equal relation for Boolean values; and • or(0,0,0), or(0,1,1), or(1,0,1), and or(1,1,1), representing the Boolean relation or.

Sub-Program . This part of the program consists of a single, non-ground rule that guesses

a subset of the epistemic literals (stored in predicate g) as follows: g(L,1)∨g(L,0) ← elit(L). Shorthands. Before deﬁning the three check parts of the program, we will introduce some useful shorthands which will be used at several occasions. To this end, we use a context identiﬁer C . We ﬁrst deﬁne the following:

that is, Hguesses a truth assignment for some variable A and stores it in relation v. We

will often use variables X = {X1,...,Xn} or Y = {Y1,...,Yn} to represent a subset M of A , where assigning Xi to 1 characterizes ai ∈ M, and Xi = 0 otherwise. Let

vC (ai,Xi),

that is, Bextracts the truth assignment from relation vinto the variables X as described

above. Finally, for some rule r in Π, we deﬁne a formula Brsat(X,Y,S) that checks whether the

6 M. Bichler, M. Morak, and S. Woltran rule r is satisﬁed in the epistemic reduct ΠΦ w.r.t. the guess Φ encoded in the relation g, when the negative body (resp. positive body and head) is evaluated over the set of atoms encoded by

X (resp. Y). If the rule is satisfied, Brsat(X,Y,1) should hold, and Brsat(X,Y,0) otherwise. This

is done as follows. Let r contain the atoms {ai1,...,aim} (recall that no atom appears twice in a rule), where i1,...,im ∈ {1,...,n}. For ease of notation, we will use a four-ary or relation, which can easily be split into two of our three-ary or atoms using a helper variable T: or(W,X,Y,Z) ← or(W,X,T),or(T,Y,Z). The following is the central building block of our reduction:

or(R j−1,1−Yij,R j), �

g(aij,Nj),or(Nj,1−Xij,Tj),or(R j−1,1−Tj,R j),

g(¬aij,Nj),or(Nj,Yij,Tj),or(R j−1,1−Tj,R j),

g(aij,Nj),or(R j−1,Nj,1−Yij,R j),

g(¬aij,Nj),or(R j−1,Nj,Xij,R j). For a rule r, each big conjunction in the above formula encodes a reason for r to be satisﬁed. For example, the ﬁfth line encodes the fact that rule r is true if the disjunct ¬notaij is not satisﬁed, that is, if the epistemic literal notaij is part of the guess Φ, or the atom aij is false (represented by 1−Yij). Each disjunct of rule r is evaluated in this way, and the results are connected via the or relation (with the result of the ﬁrst i disjuncts stored in variable Ri). Therefore, Rm will be 1 if r is satisﬁed, and 0 otherwise, as desired (recall that r has m disjuncts). The following example illustrates how this shorthand is constructed for a concrete input program. Example 5 Recall program Π = (A ,R) from Example 4. Let A = {a1,a2}, where a1 = p and a2 = q. Let rule r2 ∈ R contain the atoms {ai1,ai2}, where i1 = 2 and i2 = 1. We give the core construct,

Br2sat(X1,X2,Y1,Y2,R2) ≡ or(0,Y2,R1),g(p,N2),or(N2,1−X1,T2),or(R1,1−T2,R2).

Finally, we deﬁne Bss(X,Y), which makes sure that the variables Y identify a strict subset of the atoms identiﬁed by X. Let Bss(X,Y) ≡ N0 = 0,Nn = 1, �

leq(Yi,Xi),or(Ni−1,Xi−Yi,Ni). We can now proceed with the remainder of our reduction.

Theory and Practice of Logic Programming 7

Sub-Program 1. This part of the program needs to check that, given the guess made in , there exists at least one answer set of the epistemic reduct , as per Definition 3(1).

Therefore, according to Deﬁnition 2, we need to ﬁnd a set M ⊆ A , such that (1) M is a model of ΠΦ, and (2) there is no proper subset of M that is a model of the GL-reduct (ΠΦ)M. Π′check1 contains the following rules: • Hcheck1val (A) ← atom(A);

The ﬁrst rule guesses a truth assignment for all atoms. The second rule veriﬁes that there is no rule in ΠΦ that is violated by the candidate answer set M, represented by the variables X, guessed

end, let

Y is indeed a model of every rule in the GL-reduct (ΠΦ)M. This completes Π′check1.

epistemic reduct ΠΦ has some answer set wherein ℓ is false. Π′check2 contains the following rules and facts, for each epistemic literal notℓ ∈ elit(Π) (used as the context C so guesses are independent):

• vℓ(a,η), where η = 1 if ℓ = ¬a, or η = 0 if ℓ = a;

These rules guess, for each epistemic literal notℓ ∈ Φ, a candidate answer set M wherein ℓ is false, and then verify that M is indeed an answer set, using the same technique as in Π′check1. This ensures Condition 2 of Deﬁnition 3.

elit(Π) \ Φ, every answer set of ΠΦ satisﬁes ℓ. The construction makes use of the technique of saturation (Eiter and Gottlob 1995): • Hcheck3val (A) ← atom(A); • vcheck3(A,0) ← sat,atom(A); • vcheck3(A,1) ← sat,atom(A); and

This setup checks that, for every candidate answer set M guessed in the ﬁrst rule, the atom sat is derived. Since we are only interested in answer sets, we ﬁrst check that M is indeed one, using the following rules, similarly to Π′check1:

8 M. Bichler, M. Morak, and S. Woltran

• sat ← Bcheck3red . It now remains to check that in each answer set M (that is, where sat has not been derived yet) all epistemic literals notℓ are either in Φ, or otherwise ℓ is true in M. This is done by adding the following rule to Π′check3: sat ← �

g(a,Na),vcheck3(a,Xa),or(Na,Xa,1),

This completes the reduction. We will now show that this reduction indeed accomplishes our goals. The correctness of our reduction can be intuitively seen from the observation that each of the three check parts of the constructed ASP program Π′ ensures precisely one of the three conditions that deﬁne a candidate world view. Each answer set A of Π′ is a witness for the fact that a guess Φ ⊆ elit(Π) encoded in A indeed gives rise to a candidate world view. The next theorem formally states that our reduction is correct. Theorem 6 Let Π = (A ,R) be an ELP and let Π′ be the ASP program obtained from Π via the above reduction. Then, Π has a candidate world view if and only if Π′ has an answer set. Proof We will begin with the “if” direction. To this end, assume that there is a guess Φ ⊆ elit(Π) for Π that gives rise to a candidate world view M = AS(ΠΦ). We will show that Π′ has an answer set

each epistemic literal notℓ ∈ Φ and the fact g(ℓ,0) for each epistemic literal notℓ ∈ elit(Π)\ Φ. This clearly satisﬁes sub-program Π′guess. Now, let M′ ∈ M be any answer set of ΠΦ (such an answer set exists, since, by assumption, M is a candidate world view for Φ and by Deﬁnition 3, M is non-empty). Let M contain the fact vcheck1(a,1) for each a ∈ M′ and the fact vcheck1(a,0) for each a ∈ A \ M′. This satisﬁes

atoms with relation vcheck1 encode precisely the answer set M′ of ΠΦ, and since M′ is a model of ΠΦ, also the second line of the sub-program is satisﬁed, which, by construction, checks that the assignment encoded in relation vcheck1 satisﬁes all the rules of ΠΦ. Finally, the third line, by construction, checks that the same assignment is also minimal w.r.t. the GL-reduct [ΠΦ]M′. Since M′ is an answer set of ΠΦ, also this line of the sub-program Π′check1 is satisﬁed.

didate world view for guess Φ, it contains, for each epistemic literal notℓ ∈ Φ, an answer set Mℓ ∈ M such that ℓ is false in Mℓ. Thus, the argument for sub-program Π′check1 can be analogously applied for each notℓ ∈ Φ, taking the answer set Mℓ instead of M′. Finally, we need to verify that M also satisﬁes the rules in Π′check3. To this end, let M contain the facts Mcheck3 consisting of the fact sat, as well as the fact vcheck3(a,b) for each a ∈ A and b ∈ {0,1}. It is easy to verify that all the rules in Π′check3 are classically satisﬁed. However, since

Theory and Practice of Logic Programming 9 the negative literal ¬sat appears in line 4, in order to verify that M is indeed an answer set, we also need to look at minimality w.r.t. GL-reduct. Since line 4 is removed in the GL-reduct of

However, we will show that every such subset requires sat to be true via lines 5, 6, or 7 of Π′check3

subset of Mcheck3 \ {sat} that does not encode an answer set of ΠΦ in relation vcheck3 derives sat via lines 5 or 6, by construction (the argument to see this is analogous to the one for the previous two sub-programs). It remains to show that all other remaining subsets (i.e. the subsets of Mcheck3 \ {sat} that encode answer sets of ΠΦ) also derive sat. However, since every answer set M′ ∈ M , by Deﬁnition 3, has to satisfy precisely the condition encoded by line 7 of Π′check3, this is easy to see. We thus have that M, as constructed above, is indeed an answer set of Π′. The “only if” direction can be seen via similar arguments to the above. By construction, any answer set M of Π′ will encode a guess Φ for Π. Since any such answer set M, to be an answer set, must satisfy the three check sub-programs of Π′ in the way described above, and these three check sub-programs, by construction, correspond directly to the three conditions of Deﬁnition 3, we have that M encodes a guess Φ for Π that leads to a candidate world view. As we have seen, our reduction works as intended: the ASP program Π′ derived from the input ELP Π has an answer set precisely when Π has a candidate world view. The next interesting observation is that our reduction is, in fact, a polynomial-time reduction, as stated below. Theorem 7 Given an ELP Π, the reduction above runs in time O(e · n), where n is the size of Π and e = |elit(Π)|, and uses predicates of arity at most three. Proof Predicates of arity at most three are used if the four-ary or relation is not materialized as an actual relation in ASP, but viewed as a shorthand for two connected ternary or relations (cf. the paragraph on shorthands of our reduction). The reduction’s runtime (and output size) can be seen to be in O(e · n) by noting the fact that the construct Bred is of size linear in n (it precisely encodes each rule using the or predicates). Bred is then used once for each epistemic literal in Π (cf. Π′check2). Note that the above theorem shows that our reduction is indeed worst-case optimal as claimed in Section 1: checking consistency of non-ground, ﬁxed-arity ASP programs is Σ3P-complete, as is checking world view existence for ELPs. 3.2 Using the Reduction in Practice As we have seen, using the construction in the previous subsection, we can solve the consistency problem for a given ELP via a single call to an ASP solving system. However, when trying this in practice, the performance is less than optimal, mainly for the following reason. At several points in the construction, large non-ground rules are used (i.e. where BCred appears in a rule body). As noted in Section 2, these rules need to be grounded, but may contain hundreds or thousands of variables, which need to be replaced by all possible combinations of constants; a hopeless task for ASP grounders, as the resulting ground program is exponential in the number of variables.

10 M. Bichler, M. Morak, and S. Woltran

Fig. 1: Creating a grid from chains.

However, as noted in (Bichler et al. 2016b), such large rules can often be decomposed into smaller, more manageable rules, using the lpopt tool (Bichler et al. 2016a). This tool roughly works as follows: (1) compute a rule graph Gr for each non-ground rule r, where there is a vertex for each variable V in r, and there is an edge between V1 and V2, if the two variables appear together in an atom of r; then (2) compute a tree decomposition of Gr of minimal width; and ﬁnally, (3) in a bottom-up manner, output a rule for each node in the tree decomposition. The resulting rules each contain only as many variables as the treewidth of Gr (plus one), and, together, are equivalent to the original rule r. After this rule decomposition step, grounding now becomes much easier, since the number of variables in each rule is reduced. Note that, since ﬁnding optimal tree decompositions is NP-hard, lpopt employs heuristics to ﬁnd good decompositions.

ELP Π. Each atom ai in Π is represented by the two variables Xi and Yi. If we represent Π as a graph GΠ, where each atom ai is a vertex, and there is an edge between two atoms if they appear together in a rule in Π, then this graph structure can be found (as a minor) in the rule

that introduce additional connections in the rule graph of BCred. These connections may increase the treewidth substantially. In fact, even if GΠ has a treewidth of 1, by introducing the additional connections in a bad way, the treewidth may increase arbitrarily: imagine that GΠ is a chain, depicted in black in Figure 1, and imagine the or(·,·,·)-chain from Bss(X,Y) is inserted into GΠ, illustrated in pink. The treewidth now depends on the chain’s length (and thereby on the size of Π), and lpopt can no longer split the rule well. In the following, we will formalize the problem described above and present an extension to our reduction presented in the previous subsection that will alleviate the problem. First, we deﬁne the primal graph of an ELP Π, a standard notion in topics of satisﬁability, constraint programming,and logic programming; cf. standard textbooks, e.g. (Ebbinghaus and Flum 1995). Deﬁnition 8 The primal graph of an ELP Π = (A ,R) is the graph GΠ = (V,E), where V = A and there is an edge (ai,a j) ∈ E iff the atoms ai and a j occur together in a rule in R. Then, we deﬁne the rule graph for a non-ground ASP rule r: Deﬁnition 9 The rule graph of a non-ground ASP rule r is the graph Gr = (V,E), such that V = var(r), and there is an edge between two variables X and Y in E iff X and Y occur together in an atom in r. From the construction, it is not difﬁcult to see that any rule r containing BCred reﬂects the structure of the input ELP Π, or, more formally, the graph GΠ is contained (as a minor) in the graph Gr. Thus, by well-known graph-theoretic results, the treewidth of Gr is at least the treewidth of GΠ. Since this is an integral part of our construction, we cannot hope for lpopt to split up rule r any better than the structure of Π allows. However, as noted in the intuitive problem description above, Gr contains additional connections between variables. These are introduced by the subformula Bss(·,·) that effectively links all the variables in a rule r into a chain in Gr.

Theory and Practice of Logic Programming 11 In the worst case, as illustrated by Figure 1, these additional connections in Gr may increase the treewidth arbitrarily, making it almost impossible for lpopt to split up the rule well. It is therefore important to introduce these additional connections carefully. We will now introduce a more involved construction of Bss(·,·) that preserves the treewidth of GΠ in Gr (i.e. does not arbitrarily increase it). In this modiﬁed version, Bss(·,·) is constructed as follows: 1. First, compute a tree decomposition TΠ of GΠ with minimal width. 2. Secondly, construct Bss(·,·) in a bottom-up (i.e. post-order traversal) fashion along this tree decomposition in the following way, for each node type. To this end, let A = {a1,...,an}, and, for a node t of TΠ, let χ(t) contain the set of atoms {ai1,...,aim}, with ij ∈ {1,...,n}. Leaf Node t: For a leaf node t of TΠ, let Bss(X,Y) contain the following conjunction of atoms:

leq(Yij,Xij),or(Ntj−1,Xij −Yij,Ntj), that is, Nt contains 1, if the proper subset condition between X and Y is already fulﬁlled in node t, and 0 otherwise. Inner Node t: For an inner node t of TΠ with children t1,...,tk, let Bss(X,Y) contain the same conjunction as for a leaf node, but where the equality atom Nt = Ntm is replaced by the following disjunction:

where the k+2-ary or atom can be split into 3-ary or atoms in the same way as with the 4-ary or atom in our main construction. Intuitively, we now have that Nt is set to 1 if the proper subset condition is already fulﬁlled somewhere in the subtree rooted at t. Root Node troot: Finally, for the root node troot, we add the same conjunction of atoms to Bss(X,Y) as for an inner node, but, in addition, we add the ﬁnal condition Ntroot = 1, that makes sure that, at the root node, the proper subset condition is fulﬁlled. If constructed in the way described above, it is not difﬁcult to see that Bss(X,Y) still ensures the same condition as in our original construction from Section 3.1, namely, that the variables Y identify a proper subset of the atoms identiﬁed by the variables X. However, the treewidth of a rule containing Bss(·,·) is now not increased arbitrarily. In fact, it can be veriﬁed that the treewidth of GΠ is preserved up to a constant additive factor, for any rule containing BCred, when using the alternative construction for Bss(·,·) provided above. In practice, this means that lpopt is able to split the rule up as well as possible; that is, as well as the structure of Π allows. 3.3 Discussion and Related Work As we have seen, the reduction proposed above allows us to solve ELPs via a single call to an ASP solving system. However, our encoding also has several other interesting practical properties, which make it very ﬂexible for use with, for example, different ASP semantics, or harder problems. A brief discussion follows. Other ASP Semantics. Apart from the original semantics for ASP (called stable model semantics, (Gelfond and Lifschitz 1988; Gelfond and Lifschitz 1991)), several different semantics have been proposed that investigate how to interpret more advanced constructs in ASP, like double negation, aggregates, optimization, etc (Lifschitz et al. 1999; Pearce 2006; Pelov et al. 2007;

12 M. Bichler, M. Morak, and S. Woltran Ferraris et al. 2011; Faber et al. 2011; Shen et al. 2014). Epistemic reducts may contain double negation, and we have opted to use the FLP semantics by Faber et al. (2011), as used by Shen and Eiter (2011), to interpret this. The actual interpretation of double negation is encoded in the

modiﬁed to use different ASP semantics (e.g. (Lifschitz et al. 1999)). Enumeration of World Views. Modern ASP systems like clasp (Gebser et al. 2012) contain several useful features not included in the ASP base language. One such feature is an advanced implementation of projection, as presented in (Gebser et al. 2009): given a set of atoms (or relations), the solver will output answer sets where all other atoms are projected away, and will also guarantee that there are no repetitions (even if multiple answer sets with the same assignment on the projected atoms exist), while still maintaining efﬁciency. This can be used to enumerate candidate world views by projecting away all relations in our encoding, except for g(·) and vcheck1(·). When enumerating all projected answer sets in this way, our encoding yields all guesses together with their candidate world views (when grouped by g(·)). Comparison to Related Work. Classic ELP solvers generally work by ﬁrst establishing a candidate epistemic guess Φ and then use an answer set solver to verify that the epistemic guess indeed yields an epistemic reduct whose answer sets form a candidate world view of the original ELP w.r.t. Φ. Different approaches are used to ﬁnd promising epistemic guesses, and also to verify that they lead to candidate world views, but, generally, these systems have in common that an underlying ASP solver is used, and called multiple times, to solve the ELP. Notable recent ELP solvers include that follow this approach include EP-ASP (Son et al. 2017), GISolver (Zhang et al. 2015) and a later, probabilistic, variant called PelpSolver, and ELPsolve (Kahl et al. 2016). A comprehensive survey of recent ELP solving systems (including the one presented in the present paper) can be found in (Leclerc and Kahl 2018). We are not aware of another single-shot ELP solver that only needs to call an underlying ASP system once. However, the idea of our approach is similar to the one used by Bichler et al. (2016b), where a single-shot ASP encoding for disjunctive ASP, which is rewritten into non-ground normal ASP with ﬁxed arity, is presented. That is, a solving system for normal ASP would be able to solve a disjunctive ASP program in a single call. However, this approach was not implemented, and only presented as an example to show how long non-ground rules with ﬁxed arity can be used to solve hard problems. In order to use such encodings (including our own presented herein), (Bichler et al. 2016b) make use of rule decomposition, where large non-ground ASP rules are split up into smaller parts based on tree decompositions (Morak and Woltran 2012). This rule decomposition approach has been implemented as a stand-alone tool called lpopt (Bichler et al. 2016a), but has recently also been integrated into ASP solving systems like I-DLV (Calimeri et al. 2017). 4 Application: QBF Solving In this section, we illustrate the power of ELPs by illustrating a way to solve QBF formulas with at most three quantiﬁer alternations (3-QBF) by encoding them as ELPs. This provides an

alternative way to show the lower bound for ELP consistency, but relies on the existence

of a reduction from so-called restricted 3-QBF formulas. (Shen and Eiter 2016) present such a reduction from restricted 3-QBF formulas to ELP world view existence. Our aim is to generalize

Theory and Practice of Logic Programming 13 this by presenting a reduction from (general) 3-QBF formulas to restricted 3-QBF formulas. We will use this result to benchmark our ELP solver presented in Section 5. Let us begin by ﬁrst recalling the deﬁnition of such 3-QBF formulas. Deﬁnition 10 A 3,∃-QBF in CNF form (or QBF, for short) is a formula of the form

where X, Y, and Z are sets (or sequences) of distinct (propositional) atoms (also called variables),

Li,j is either an atom a or its negation ¬a. W.l.o.g. we can assume that the clause size ki = 3 for each 0 < i ≤ k, that is, that ϕ is given in 3-CNF form, where each clause has at most three elements. In (Shen and Eiter 2016), the authors make use of a version of QBFs called restricted QBFs. These are QBFs that evaluate to true under all interpretations of the existentially quantiﬁed variables if all universally quantiﬁed variables are replaced by ⊤ (i.e. if they are set to true). Deﬁnition 11 A restricted QBF is a QBF where ϕ[y/⊤ | y ∈ Y] is a tautology. The hardness proof of Theorem 5 of (Shen and Eiter 2016) is a reduction from the validity problem of restricted QBFs to the consistency problem of epistemic logic programs. While the actual construction of the reduction is not needed for our purposes in this section, we nevertheless report it here, for completeness sake. Proposition 12 (Shen and Eiter 2016, Proof of Theorem 5) Let Θ = ∃X∀Y∃Zϕ be a restricted QBF. Then, there exists an ELP Π such that Π has a candidate world view iff Θ is satisﬁable. Proof The ELP Π consists of the following rules: • For each variable X ∈ X: X ← not X, X ← notX. • For each variable Y ∈ Y:

• For each variable Z ∈ Z:

Z. • For each clause Ci, 0 < i ≤ k:

where ∗ is an operator that converts a positive literal W intoW, and a negative literal ¬W into W. • For each Z ∈ Z: Z ← U, Z ← U. • And, ﬁnally, the rule V ← notV,not¬U. ELP Π has a (candidate) world view iff ∃X∀Y∃Zϕ is satisﬁable (Shen and Eiter 2016).

14 M. Bichler, M. Morak, and S. Woltran We now show a more general reduction that also works for the non-restricted case. To this end, we will combine the (Shen and Eiter 2016) reduction with our own reduction of QBF formulas to restricted QBF formulas. To achieve our goal, we are going to introduce one new atom vi in each clause Ci and ∀-quantify these new atoms together with the Y atoms. Deﬁnition 13 Given a QBF Θ = ∃X∀Y∃Zϕ with ϕ being constructed as in Deﬁnition 10, let its extension, denoted Θ↑, be the QBF

where

and V = {v1,...,vk} is a list of fresh atoms. It is easy to see that any extension Θ↑ of a QBF Θ is a restricted QBF. Proposition 14 Let Θ be a QBF. Its extension Θ↑ is a restricted QBF. We will now show that validity-equivalence between a QBF and its extension is preserved. For the proof, we establish the following terminology: given a subset of atoms σ ⊆ S, we deﬁne its out-setσ = {¬a | a ∈ S\ σ} and its literal-set �σ = σ ∪

Proposition 15 Θ and Θ↑ are validity-equivalent. Proof (⇒) Assume Θ is valid, i.e. there exists an interpretation σX ⊆ X, such that for any interpretation σY ⊆ Y there exists an interpretation σZ ⊆ Z such that (�σX ∪ �σY ∪ �σZ) ∩Ci ̸= /0 for all i ∈ {1,...,k}. By monotonicity of non-emptiness of set intersections, also (�σX ∪ �σY ∪ �σV ∪ �σZ)∩ (Ci ∪{vi}) ̸= /0 for any interpretation σV ⊆ V of a list of new atoms V = {v1,...,vk}. But this is proof of the validity of Θ↑. (⇐) For the other direction, assume Θ↑ is valid, i.e. there exists an interpretation σX ⊆ X such that for any interpretations σY ⊆ Y and σV ⊆ V there exists an interpretation σZ ⊆ Z such that (�σX ∪ �σY ∪ �σV ∪ �σZ)∩(Ci ∪{vi}) ̸= /0 for all i ∈ {1,...,k}. By setting σV = /0, we especially get that there exists an interpretation σX ⊆ X such that for any interpretation σY ⊆ Y there exists an interpretation σZ ⊆ Z such that (�σX ∪ �σY ∪ {¬v1,...,¬vk} ∪ �σZ) ∩ (Ci ∪ {vi}) ̸= /0 for all i ∈ {1,...,k}. Since the only literals containing a vi variable on the left-hand side of the ∩ are negative and the only ones on the right-hand side are positive, we get (�σX ∪ �σY ∪ �σZ)∩Ci ̸= /0 for all i ∈ {1,...,k}, which establishes validity of Θ. Now it is straightforward to generalize the reduction from (Shen and Eiter 2016): let Θ be a QBF and apply the reduction from (Shen and Eiter 2016) to the restricted QBF Θ↑. Theorem 16 Let Θ be a QBF. Let the ELP ΠΘ be obtained by applying the reduction by Shen and Eiter (2016) to the restricted QBF Θ↑. It holds that Θ is valid iff ΠΘ is consistent, that is, ΠΘ has at least one candidate world view. Correctness of this theorem follows from immediately from Proposition 12 and Proposition 15.

Theory and Practice of Logic Programming 15 5 The selp System We implemented the reduction in Section 3 as part of the single shot ELP solving toolbox selp, available at https://dbai.tuwien.ac.at/proj/selp. In addition, the toolbox features a grounder for ELPs and a grouping script which groups answer sets of the reduction into candidate world views (allowing for enumeration). The tools are implemented in python and depend on the parser generator LARK4, the rule decomposition tool lpopt (Bichler et al. 2016a), the tree decomposition tool htd_main (Abseher et al. 2017), and the plain ASP grounder gringo (Gebser et al. 2011). Input Formats. The selp solver reads the EASP-not ﬁle format, which is a restriction of the ASP input language of gringo to plain ground logic programs as deﬁned in Section 2, extended with the $not$ operator for epistemic negation. This allows us to encode ELPs as deﬁned in Section 2. selp also supports EASP-KM, deﬁned by adding the operators K$ and M$ instead of $not$. By allowing variables in body elements, both formats also have a non-ground version. The toolbox offers scripts to translate between the two formats. Toolbox. We brieﬂy present the main building blocks of selp. easpGrounder.py takes as input a non-ground EASP-not program and outputs its equivalent ground form by rewriting it into an ASP program that the gringo grounder can understand and ground. This is done by encoding epistemic negation as predicate names and, after grounding, re-introducing epistemic negation where a placeholder predicate appears. Our grounding component, easpGrounder.py, supports arithmetics and the sorts format (Kahl et al. 2015) as input. easp2asp.py is selp’s key component. It takes a ground EASP-not program, performs the reduction given in Section 3.1 (with some modiﬁcations to account for the extended language of ASP used by today’s ASP systems and some straightforward optimizations), also adhering to the practical considerations presented in Section 3.2, and it ﬁnally outputs the resulting non-ground logic program in the syntax of gringo. Optionally, additional clasp directives are generated to allow for enumeration; cf. Section 3.3. For concrete implementation details, please consult the

groupWorldViews.py takes clasp’s output in JSON format, groups the answer sets into candidate world views according to their g(·) atoms, and outputs them in a human-readable format. Usage. As a typical use case, suppose the ﬁle problem.easp contains a non-ground ELP encoding of a problem of interest and the ﬁle instance.easp contains a problem instance. In order to output all candidate world views, one would use the following command (ﬂags -pas and --project enable projection of answer sets onto relevant predicates only. -n0 tells clasp to compute all answer sets, and --outf=2 to print in JSON format. lpopt is used to decompose long rule bodies. The --sat-prepro=3 ﬂag is recommended by lpopt):

16 M. Bichler, M. Morak, and S. Woltran

Fig. 2: Benchmark results. Missing points indicate timeouts.

6 Experimental Evaluation We tested our system selp against the state-of-the-art ELP solver, EP-ASP (Son et al. 2017), using three test sets. For every test set, we measured the time it took to solve the consistency problem. For selp, clasp was stopped after ﬁnding the ﬁrst answer set. For EP-ASP, search was terminated after ﬁnding the ﬁrst candidate world view5. Note that a single answer set of the selp system is enough to establish consistency of an input ELP. EP-ASP needs to compute a full candidate world view to be able to prove consistency. Experiments were run on a 2.1GHz AMD Opteron 6272 system with 224 GB of memory. Each process was assigned a maximum of 14 GB of RAM. For EP-ASP, we used the required clingo 4.5.3, since newer versions are incompatible with the solver. For selp, we used clingo 5.2.2, htd_main 1.2.0, and lpopt 2.2. The time it took EP-ASP to rewrite the input to its own internal format was not measured. EP-ASP was called with the preprocessing option for brave and cautious consequences on, since it always ran faster this way. The selp time is the sum of running times of its components. Benchmark Instances. We used three types of benchmarks, two coming from the ELP literature and one from the QSAT domain that contains structures of low treewidth6. Scholarship Eligibility (SE). This set of non-ground ELP programs is shipped together with EP-ASP. Its instances encode the scholarship eligibility problem for 1 to 25 students. Yale Shooting (YS). This test set consists of 25 non-ground ELP programs encoding a simple version of the Yale Shooting Problem, a conformant planning problem: the only uncertainty is whether the gun is initially loaded or not, and the only ﬂuents are the gun’s load state and whether the turkey is alive. Instances differ in the time horizon. We follow the ELP encoding from (Kahl et al. 2015).

Theory and Practice of Logic Programming 17 Tree QBFs (TQ). The hardness proof for ELP consistency (Shen and Eiter 2016) relies on a reduction from the validity problem for restricted quantiﬁed boolean formulas with three quantiﬁer blocks (i.e. 3-QBFs), which can be generalized to arbitrary 3-QBFs as discussed in Section 4. We apply this extended reduction to the 14 “Tree” instances of QBFEVAL’16 (Pulina 2016),

available at http://www.qbflib.org/family_detail.php?idFamily=56, split-

ting each instance’s variables into three random quantiﬁer blocks. Results. The results for the ﬁrst two sets are shown in Figure 2. selp solves all instances from (SE) within 30 seconds, while EP-ASP only solves 17 within the time limit of 8 hours. For (YS), on the other hand, selp is able to solve only 6 instances within the time limit of 30 minutes, whereas EP-ASP can solve 17. Finally, for (TQ), selp can solve 6 of the 14 instances within the time limit of 12 hours, whereas EP-ASP was unable to solve any instances at all. These results conﬁrm that selp is highly competitive on well-structured problems: in the (SE) instances, knowledge about students is not interrelated, and hence the graph GΠ of the ground ELP Π consists of one component for each student, thus having constant treewidth. The (TQ) instances keep their constant treewidth thanks to the fact that both the reduction from QBF to ELP (cf. Section 4) and from ELP to non-ground ASP (cf. Section 3.2) preserve the low treewidth of the original QBF instance. Different from selp, EP-ASP is not designed to exploit such structural information of ELPs and, consequently, performs worse than selp in these benchmarks. On the other hand, (YS) contains instances of high treewidth, even though it does not depend on the horizon. EP-ASP is therefore able to outperform selp on such instances. A similar observation can be made for the “Bomb in the Toilet” problem, as benchmarked in (Son et al. 2017), which inherently contains a huge clique structure. selp is not designed to solve such instances, and is therefore most suited to solve ELPs of low treewidth, where it is able to efﬁciently exploit the problem structure. 7 Conclusions In this paper, we have seen that ELPs can be encoded into ASP programs using long non-ground rules, such that a single call to an ASP solver is sufﬁcient to evaluate them. A prototype ELP solver implementation, selp, performs particularly well on problems whose internal structure is of low treewidth. A combined solver that either calls selp or another state-of-the-art solver based on the treewidth of the input may therefore lead to even better overall performance. Another topic for future work is that, under the FLP semantics, checking whether a given atom a is true in all candidate world views with a subset-maximal guess Φ is known to be Σ4P-complete (Shen and Eiter 2016). To solve this problem, advanced optimization features of state-of-the-art ASP solvers could allow us to encode this subset-maximality condition, while leaving the core of our encoding unchanged. Finally, an interesting question is program optimization. Recently, a practical, easily applicable notion of strong equivalence for ELPs has been deﬁned (Faber et al. 2019). It would be interesting to investigate if and how parts of ELPs can be replaced in such a way that the solving performance of selp improves, seeing that selp is sensitive to treewidth. This could lead to an encoding technique for ELPs that tries to minimize the treewidth, similar to the class of connectionguarded ASP (Bliem et al. 2017), which was recently proposed in order to write ASP programs in such a way as to keep the treewidth of the resulting ground program low.

18 M. Bichler, M. Morak, and S. Woltran Acknowledgements This work was funded by the Austrian Science Fund (FWF) under grant numbers Y698 and P30930. References

ABSEHER, M., MUSLIU, N., AND WOLTRAN, S. 2017. htd - A free, open-source framework for (cus-

tomized) tree decompositions and beyond. In Proc. CPAIOR. 376–386. ALVIANO, M., DODARO, C., FABER, W., LEONE, N., AND RICCA, F. 2013. WASP: A native ASP solver

based on constraint learning. In Proc. LPNMR. 54–66. BICHLER, M., MORAK, M., AND WOLTRAN, S. 2016a. lpopt: A rule optimization tool for answer set

programming. In Proc. LOPSTR. 114–130. BICHLER, M., MORAK, M., AND WOLTRAN, S. 2016b. The power of non-ground rules in answer set

programming. TPLP 16, 5-6, 552–569. BICHLER, M., MORAK, M., AND WOLTRAN, S. 2018a. Single-shot epistemic logic program solving. In

Proc. IJCAI. 1714–1720. BICHLER, M., MORAK, M., AND WOLTRAN, S. 2018b. Single-shot epistemic logic program solving. In

Proc. ASPOCP. BLIEM, B., MOLDOVAN, M., MORAK, M., AND WOLTRAN, S. 2017. The impact of treewidth on ASP

grounding and solving. In Proc. IJCAI. 852–858. BODLAENDER, H. L. 1993. A tourist guide through treewidth. Acta Cybern. 11, 1-2, 1–21. BREWKA, G., EITER, T., AND TRUSZCZYNSKI, M. 2011. Answer set programming at a glance. Commun.

ACM 54, 12, 92–103. CALIMERI, F., FUSCÀ, D., PERRI, S., AND ZANGARI, J. 2017. I-DLV: the new intelligent grounder of

DEL CERRO, L. F., HERZIG, A., AND SU, E. I. 2015. Epistemic equilibrium logic. In Proc. IJCAI. 2964–2970.

EBBINGHAUS, H.-D. AND FLUM, J. 1995. Finite Model Theory. Springer Monographs in Mathematics. Springer, Berlin, Heidelberg.

EITER, T., FABER, W., FINK, M., AND WOLTRAN, S. 2007. Complexity results for answer set programming with bounded predicate arities and implications. Ann. Math. Artif. Intell. 51, 2-4, 123–165.

EITER, T. AND GOTTLOB, G. 1995. On the computational cost of disjunctive logic programming: Propositional case. Ann. Math. Artif. Intell. 15, 3-4, 289–323.

FABER, W., MORAK, M., AND WOLTRAN, S. 2019. Strong equivalence for epistemic logic programs made easy. In Proc. AAAI.

FABER, W., PFEIFER, G., AND LEONE, N. 2011. Semantics and complexity of recursive aggregates in answer set programming. Artif. Intell. 175, 1, 278–298.

FERRARIS, P., LEE, J., AND LIFSCHITZ, V. 2011. Stable models and circumscription. Artif. Intell. 175, 1, 236–263.

GEBSER, M., KAMINSKI, R., KAUFMANN, B., AND SCHAUB, T. 2012. Answer Set Solving in Practice. Morgan & Claypool.

GEBSER, M., KAMINSKI, R., KAUFMANN, B., AND SCHAUB, T. 2014. clingo = ASP + control: Preliminary report. In ICLP Tech.Comm.

GEBSER, M., KAMINSKI, R., KAUFMANN, B., AND SCHAUB, T. 2019. Multi-shot ASP solving with clingo. TPLP 19, 1, 27–82.

GEBSER, M., KAMINSKI, R., KÖNIG, A., AND SCHAUB, T. 2011. Advances in gringo series 3. In Proc. LPNMR. 345–351.

GEBSER, M., KAUFMANN, B., AND SCHAUB, T. 2009. Solution enumeration for projected boolean search problems. In Proc. CPAIOR. 71–86.

GEBSER, M., KAUFMANN, B., AND SCHAUB, T. 2012. Conflict-driven answer set solving: From theory to practice. Artif. Intell. 187, 52–89.

GELFOND, M. 1994. Logic programming and reasoning with incomplete information. Ann. Math. Artif. Intell. 12, 1-2, 89–116.

GELFOND, M. AND LIFSCHITZ, V. 1988. The stable model semantics for logic programming. In Proc. ICLP/SLP. 1070–1080.

GELFOND, M. AND LIFSCHITZ, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Comput. 9, 3/4, 365–386.

KAHL, P. T. 2014. Refining the semantics for epistemic logic programs. Ph.D. thesis, Texas Tech University, Texas, USA.

KAHL, P. T., LECLERC, A. P., AND SON, T. C. 2016. A parallel memory-efficient epistemic logic program solver: Harder, better, faster. In Proc. ASPOCP.

KAHL, P. T., WATSON, R., BALAI, E., GELFOND, M., AND ZHANG, Y. 2015. The language of epistemic specifications (refined) including a prototype solver. J. Log. Comput., exv065.

LECLERC, A. P. AND KAHL, P. T. 2018. A survey of advances in epistemic logic program solvers. CoRR abs/1809.07141.

LIFSCHITZ, V., TANG, L. R., AND TURNER, H. 1999. Nested expressions in logic programs. Ann. Math. Artif. Intell. 25, 3-4, 369–389.

MORAK, M. AND WOLTRAN, S. 2012. Preprocessing of complex non-ground rules in answer set programming. In ICLP Tech.Comm. 247–258.

PELOV, N., DENECKER, M., AND BRUYNOOGHE, M. 2007. Well-founded and stable semantics of logic programs with aggregates. TPLP 7, 3, 301–353.

PULINA, L. 2016. The ninth QBF solvers evaluation - preliminary report. In Proc. QBF. CEUR Workshop Proceedings, vol. 1719. CEUR-WS.org, 1–13.

SHEN, Y. AND EITER, T. 2016. Evaluating epistemic negation in answer set programming. Artif. Intell. 237, 115–135.

SHEN, Y., WANG, K., EITER, T., FINK, M., REDL, C., KRENNWALLNER, T., AND DENG, J. 2014. FLP answer set semantics without circular justifications for general logic programs. Artif. Intell. 213, 1–41.

SON, T. C., LE, T., KAHL, P. T., AND LECLERC, A. P. 2017. On computing world views of epistemic logic programs. In Proc. IJCAI. 1269–1275.

TRUSZCZYNSKI, M. 2011. Revisiting epistemic specifications. In Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning - Essays Dedicated to Michael Gelfond on the Occasion of His 65th Birthday. 315–333.

ZHANG, Z., WANG, B., AND ZHANG, S. 2015. Logic programming with graded introspection. In Proc. ASPOCP.