We introduce resilient logic programs that couple a nonmonotonic logic program and a rst-order theory or description logic (DL) ontology. Unlike previous hybrid languages, where the interaction between the program and the theory is limited to consistency or query entailment tests, in RLPs answers must be `resilient' to the models of the ontology, allowing non-output predicates to respond di erently to di erent models. RLPs can elegantly express 989-QBFs, disjunctive ASP, and con guration problems under incompleteness of information. To guarantee decidability, we use a novel relaxation of DL-safeness that safeguards rules via predicates whose extensions can be inferred to have a nite bound. We present algorithms and tight complexity results for the case where ontologies are written in some prototypical DLs.
Description Logics (DLs) [
Motivated by this complementarity, combining DLs and rule-based languages
into the so-called Hybrid Knowledge Bases (HKBs) is a well-established
research topic in KR&R [
For many KR problems both extremes are inadequate. We thus study HKBs that blur the lines between the model-centric and the entailment-centric approaches: di erent models of the input ontology may be processed in di erent ways, in the model-centric spirit, but the intended answer sets are de ned via universal quanti cation over the models of the ontology, as in entailment-centric approaches. For a simple (synthetic) example, assume we want to generate a directed graph G from a given set of nodes n1; : : : ; nk, so that removing one node from the graph will always lead to graph that is strongly connected. Intuitively, here selecting which edges to include in G depends on the universal quanti cation over all induced subgraphs G0 obtained by removing a single node from G, while the reachability relation in G0 is di erent for di erent choices of G0.
In our formalism, resilient logic programs (RLPs), a standard ASP program P is paired with a rst-order theory (or a DL ontology) T that challenges it. Predicates are divided into output, response, and open-world predicates. The semantics is de ned via a \negotiation" between P and T : the two components need to agree on answer sets I over the output signature, so that no matter how I is extended into a model of T (by interpreting the open-world predicates), the program P can give a matching and justi ed interpretation to the response predicates. Both 989-QBFs and disjunctive ASP are naturally captured by RLPs, and in fact, the QBF reduction shows that reasoning is 3P -hard in data complexity, setting RLPs apart form previous hybrid languages. We illustrate that RLPs are powerful for solving incompletely speci ed con guration problems.
Inevitably, reasoning in RLPs is undecidable unless restrictions are imposed on
how rules are allowed to manipulate anonymous objects. While the usual notion
of DL-safeness can be used [
Due to space limitations some constructions and proofs are provided the extended version of this paper 1. 2
We assume countably in nite and mutually disjoint sets Sconst, Svar, and Spred of constants, variables, and predicate symbols, respectively. Each p 2 Spred is associated with a non-negative arity, denoted by art (p). A term is a variable or 1 https://dbai.tuwien.ac.at/staff/simkus/papers/dl2019-long.pdf a constant, and an atom is an expression p(t1; : : : ; tn), where p 2 Spred has arity n, and t1; : : : ; tn are terms. A program is a set of rules of the form r : h
b1; : : : ; bn; not bn+1; : : : ; not bm where n; m 0, h; b1; : : : ; bm are atoms, and each variable that occurs in h; bn+1; : : : bm must occur in some b1; : : : ; bn. We let head (r) = fhg, body +(r) = fb1; : : : ; bng, and body (r) = fbn+1; : : : ; bmg. If p is an atom, we call an expression of the form not p a negated atom. A literal is an atom or a negated atom. A rule r is positive if jbody (r)j = 0. A program is positive if all its rules are positive. We call an atom, a rule, or a program ground if it contains no variables. Facts are ground rules of the form h , where \ " is often omitted. We let adom(P) be the set of constants in P. Given a set of constants C Sconst, the grounding of a rule w.r.t. C, in symbols ground (r; C), is a set of rules obtained from r by uniformly replacing variables in r by all possible elements from C. The grounding of a program w.r.t. C is then given as ground (P; C) = Sr2P ground (r; C).
An (Herbrand) interpretation over Spred is a set of ground atoms using only predicates from (if is not speci ed we assume = Spred). Given an interpretation I and a set Spred, we let Ij = fp(u) j p(u) 2 I and p 2 g.
An interpretation I is a model of a ground positive program P if body +(r) I
implies head (r) \ I 6= ;, for each rule r 2 P. Further, I is a minimal model of P
if there exists no J I that is a model of P. The semantics to programs with
negation is given using a program transformation due to Gelfond and Lifschitz [
We introduce our formalism. Syntactically, it pairs a program with a function-free rst order logic (FO) theory|as usual in hybrid languages|and also de nes a partition of the signature, which is relevant for our resilient semantics.
Given a program P and a theory T , we use sig(P) and sig(T ) to denote sets of predicate symbols that occur in P and T , respectively.
De nition 1 (Syntax). A resilient logic program (RLP) is a tuple = (P; T ; out; owa; re) where P is a program, T is an FO theory, and the sets out, owa, re are a partition of sig(P) [ sig(T ) with re \ sig(T ) = ;. We call out the set of output predicates, owa the open predicates, and re the response predicates of . The predicates in out [ re are called closed predicates of .
Our semantics uses the following generalized de nition of a reduct. It is
inherited from Clopen KBs [
Given a program P, an interpretation I, and Spred, the reduct PI; of P w.r.t. I and is the positive program obtained from ground (P; Sconst) by: 1. Deleting every rule r that contains a literal p(u) such that (a) p(u) 2 body+(r), p(u) 62 I, and p 2 (b) p(u) 2 head (r), p(u) 2 I, and p 2 (c) p(u) 2 body (r) and p(u) 2 I.
, , or 2. In the remaining rules, deleting all negated atoms and atoms p(u) with p 2 . Intuitively, PI; is the result of partially evaluating P according to the facts in I, under the open-world assumption for the predicates in .
Now we can de ne the semantics of RLPs. For convenience, we adopt the standard Herbrand semantics of FO theories.
De nition 2 (Semantics). Let = (P; T ; out; owa; re) be an RLP, and let I be an interpretation over out. Then I is an answer set of if (i) there exists some model J of T such that Ij out = Jj out , and (ii) for each model J of T with Ij out = Jj out , there is an interpretation H such that Jj out[ owa = Hj out[ owa and Hj out[ re is a minimal model of PH; owa . We call H a response to J w.r.t. I and .
The main reasoning task for RLPs is answer set existence, i.e., given an RLP , does there exist an answer set I of . Other common reasoning problems like skeptical (resp., brave) entailment can be easily reduced to checking non-existence (resp., existence) of an answer set. In particular, a ground atom p(c) is true in all answer sets of (i.e. p(c) is a skeptical consequence) i the result of adding p(c) to (the program component of) does not have an answer set.2 Similarly, a ground atom p(c) is true in some answer set of (i.e. p(c) is a brave consequence) i augmented with not p(c) does have an answer set.
We illustrate RLPs. For brevity, we use h1j jhk as a shorthand for the set of rules fhi ; not h1; : : : not hi 1; not hi+1; : : : ; not hk j 1 i kg. This choice rule tells us that at least one of h1; ; hk must be true in case is true. Example 1. We show how to express the graph problem from the introduction as an RLP. Given nodes n1; : : : ; nk, let = (P; T ; fV; Eg; fE; Rg; fin; out g), where T = f8x(V (x) ! in(x) _ out (x)); 8x(V (x) ! :in(x) _ :out (x)); 9xout (x); 8x8y out (x) ^ out (y) ! x = yg and the program P consists of the following rules: V (n1);
V (nk); E(x; y)jE(x; y) ; R(x; z) R(x; y); R(y; z);
R(x; y) E(x; y); not out (x); not out (y)
V (x); V (y); x 6= y; not out (x); not out (y); not R(x; y)
Then each answer set of is true for all nodes ni, 1 is still strongly connected.
i de nes a directed graph G such that the following
k: if ni is removed from G, the remaining graph 2 The constraint ` ' is a shorthand for `p ; not p', where p is a fresh atom.
Example 2. Consider the evaluation problem for quanti ed Boolean formulas (QBFs) of the form = 9X1; : : : ; Xn8Y1; : : : ; Ym; 9Z1; : : : ; Zk':, where ' is in 3CNF. The quanti er alternation resembles the semantics of our RLPs, as re ected in the following RLP , which has an answer set i evaluates to true. We let
= (P; T ; fVX ; VY ; VZ ; TX ; FX g; fTY ; FY g; fTZ ; FZ g) with T = f 8x(VY (x) ! TY (x) _ FY (x));
8x(VY (x) ^ TY (x) ^ FY (x) ! ?)g P = f VX (c1X ); : : : ; VX (cnX );
VY (c1Y ); : : : ; VY (cYm); VZ (c1Z ); : : : ; VZ (ckZ ) TX (x)jFX (x)
VX (x);
TZ (x)jFZ (x)
VZ (x); (Li;1); (Li;2); (Li;3); for each clause Ci in 'g where, given a literal l, (l) is de ned as: (l) = (T (ci ) if l = : i; i = 1; : : : ; n
F (ci ) if l = i; i = 1; : : : ; n where
2 fX; Y; Zg, nX = n; nY = m, and nZ = k.
In the extended version, we use a slightly modi ed reduction to show that answer set existence is p3-hard in data-complexity for many classes of RLPs.
We note that there is a strong connection between RLPs and disjunctive logic
programs with negation under the answer set semantics [
This section focuses on RLPs whose theory is a DL TBox. We consider ALCHI, ALCHOIQ, and DL-LiteF , de ned as usual. We assume Scn [ Srn Spred and Sin Sconst where Scn, Srn, and Sin denote respectively the set of concept names, the set of role names, and the set of individual names. As for FO theories, also for DLs we use Herbrand interpretations. Recall that an Herbrand interpretation I can be viewed as an ordinary DL interpretation I = ( I ; I ), where I = Sconst and pI = fc j p(c) 2 Ig for each p 2 Scn [ Srn.
RLPs in their general form are undecidable. This is not hard to show adapting
analogous results for some well-known hybrid languages [
This restriction ensures that variables only take on those constants that are explicitly mentioned in P. However, this is often too strong. We relax it by safeguarding variables with positive literals whose predicate is a bounded concept name. De nition 4. Let T be an ALCHOIQ TBox, Spred be a nite set of predicate symbols, and N = ffcg j c occurs in T g. The set Bcn(T ; ) of bounded concept names in T w.r.t. is the smallest set such that: 1. if A is a concept name in \ sig(T ) then A 2 Bcn(T ; ) 2. if A is a concept name in sig(T ) and there is a role name P in sig(T ) \ s.t.
T A v 9P:> or T A v 9P :>, then A 2 Bcn(T ; ) 3. if A is a concept name in sig(T ) and T A v FB2B[N B, then A 2 Bcn(T ; ) 4. if A is a concept name in sig(T ) and there exists B 2 Bcn(T ; ) [ N , a role R occurring in T , and integers n; m 0 s.t. T A v mR:B and T B v nR :A, then A 2 Bcn(T ; ) If T is in ALCHI, item 4. in the de nition above is omitted and N = ;. Similarly, if T is in DL-LiteF , item 3. is omitted and item 4. is replaced by the following: 4a. if A is a concept name in sig(T ) and there exists B 2 Bcn(T ; ) and a role R occurring in T s.t. T A v 9R , T 9R v B, and (funct R) 2 T , then A 2 Bcn(T ; ).
Note that, given T and , computing the set Bcn(T ; ) requires a polynomial
number of steps, some of which use an entailment test as an oracle. A similar
computation for bounded concepts is done in [
Proposition 1. Let T be a TBox in one of the considered DLs, Spred, and b 0. Then, we can compute b0 0 s.t. jfc j A(c) 2 J; A 2 Bcn(T ; )gj b0 holds in every model J of T in which jfc j p(c) 2 J; p 2 ; c occurs in cgj b. If T is in ALCHOIQ, b0 is at most exponential in the size of T . For ALCHI and DL-LiteF , b0 is polynomial in the size of T .
We remark that the de nition above is incomplete, in the sense that Bcn(T ; )
need not contain all concept names for which a bound exists. Nonetheless, it is
su cient to relax our previous notion of safeness. To this end, given a program
P, for each p 2 sig(P) and 1 i art (p), we de ne a position p[i]. Given a set
of predicates , the set ap(P; ) of a ected positions (see [
A predicate symbol occurring in an RLP = (P; T ; out; owa; re) is called a bounded predicate if it is (i) a closed predicate or (ii) in Bcn(T ; out). We now relax the safeness condition from De nition 3 as follows: De nition 5. An RLP = (P; T ; out; owa; re) ful lls the relaxed safeness condition if the following holds for each rule r 2 P: each variable in r must also occur in some atom p(u) 2 body+(r) where p is a bounded predicate in and, additionally, q[i] 62 ap(P; Bcn(T ; out) n out), for all q 2 out and 1 i art (q). Example 3. Assume a company wants to process a certain amount of customer orders per day. Incoming orders will consist of tasks, and the tasks will be associated with services that are o ered by the company (active services). The company needs to decide which services it should o er, so that for all the possible con gurations of received orders (including the tasks they comprise and the services they require, which are not yet known), they can schedule tasks to employees in such a way that all tasks are nished in the working day.
This problem is solved by an RLP where the models of the theory correspond to possible con gurations of received orders, and the models of the program de ne viable schedules of tasks. Its answer sets correspond to sets of services that, if activated, guarantee that for any con guration of received orders there is a schedule in which each task will be completed before the end of the working day. We rst model the time line of a work day as follows:
P1 = fNext(0 ; 1 ); Next(1 ; 2 ); : : : ; Next(tmax 1 ; tmax ) Time(x)
Next(x; y); Time(y)
Next(x; y); Earlier (x; y) less10 (x0; xn)
Next(x; y); Earlier (x; z)
Earlier (x; y); Earlier (y; z); Next(x0; x1); : : : ; Next(xn 1; xn); for 0 n < 10g P1 also contains rules for less30 and less60 , de ned similarly as for less10 . Assuming that employees work eight hours per day and that the granularity of Next is one minute, we set tmax = 480.
As facts, we store our employees (Employee), the services that could be o ered (Service), as well as which employee can provide which service (Provides). We also store the length of each service. For simplicity reasons we consider three types of services: short, medium, and long, captured by unary relations Short , Medium, and Long, respectively. Short services take ten minutes, medium-length services 30 minutes, and long services takes 60 minutes to be completed. Assume our company receives two orders per day. We also encode this information using facts. Finally, it is reasonable to assume that for a given order there might be services that need to be completed before other services can be performed. We store this information using a binary relation ServiceBefore and once again, facts. Consider, for demonstration purposes, the following set of facts: P2 = fService(s1); Service(s2); Service(s3); Employee(e1); Employee(e2); Provides(e1; s1); Provides(e1; s2); Provides(e2; s1); Provides(e2; s3);
We do not know how orders will comprise tasks, and which services these tasks will require. We only know that orders consist of at least one and at most ve tasks (Task ), each belonging to exactly one order and requiring (Req ) one service. The possible con gurations of orders are given by the models of this theory: T = fOrder v
Task v = 1hasTask :Order Task v = 1Req:>;
The rules that select services to be provided are de ned as follows: P3 = fActiveService(x)jInactiveService(x)
We look for schedules (Sched ) consisting of tuples (x; y; z), assigning task y to employee x to be performed starting at time point z. These rules populate the response predicates, trying to nd viable schedules for the di erent models of the theory. Due to space restrictions, we show only the rules for short services. P4 = fSched (x; y; z)
Illegal (x; y; z) Illegal (x; y; z) Illegal (x; y; z) Illegal (x; y; z) FaultyServ (x0) FaultyServ (x0) OKService(x)
Task (y); Req(y; u); Provides(x; u); Time(z); not Illegal (x; y; z) Task (y); Req(y; u); Short(u); Time(z); less10 (z; tmax); Employee(x) Sched (x0; y; z0); less10 (z0; z); Req(y; u); Short(u); Employee(x); x 6= x0 Sched (x; y; z0); less10 (z0; z); Req(y; u); Short(u); z 6= z0 Task (y); Sched (x; y0; z0); less10 (z0; z); Req(y0; u); Short(u); y 6= y0 Order (z); Task (y); Task (y0); hasTask (z; y); hasTask (z; y0); Req(y; x); Req(y0; x0); Before(x; x0)Sched (w; y; t); Sched (w0; y0; t0); Earlier (t0; t) Order (z); Task (y); Task (y0); hasTask (z; y); hasTask (z; y0); Sched (w; y; t); Sched (w0; y0; t0); Req(y; x); Short(x); Req(y0; x0); Before(x; x0); less10 (t; t0) not FaultyServ (x); Service(x) not OKService(x); ActiveService(x)
OKTask (y) Sched (x; y; z) not OKTask (y); T ask(y)g Let P = P1 [ P2 [ P3 [ P4 and out = fOrder ; ActiveServiceg. The RLP = (P; T ; out; sig(T ) n out; sig(P) n ( out [ owa)) ful lls the relaxed safeness condition and its answer sets represent sets of services that can be o ered and completed within the given time constraint regardless of the type of received orders. E.g., I = fActiveService(s1); ActiveService(s2); Order (o1); Order (o2)g is an answer set of . In the worst case, both orders consist of ve tasks each that in turn require a medium-length service s2. A valid schedule in this case is: Sched (e1; y1; 0), Sched (e1; y2; 20) : : : ; Sched (e1; y10; 180). Note that, unlike traditional ASP, we can have comparable answer sets, e.g., fActiveService(s1); Order (o1); Order (o2)g is also an answer set of .
Consider J = fActiveService(s3); Order (o1); Order (o2)g and a model of T in which each order consist of ve tasks associated with the long service s3. Since only employee e2 can perform s3, she would have to perform it ten times, thus taking more than 480 minutes. Hence, there is no valid schedule and J is not an 5
Algorithm 1 decides answer set existence for a given = (P; T ; out; owa; re). In a nutshell, it guesses a candidate interpretation I and subsequently uses two oracle calls to check whether I is an answer set of . The rst call checks whether there are any models of T that agree with I on out. The second call tries to verify whether each such model of T has a response w.r.t. I and by attempting to guess a model J of T for which this does not hold. In order to check that J has no response, another oracle call is made which attempts to nd a response by guessing it. If this fails, J is a counter example to I being an answer set of .
Assuming RLPs ful ll (relaxed) safeness condition, we have the following: Proposition 2. Let = (P; T ; out; owa; re) be an RLP and let I be an answer set of . For every c 2 Sconst occurring in I, c 2 adom(P) holds. Proposition 3. Let = (P; T ; out; owa; re) be an RLP , I and J be interpretations over and sig(T ), resp. Let J 0 = fp(c) 2 J j p 2 owa \ sig(P); c 2 art(p)g, where is the set of constants that occur in P or in some q(a) 2 J with q 2 Bcn(T ; out). Then J and J 0 have the same responses w.r.t. I and .
Due to Proposition 2, the maximum number of di erent constants occurring in some answer set of is bounded by jadom(P)j. In view of Proposition 1, we can thus compute an integer b that limits the amount of di erent constants that can be in the extension of any concept name in Bcn(T ; out) in any model of T that agrees with some answer set of on out, referred to as a relevant model of T . We construct a set of size b consisting of adom(P), constants occurring in T and additionally of fresh constants giving a name to each anonymous element that could hypothetically occur in the extension of some A 2 Bcn(T ; out) in some relevant model of T . Checking whether there are models of T that agree with I on out is a well-known problem in the literature and it boils down to checking the consistency of a description logic knowledge base (T ; I) in the presence of closed predicates from out, where I is seen as an ABox. In view of Proposition 3, to nd a model of T with no response we only guess the extensions of open predicates that occur in P using the constants from . We next check whether our partial guess J actually corresponds to some model of T and if so, we check whether there is a response H to J . Due to our safeness condition, for this guess it su ces to consider only the constants from J and adom(P). Note that to verify whether H is a response to J , we need not fully compute the possibly in nite reduct PH; owa . Instead, we use the reduct ground (P; )H; owa which is guaranteed to be nite and has the same minimal model as the original reduct.
As reasoning in the considered logics in the presence of closed predicate is
decidable [
Algorithm hasAnswerSet( )
Input : An RLP = (P; T ; out; owa; re) Output : true i has an answer Guess an interpretation I over out using constants from adom(P) B Bcn(T ; out) b max number of di erent const. in extensions of bounded concept names adom(P) [ fc j c occurs in T g [ fa1; : : : ; ab b0 g, where b0 = jadom(P)j + jfc j c occurs in T gj return isConsistent(T ; I; out) and not hasCE(I; ; ; B) Subroutine hasCE(I; ; ; B)
Input : An interpretation I, an RLP = (P; T ; out; owa; re),
Sconst, and B sig(T ) Output : true i there is a counter example to I being an answer set of Guess an interpretation J over sig(P) \ sig(T ) [ out and constants from s.t. Jj out = Ij out J 0 J [ f:p(c) j c 2 art(p); p 2 sig(P) \ (sig(T ) n B); and p(c) 62 J g return isConsistent(T ; J 0; B) and not hasResp(J; ) Subroutine hasResp(J; )
Input : An interpretation J and an RLP = (P; T ; out; owa; re) Output : true i there is a response for J w.r.t. Jj out and Guess an interpretation H over sig(P) and the constants from J and adom(P) s.t. Hj out[ owa = J if Hj out[ re is a min. model of PH; owa then return true else return false Algorithm 1: Answer set existence of RLPs. Here isConsistent(T ; I; ) checks consistency of DL KB (T ; I) with closed predicates .
We brie y guide the reader through the entries in this table. Observe that for
predicates of arbitrary arities, I is at most exponential in jPj, and consider the
logic ALCHI. In view of Proposition 1, is polynomial in j j and thus there are
only exponentially many di erent guesses for J . As ALCHI with closed predicates
is ExpTime-complete [24,25], we modify the algorithm to do the following in
exponential time: guess I, compute Bcn(T ; out), construct and check whether
there is a model of T that agrees with I on out. If so, iterate through possible
guesses for J and check for each whether it corresponds to some model. If so, call
an oracle to determine whether there is a response H to J . Due to unbounded
predicate arities, both H and the grounding ground (P; ) may be at most of
exponential size. Thus, we can guess H, compute the corresponding reduct and
verify whether Hj out[ re is its minimal model in exponential time. Observe that,
by the standard padding argument [
ALCHI ALCHOIQ NExpTimeNP- c NExpTimeNP- c NExpTimeNExpTime
ExpTime - c 3P - c 3P - c 3P - c
immediate. As DL-LiteF with closed predicates is in NP both in data and in
combined complexity [
All bounds for DL-LiteF and ALCHI are tight. ExpTime-hardness for ALCHI in the case of bounded predicate arities is due to the same hardness of ALCHI with closed predicates. NExpTimeNP-hardness in the case of unbounded predicate arities is obtained by a reduction from answer set existence problem for disjunctive datalog which is complete for this class. Finally, p3-hardness is shown by a reduction from 989-QBFs to RLPs with ALCHI/DL-LiteF theories, given in the extended version. The presented data complexity bound for ALCHOIQ is inherited from the combined complexity, as the data complexity of ALCHOIQ with closed predicates is unknown, and it is likely that it is not optimal. 6
We note that the decidability of the answer set existence problem under plain
safety (see De nition 3) easily generalizes from DLs to other fragments of
rstorder logic. The only requirement for such fragments is the decidability of theories
in the presence of closed predicates, which is enjoyed, e.g., by the guarded negation
fragment (GNFO) [
In this paper, DL ontologies are interpreted over Herbrand interpretations (whose domain is a xed in nite set of constants). This was done for mathematical clarity of the semantics of RLPs, but it has some side-e ects, e.g., by ruling out ontology models with a nite domain. This can be easily xed using a more complicated de nition that handles two kinds of interpretations: Herbrand interpretations for rules, and ordinary rst-order structures for DL ontologies.
The are several questions for future research. We plan to investigate the complexity of RLPs under various restrictions on rules. In particular, we believe that disallowing default negation in front of response predicates will often lead to lower computational complexity. We also plan to study rewritability of RLPs into standard disjunctive ASP, for which e cient implementations exist. 21. Riccardo Rosati. On the decidability and complexity of integrating ontologies and rules. J. Web Sem., 3(1):61{73, 2005. 22. Riccardo Rosati. DL+log: Tight integration of description logics and disjunctive datalog. In Proc. of KR 2006. AAAI Press, 2006. 23. Riccardo Rosati. The limits of querying ontologies. In Proc. of ICDT 2007, volume 4353 of Lecture Notes in Computer Science, pages 164{178. Springer, 2007. 24. Inanc Seylan, Enrico Franconi, and Jos de Bruijn. E ective query rewriting with ontologies over dboxes. pages 923{925, 2009. 25. Stephan Tobies. The complexity of reasoning with cardinality restrictions and nominals in expressive description logics. J. of Arti cial Intelligence Research, 12:199{217, 2000.