# knowledgebase_degrees_of_inconsistency_complexity_and_counting__8795e876.pdf

Knowledge-Base Degrees of Inconsistency: Complexity and Counting

Johannes K. Fichte1 Markus Hecher2 Arne Meier3

1 TU Dresden 2 TU Wien 3 Leibniz Universität Hannover johannes.ﬁchte@tu-dresden.de, markus.hecher@tuwien.ac.at, meier@thi.uni-hannover.de

Description logics (DLs) are knowledge representation languages that are used in the ﬁeld of artiﬁcial intelligence (AI). A common technique is to query DL knowledge-bases, e.g., by Boolean Datalog queries, and ask for entailment. But real world knowledge-bases often have a certain inconsistency (with respect to a given query) or we are required to estimate a degree of inconsistency when using a knowledge-base. In this paper, we provide a complexity analysis of ﬁxed-domain nonentailment (NE) on Datalog programs for well-established families of knowledge-bases (KBs). We exhibit a detailed complexity map for the decision cases, counting and projected counting, which may serve as a quantitative measure for inconsistency of a KB with respect to a query. Our results show that NE is natural for the second, third, and fourth level of the polynomial (counting) hierarchy depending on the type of the studied query (stratiﬁed, tight, normal, disjunctive) and one level higher for the projected versions. Further, we show ﬁxed-parameter tractability by bounding the treewidth, provide a constructive algorithm, and show its theoretical limitation in terms of conditional lower bounds.

1 Introduction Description logics (DL) have proven itself as a central framework in the ﬁeld of artiﬁcial intelligence (AI) (Krötzsch, Simancik, and Horrocks 2012; Baader et al. 2017). Since DL was introduced by Brachman and Levesques in 1984, the formalism has become a host for expressing knowledge representation problems and reasoning about the relevant concepts of an application domain (ontologies). As the application domain is quite vast (Hitzler et al. 2012; Knublauch, Musen, and Rector 2004; Eiter et al. 2015; Klinov 2008), a plethora of different extensions as well as restrictions have emerged (Calvanese 2006; Horrocks, Kutz, and Sattler 2006; Horrocks and Sattler 2007). The versatility of DL is one of its strength and, as a result, new extensions or combinations with other concepts or formalisms are common (Baader, Küsters, and Wolter 2003; Baader et al. 2005; Motik 2006). In general, a knowledgebase consists of different components: an ABox, a TBox, and a RBox. An ABox (assertion box) can be seen as a prescribed part of the model, a TBox (terminology box) is

Copyright 2021, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

a set of so-called inclusion-axioms that have to be obeyed in every world of the model, and an RBox (role box) is a set of relation constraints. Reasoning in DLs often involves querying knowledge-bases which, when asking for closedworld, can be achieved by Boolean Datalog programs. While constructing those queries seem straight-forward, huge real world databases often contain data entries that are inconsistent with respect to a considered query. In other words, given a knowledge-base and a Datalog query, a model of a knowledge-base cannot consistently be extended to the query and is seen to be inconsistent with respect to it. We want to estimate a degree of inconsistency by counting inconsistencies. This can be particularly interesting in a setting where we need a quantitative measure on the models that cannot be entailed. This is a stronger notion of reasoning than classical skeptical reasoning (asking for containment in all models). Let us consider the following example from the propositional setting to illustrate this approach. Note that stable models are deﬁned in terms of subset-minimality. We give a more elaborate example in the sequel of the paper. Example 1. Consider the following entailment question: {p(a) p(b)} |= {p(c) ; p(a), p(b)}? The models of {p(a) p(b)} are {p(a)}, {p(b)}, and {p(a), p(b)}. However, only {p(a), p(c)} and {p(b), p(c)} are stable models of the program {p(c) ; p(a), p(b)} extending {p(a)} and {p(b)}, respectively. As a result, the last of the three models cannot be extended to a stable model. In this paper, we investigate the complexity of ﬁxeddomain non-entailment (NE) on Datalog programs for SROIQ or DLmin knowledge-bases, which may serve as a quantitative measure for inconsistency. The DL SROIQ is quite expressive: it allows to express transitivity, (ir)reﬂexivity, antisymmetry, subrole-relation, inverse, disjointness of roles, as well as negated role assertions, complex role inclusions, the universal role, and local reﬂexivity (Horrocks, Kutz, and Sattler 2006). The DL DLmin is, as already stated by its name, quite restricted: only TBoxaxioms of the form A B as well as atomic assertions A(a), r(a, b) are allowed, with A, B are concept names, r a role name and a, b individual names. In our setting, we also incorporate a more ﬁne-grained analysis by considering the treewidth, which is a popular parameter that makes various NP-hard problems tractable and is widely used in the ﬁeld of artiﬁcial intelligence (Gottlob and Szeider 2007;

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

Name Syntax Semantics

inverse role r { (x, y) | (y, x) r I } universal role u top bottom negation C \ CI

conjunction C D CI DI

disjunction C D CI DI

nominals {a1, . . . , an} {a I 1, . . . , a I n} univ. restr. s.C {x | y.(x, y) s I y CI } exist. restr. s.C {x | .(x, y) s I y CI } self concept s.self {x | (x, x) s I } qualiﬁed no. nr.C {x | #{y CI | (x, y) r I} n} restriction nr.C {x | #{y CI | (x, y) r I} n}

Sets Axiom α I satisﬁes α if

ABox A C(a) a I CI

r(a, b) (a I, b I) r I

a b a I = b I

a = b a I = b I

RBox R r1 . . . rn r r I 1 . . . r I n r I

Dis(r1, r2) r I 1 r I 2 =

TBox T C D CI DI

Table 1: Syntax and semantics of SROIQ, where a, b, a1, . . ., an denote individual names, s is a role name, r, r1, . . ., rn are role expressions, and C and D concept expressions.

Gottlob, Pichler, and Wei 2006, 2007) and databases (Grohe 2007). Our main contributions are as follows: (I) We establish the computational complexity for deciding NE and for (projected) counting of NE anti-witnesses. Our results show that NE is complete for the second, third, and fourth level of the polynomial (counting) hierarchy depending on the type of the studied query (stratiﬁed, tight or normal, disjunctive) and increases by one level when considering projected answers in the setting of bounded domains. (II) We provide a novel graph (knowledge-program graph) to deﬁne treewidth on non-ground Datalog programs and show ﬁxed-parameter tractability by bounding the treewidth of the knowledgeprogram graph and bounding the domain. (III) We establish dynamic programming algorithms for solving the problems and show also matching conditional lower bounds.

Related Works Parameterized complexity results for description logics, however, mostly hardness results, have recently been established by de Haan (2018). Treewidth is widely used for ﬁne-grained complexity analyzes and to establish algorithms that provide tractability when bounding the treewidth, e.g., artiﬁcial intelligence (Gottlob and Szeider 2007), knowledge representation (Gottlob, Pichler, and Wei 2006), abduction in Datalog (Gottlob, Pichler, and Wei 2007), and databases (Grohe 2007). In the context of counting and projected counting treewidth has been considered in various areas (Fichte, Hecher, and Meier 2018; Fichte et al. 2017; Fichte and Hecher 2019; Fichte, Hecher, and Schindler 2018; Fichte et al. 2018a). Also competitive implementations are available (Fichte et al. 2018b, 2020; Hecher, Thier, and Woltran 2020; Dudek, Phan, and

Vardi 2020). Conditional lower bounds have been considered by Pan and Vardi (2006) and Fichte, Hecher, and Pfandler (2020). Inconsistencies and distance measures, in terms of the number of formulas responsible for an inconsistency and the propositions in the language affected by the inconsistency, have been considered by Ma, Qi, and Hitzler (2010; 2011). Para-consistent semantics for handling inconsistencies occurring in the combination of description logics and rules have been suggested by Huang, Li, and Hitzler (2012). Repair-related problems have been considered in databases, but are conceptually different from our setting, as databases usually only assume closed world. Eiter et al. (2008) studied the combination of ASP and DL in terms of ﬁxpoint characterizations, strong and a weak answer set semantics, and computational complexity (EXP, NEXP, co-EXP, P NEXP). Gaggl, Rudolph, and Schweizer (2016) considered the complexity for standard reasoning and query answering under the ﬁxed-domain semantics for DLs. While they investigate the complexity under queries that implement stable model semantics, their work is limited to the ground case and does not incorporate disjunctive queries. In contrast to our work, they consider a different formalism restricting the occurrences of atoms in the heads in the rules of the query. They do not consider treewidth. We state explicit runtime bounds yielding tractability and precise runtime guarantees. Rosati (2011) considered the complexity of inconsistency by minimally repairing an ABox while keeping the TBox untouched. There are various works that consider treewidth or other parameterizations in the realm of DL (Bienvenu et al. 2013; Simanˇcík, Motik, and Horrocks 2014; Barceló et al. 2019; Bienvenu et al. 2017). We consider the ﬁxed-domain setting, which in practical solving is a fairly weak limitation, but allows for much better complexity behavior. In contrast to the mentioned works above, we establish exact runtimes that cannot be signiﬁcantly improved under ETH (both upper and lower bounds). Projected model counting is also emerging topic in practical experimental evaluations (Fichte, Hecher, and Hamiti 2020).

2 Preliminaries

Let tower(i, p) be tower(i 1, 2p) if i > 0 and p otherwise.

Description Logics For an introduction to the description logic SROIQ, we refer to its original source (Horrocks and Sattler 2007). We brieﬂy outline its syntax and semantics. Let be a ﬁnite, ﬁxed domain. Let NI, NC, and NR be ﬁnite disjoint sets. We call NI individual names, NC concept names, and NR role names, which can be used to form complex expressions as displayed in Table 1. An axiom in description logic is a logical statement that relates roles and concepts. Table 1 provides the axioms that are allowed for the description logic SROIQ and its ABox (assertion box), TBox (terminology box), and RBox (role box). Intuitively, an ABox contains sentences stating where in the hierarchy, individuals belong (i.e., relations between individuals and concepts), and a TBox contains sentences describing concept hierarchies (i.e., relations between concepts), and an RBox the relations of constraints. Let K = (A, T , R) be a tuple called knowledge-base, where A is an ABox, T is

a TBox, and R is an RBox. Then, we abbreviate the individual names, concept names, and role names that occur in K by NI(K), NC(K), and NR(K), respectively. Further, we let N(K) := NI(K) NC(K) NR(K) be the names occurring in K and we let these deﬁnitions naturally extend to ABox, TBox, RBox, and axioms. An interpretation I is a tuple I = ( , I) where I is a function that maps elements in NI to elements in , elements in NC to elements in 2 , elements in NR to elements in 2 , and for extended concepts to complex role and concept expressions according to Table 1. Alternatively, we may view an interpretation I as a triple I, C, R with I : NI(K) , C : NC(K) 2 , and R: NR(K) 2 . We say that I satisﬁes K, or I |= K for short and call I model of K, if it satisﬁes all axioms of A, T , and R where the satisfaction of axioms is given as in Table 1. We say that K entails an axiom α, or K |= α for short, if all models of K are models of α. The DL DLmin allows only TBox-axioms of the form A B as well as atomic assertions A(a), r(a, b), with A, B are concept names, r a role name and a, b individual names. Datalog Programs Let be a ﬁxed, ﬁnite domain of cardinality at least 2, and NP be a set of predicate names. An atom is an expression p(t1, . . . , tc), where a predicate p NP is of bounded-arity c 0 and each ti is either a (ﬁrst-order) variable or an element of domain . We say an atom is Boolean if it contains only domain elements. We usually write upper case letters like X or X attributed with a subscript for a variable. A (disjunctive) rule r is an expressions of the form a1 aℓ aℓ+1, . . . , am, am+1, . . . , an. with n > 0, ℓ m n and where a1, . . . , am are atoms. We let Hr := {a1, . . . , aℓ}, B+ r := {aℓ+1, . . . , am}, and B r := {am+1, . . . , an}. A ground rule is of the same form as a disjunctive role, however, a1, . . . , am are Boolean atoms. A rule r is normal if |Hr| 1. We say that a program has a certain property if all its rules have the property. A program is a ﬁnite set of rules. We denote the sets of atoms occurring in a rule r, resp., in a program P, by at(r) := Hr B+ r B r , resp., by at(P) := S r P at(r). Further, the predicates of NP occurring in a rule r or program P are addressed by NP(r) or NP(P), respectively. A substitution σ is a total mapping from a given set of variables to . Then, Ground(P) is the set of ground rules rσ obtained by applying, to each rule r P, all possible substitutions σ from variables in P to . A normal program P is stratiﬁed if there is a mapping str: at(Ground(P)) N such that for each rule r Ground(P) the following is true: (i) if x Hr and y B+ r , then str(x) str(y), and (ii) if x Hr and y B r , then str(x) < str(y). We say that a normal program is tight if it has no cycles w.r.t. the graph that has as vertices the Boolean atoms at(Ground(P)) and a directed edge (x, y) between any two atoms x,y at(Ground(P)) for which there is a rule r Ground(P) with x Hr and y B+ r . We denote the class of all normal programs by Normal, the class of all stratiﬁed programs by Strat, the class of all tight programs by Tight, and the class of all programs by Disj. An interpretation J is a set of Boolean atoms. Then, J satisﬁes a ground rule r if (Hr B r ) J = or B+ r \ J = . J is a model of P if it satisﬁes every ground

rule r Ground(P), in symbols J |= P. The GL-reduct of P (Gelfond and Lifschitz 1991) under J is the program PJ = { Hr B+ r | J B r = , r Ground(P) }. We say that J is a stable model of a program P if J is a subset-minimal model of PJ . For tight programs this is equivalent (Lin and Zhao 2003) to J |= P such that every a J is justiﬁed (by P), i.e., there has to exist r Ground(P) with a Hr, J B+ r and J B r = . Deciding whether a ground program has a stable model (consistency problem) is ΣP 2 -complete (Eiter et al. 2007; Eiter and Gottlob 1995). Deciding whether a program has a stable model (consistency problem of a program with boundedarities) as well as deciding whether an atom is in a stable model (brave reasoning) is ΣP 3 -complete (Eiter et al. 2007). Tree Decompositions Let G = (V, E) be a graph. A tree decomposition (TD) of a graph G is a pair T = (T, χ), where T is a rooted tree and χ a mapping that assigns to each node t of T a set χ(t) V , called a bag, such that the following conditions hold: (i) E t of T { {u, v} | u, v χ(t) }; and (ii) for each r, s, t, such that s lies on the path from r to t, we have χ(r) χ(t) χ(s). Then, the width of T corresponds to maxt of T |χ(t)| 1 and the treewidth is the minimum width over all TDs of G. In order to simplify case distinctions in the algorithms, we assume nice TDs as follows: For a node t of T, we say that type(t) is leaf if t has no child nodes and χ(t) = ; join if t has exactly two child nodes t1, t2 with χ(t) = χ(t1) = χ(t2); intr if t has only one child node t1 with χ(t1) χ(t) and |χ(t)| = |χ(t1)| + 1; forget if t has only one child node t1 s.t. χ(t1) χ(t) and |χ(t1)| = |χ(t)| + 1. If for every node t N, type(t) {leaf, join, intr, forget} and the bag of the root is empty, then the TD is called nice.

3 Datalog Queries in Description Logics We use ﬁxed-domain semantics inspired by earlier work (Gaggl, Rudolph, and Schweizer 2016). However, we extend the notion and enable full Datalog programs. Given a knowledge-base K, a ﬁxed domain , and a Datalog program P, we say that K |= P if and only if every model I = ( , I) of K can be extended to a stable model J of P. More precisely, K |= P is true if and only if there a subset-minimal model J of (Ground(P) PI)J where PI := { C(d) | d CI, C NC(K) } { R(d1, d2) | (d1, d2) RI, R NR(K) }. If I cannot be extended to a stable model J of P, we say I is an anti-witness of K |= P. We consider the following ﬁxed-domain non-entailment problem on speciﬁc bounded-arity Datalog programs. Let NEC; C {Strat, Tight, Normal, Disj} be the problem asking, given KB K and a C-program P, K |= P? Sometimes we write NE for NEDisj. The following example illustrates the problem NE.

Example 2. Consider the following knowledge-base K = (A, T , ), which describes a medical setting and relations between diseases and symptoms. First, take as the domain = {donald, emanuel, silvio} describing three people and deﬁne the ABox A and the TBox T as follows: A := {Meet(P1, P2), Contagious(P1), Meet(P2, P3), P1 = P2, P2 = P3, P1 = P3}, T := {

1u.Mask, Contagious Flu Sinusitis, Exposed Meet.(Contagious Mask), Flu Fever Exposed, Sinusitis Fever Exposed, Meet Meet Meet, Meet Meet }. Then, we ask the following query P := { superspread; superspread Contagious(X), Contagious(Y ), X = Y }, where we simply consider = as a shortcut, since we have a ﬁxed domain. When we ask for entailment of K |= P, P expresses that there are at least two contagious people (superspread). Observe that this does not hold, i.e., P is a positive instance for NE. However, the number of anti-witnesses to K |= P is small compared to all models I of K with I |= P. This is justiﬁed since only interpretations J with P J 1 Mask J

are anti-witnesses, attributing to about 1

3 of the models of K. Hence, weaker forms of entailment are still rather likely.

Theorem 3. The combined complexity of NEStrat w.r.t. a SROIQ or DLmin knowledge-base is ΣP 2 -complete.

Proof (Sketch). We reduce QBFVAL ,2 to the complement of NEStrat. Let Φ = p1, . . . , pk q1, . . . , qmϕ with ϕ in 3CNF, that is ϕ = Vn i=1 Ci and Ci = ℓi,1 ℓi,2 ℓi,3 for 1 i n, k, m, n N, and ℓi,j are literals from variables in V := P Q, where P := {p1, . . . , pk}, Q := {q1, . . . , qm}. Next, we deﬁne a DLmin knowledgebase K = (A, T , ), a ﬁxed-domain , and a non-ground stratiﬁed Datalog program P such that K |= P if and only if Φ is valid. Set := { 0, 1 } and deﬁne K as follows. Let the ABox A contain the following axioms:

Selectv(xv), Un Selectv(yv) for all v {p1, . . . , pk}

Let the TBox T contain the following axioms:

Selectv Un Selectv for all v {p1, . . . , pk}

Fix an arbitrary total ordering < on the variables of Φ. For a set W of variables and a clause or term T, let W(T) = (w1, . . . , we) be the ordered sequence of variables of T that are also in W where 0 e 3, i.e., {w1, . . . , we} = W Vars(T). We deﬁne program P as the union of programs Sn i=1{sat Ci(θ) eℓi,j | ℓi,j / Lit(Q), θ: Q(Ci) {0, 1}, | Q(Ci)| < 3, θ |= Ci Lit(Q) }, Sn i=1{sat Ci(θ) | θ: Q(Ci) {0, 1}, θ |= Ci }, {sat sat C1( Q(C1)), . . . , sat Cn( Q(Cn)); sat}

where eℓ:= Selectv(0) if ℓ= v and eℓ:= Selectv(1) if ℓ= v. Note that θ is interpreted as bit-vector, where expressions of the form sat Ci( Q(Ci)) contain for Q(Ci) tuples of FO-variables. The construction with the tuples Q resembles an idea inﬂuenced by Eiter et al. (2007, Lemma 6). When asking for entailment, program P ensures that only those models of K are also stable models of Φ for which we have validity (i.e., for all {p1, . . ., pk} we can satisfy all clauses by setting {q1, . . ., qm} using FO-variables Q(Ci) of sat Ci. It remains to argue membership. We can obtain ﬁxeddomain non-entailment of a query P from a SROIQ knowledge-base K (I |= P) by (a) guessing an interpretation I and verifying whether I is a model of K and then (b) by checking whether P PI has a stable model. Since

for (a) we can simply guess an interpretation and checking ﬁxed-domain satisﬁability of a SROIQ knowledge-base is in NP (Gaggl, Rudolph, and Schweizer 2016, Lem 5) and for (b) consistency of a bounded-arity Datalog query is in P 2 (Eiter et al. 2007, Lem. 2), we have a machine witnessing membership in NP P 2 = NPNP.

Example 4. Let Φ = p qϕ and ϕ = C1 C2, with C1 = (p q), C2 = (p q). Then, A = {Selectp(xp), Un Selectp(yp)}, and T = {Selectp Un Selectp}. We choose the ordering p < q. (1) P contains sat C1(0) Selectp(1) and sat C2(1) Selectp(1) as C1 is only satisﬁed w.r.t. the variable q by setting it to 1 and for C2 by setting q to 0. (2) P contains sat C1(1) and sat C2(0) as argued before. (3) P contains sat sat C1(Xq), sat C2(Xq) as well as sat . Clearly, Φ is false, and, as a result, we have K |= P. Then, we construct an interpretation I = ( , I) such that I |= K and it cannot be extended to a stable model J of P. Set x I p = 0 and y I p = 1, Select I p = {0}, Un Select I p = {1}. Now, no stable model J of I can set sat C1 and sat C2 to contain the same element. As a result, sat J = 0, contradicting sat. Theorem 5. The combined complexity of NEDisj w.r.t. a SROIQ or DLmin knowledge-base is ΣP 4 -complete. Proof (Sketch). We reduce QBFVAL ,4 to the complement of NEDisj. Let k, m, h, o N, P := {p1, . . . , pk}, Q := {q1, . . . , qm}, R := {r1, . . . , rh}, and S := {s1, . . . , so}. Let Φ = p1, . . . , pk q1, . . . , qm r1, . . . , rh s1, . . . , soϕ with ϕ in 3CNF, that is ϕ = Wn i=1 Ci and Ci = ℓi,1 ℓi,2 ℓi,3 for 1 i n, and ℓi,j Lit(Φ). We use the same knowledge-base as in the proof of Theorem 3 and use notation from the proof of Theorem 6. However, of course, we will use a more complex program P, which is the union of the following programs {Selectv(0) Selectv(1); Selectv(1) Selectv(0) | v Q }, {Selectv(0) Selectv(1) | v R }, Sn i=1{sat Ci(θ) eℓi,j | ℓi,j / Lit(S), θ: S(Ci) {0, 1}, | S(Ci)| < 3, θ |= Ci Lit(S) }, Sn i=1{sat Ci(θ) | θ: S(Ci) {0, 1}, θ |= Ci }, {sat sat C1( S(C1)), . . . , sat Cn( S(Cn)); sat}, {Selectv(α) sat | α {0, 1}, v R }, where sat is a fresh atom. It remains to argue membership. We can obtain ﬁxeddomain non-entailment of a query P from a SROIQ knowledge-base K (I |= P) by (a) guessing an interpretation I and verifying whether I is a model of K and then (b) by checking whether P PI has a stable model. Since for (a) we can simply guess an interpretation and checking ﬁxed-domain satisﬁability of a SROIQ knowledge-base is in NP (Gaggl, Rudolph, and Schweizer 2016, Lem 5) and for (b) consistency of a bounded-arity Datalog query is in ΣP 2 (Eiter et al. 2007, Lem 3), we have an algorithm witnessing membership in NPΣP 3 = ΣP 4 .

Theorem 6. Let C {Tight, Normal}. The combined complexity of NEC w.r.t. a SROIQ or DLmin knowledge-base is ΣP 3 -complete.

Characterizing Counting Complexity In this section, we investigate the complexity of counting (projected) anti-witnesses for entailment problems on bounded-arity Datalog programs. We follow standard terminology in this area (Durand, Hermann, and Kolaitis 2005), using complexity classes preceded with the sharp-dot operator # . A witness function is a function w: Σ P<ω(Γ ), where Σ and Γ are alphabets, mapping to a ﬁnite subset of Γ . Such a function relates to the counting problem given x Σ , ﬁnd |w(x)| . If C is a decision complexity class then # C is the class of all counting problems whose witness function w satisﬁes (1.) polynomial p such that for all y w(x), we have that |y| p(|x|), and (2.) the decision problem given x and y, is y w(x)? is in C. Finally, note that we use parsimonious reductions (Durand et al. 2005) that preserve the cardinality between the corresponding witness sets and is computable in polynomial time. Let #NEC; C {Strat, Tight, Normal, Disj} be the problem asking to compute the number of anti-witnesses of K |= P, given A knowledge-base K and a C-program P. As the reductions in Section 3 preserve the cardinality of solutions, we immediately obtain the following corollary.

Corollary 7. For a SROIQ or DLmin knowledge-base: (1.) #NEStrat is # NP-complete, (2.) #NETight and #NENormal are # ΣP 2 -complete, and (3.) #NEDisj is # ΣP 3 -complete.

Next, we naturally want to extend the problem above by taking a set of atoms as part of the input to which all solutions are projected onto. When we count, multiple antiwitnesses that are identical when restricted to a set of projected atoms those count as only one anti-witness. Let #p NEC; C {Strat, Tight, Normal, Disj} be the problem asking to compute the number of distinct antiwitnesses to K |= P, when restricted to names in Π, given a Datalog program P C, a KB K, and a projection Π N(K).

Example 8. Consider knowledge-base K and P from Example 2. Recall that about 1

3 of the models are anti-witnesses to K |= P. Still, the number of anti-witnesses can be very large, since one can almost arbitrarily interpret Fever. If we are interested only in how to distribute the one mask, we could ask for #p NE on K, P and projection Π := {P1, Mask}. Then, this results in only three projected antiwitnesses. Each anti-witness J ensures P J 1 Mask J .

Similarly, one can show the result for the projected versions that yield one jump in the complexities, whose proof is in the extended version.

Theorem 9. For a SROIQ or DLmin knowledge-base: (1.) #p NEStrat is # ΣP 2 -complete, (2.) #p NETight and #p NENormal are # ΣP 3 -complete, and (3.) #p NEDisj is # ΣP 4 -complete.

4 Algorithms and Results for Treewidth In the following, we provide a parameterized complexity analysis for the problems NE and #NE when parameterized by treewidth of the input instance. We give algorithms and thereby establish upper bounds on the runtime. These

superspread Flu Fever

{Cont, Exp, Mask, Meet} t6

{P1, Meet, Cont} t5

{P1, P2, P3, Meet} t4

{Cont, Exp, Flu, Sin} t3

{Exp, Fever, Flu, Sin} t1

{super, Cont} t2 Figure 1: Knowledge-program graph G and a treedecomposition TG of G.

runtime results match with conditional lower bounds if we believe in the exponential time hypothesis (ETH) (Impagliazzo, Paturi, and Zane 2001). Algorithms that exploit small treewidth, typically run dynamic programming along a tree decomposition (Bodlaender and Kloks 1996) of a graph representation of the input instance. During dynamic programming the nodes of the decomposition are traversed bottomup and at each node t of the decomposition a set τt of records is computed by means of a bag algorithm. Such a bag algorithm is speciﬁed by describing how this set of records is computed for each node of the TD, thereby considering the sets of records for the child node and evaluating only a part of the instance, called bag instance. At the root we interpret the set of records and output the solution to our question. Before we provide our algorithms for treewidth, we require a dedicated graph representation of our knowledgebases and datalog programs, as well as the deﬁnition of a bag instance. Here we are dealing with the non-ground setting and bounding treewidth for both KBs and non-ground datalog programs. Consequently, we deﬁne a graph representation similar to the primal graph, but for non-ground datalog and thereby also considering KBs. To this end, we consider for an instance I = K, P , consisting of a given knowledge-base K = (A, T , R) and a given datalog program P, the knowledge-program graph GI. The vertices of GI consist of all individual, concept, and role names of K as well as all predicates occurring in P. Then, there is an edge between two vertices of GI, whenever the corresponding names appear together in at least one axiom, concept inclusion, role inclusion or at least one datalog rule. Formally, we let GI := (V, E), where V := N(K) NP(P) and E := {{e1, e2} | {e1, e2} N(a), a A} {{C, C } | {C, C } N(c), c T } {{R, R } | {R, R } N(r), r R} {{p1, p2} | p1, p2 NP(r), r P}. Example 10. Consider the knowledge-base K and program P from Example 2. The knowledge-program graph G of K and P and a decomposition is shown in Figure 1. Let T = (T, χ) be a TD of the knowledge-program graph for given K and P, and let t be a node of T. Then, the bag knowledge-base is deﬁned as Kt := (At, Tt, Rt), where At := {a | a A, N(a) χ(t)}, Tt := {c | c T , N(c) χ(t)}, and Rt := {r | r R, N(r) χ(t)}. Further, the bag program Pt is given by Pt := {r | r P, NP(r) χ(t)}. As a result, this leads to the bag instance It, which is deﬁned by It := Kt, Pt . Intuitively, the bag instance consists of those axioms and rules, whose symbols are fully contained in the bag. Example 11. Consider Example 2 and TD TG of G. Take node t3 from TD TG. Then, bag knowledge-base Kt3 =

( , {Contagious Flu Sinusitis}, ) and bag program Pt3 = , resulting in It3 = Kt3, Pt3 . Having established graph representations and the deﬁnition of bag instances that is evaluated in a node of a TD of the graph, we are ready to present our bag algorithm for NETight and #NETight. While the speciﬁcs are for brevity carried out only for the simple case of tight programs, the basic concept of these algorithms vacuously extends to the other program classes, cf., (Fichte and Hecher 2019). This algorithm is described in Figure 2 in the form of a case distinction, whose cases depend on the types of nodes of a nice TD. Note that any TD can be turned into a nice TD without increasing the width, cf., (Kloks 1994). However, for nonnice TDs, these cases simply overlap accordingly. Overall, for any set τt of records, Figure 2 maintains records of the following form: I, C, R, J , c , where I, C, R forms an interpretation of Kt and c is an integer for solving #NE (irrelevant for decision problem NETight). Further, J is a set of tuples of the form J, P , where J is an interpretation of Pt and P J is a set of atoms of J, where for every a P there is a rule r Pt justifying a. Consequently, we deﬁne the atoms of J justiﬁed by Pt by justift(J) := {a | r Ground(Pt), a Hr, J B+ r , J (B r Hr \{a}) = }. While the actual details of this bag algorithm are quite technical, the high-level idea of the algorithm for a node t is as follows: The table τt for node t contains records consisting of a model of Kt that can be extended to a model of the knowledge-base obtained by combining all bag knowledgebases below t in T, as well as a set of models of Pt such that each of these models can be extended to a stable model of the program consisting of all bag programs below t in T. For leaf nodes t (see Line 1 of Figure 2) the set τt of records only contains the empty interpretation (satisfying the empty knowledge-base) and the empty interpretation and the empty set of justiﬁed atoms satisfying the empty program. Now, let s N(Kt) NP(Pt) be any symbol of the bag instance It. Then, we deﬁne the (exhaustive) interpretations for individuals by Int(s) := {s 7 d | s NI(Kt), d }, the concept interpretations by Cot(s) := {s 7 D | s NC(Kt), D }, and the role interpretations by Rot(s) := {s 7 D | s NR(Kt), D ( )}, as well as the datalog interpretations by Prt(s) := {s(d) | s NP(Pt), d }. These deﬁnitions are used to exhaustively guess for nodes t that introduce a symbol s, as shown in Line 3 of Figure 2, all potential interpretations satisfying both Kt, as well as Pt. Further, Line 3 also updates justiﬁed atoms. Intuitively, whenever a symbol s is forgotten in a node t (cf., Line 5), the interpretations do not need to care about s any more, so we remove information about s. However, we have to ensure that every atom in J is justiﬁed. Further, for forget nodes one has to take care that interpretations that are different for child nodes of t might collapse in the set of records τt, so one has to sum up the corresponding counters. For a join node t, which is a node with two child nodes as handled by Line 8, one has to ensure to combine records, where the corresponding assignments coincide. Justiﬁcations for atoms, however, sufﬁce in only one node and one has to multiply counters accordingly. Finally, we analyze the set τr of records for the (empty)

In: Node t, bag χ(t), bag instance It = (Kt, Pt), and sets τ1, . . . , τℓ of records for children of t. Out: Set τt of records.

1 if type(t) = leaf then τt { , , , { , }, 1 }

2 else if type(t) = intr and symbol s χ(t) is introduced then

3 τt { I , C , R , J , c | I, C, R, J , c τ1, I I Int(s)+ I , C C Cot(s)+ C, R R Rot(s)+ R, J = { J , justift(X)+ P | J, P J , J J Prt(s)+ J , X = I C R J , X |= Pt}, I , C , R |= Kt}

4 else if type(t) = forget and symbol s χ(t) is forgotten then

5 ρt { I Int(s), C Cot(s), R Rot(s), { J Prt(s), P Prt(s) | J, P J , J Prt(s) P}, c, u | u τ1, u = I, C, R, J , c }

6 τt { I , C , R , J , P

I ,C ,R ,J ,c,... ρt{c} | I , C , R , J , . . . ρt}

7 else if type(t) = join then

8 τt { I, C, R, { J, P1 P2 | J, P1 J1, J, P2 J2}, c1 c2 | I, C, R, J1, c1 τ1, I, C, R, J2, c2 τ2}

S+ S :=S S and S S :=S \ S . Figure 2: Bag algorithm #NETight(t, τ1, . . . , τℓ ).

root node r of TD T . Instance I is a positive instance of NETight if and only if τr contains a record u whose fourth component J is empty. It is easy to see that also the complement of NETight can be solved using Figure 2, i.e., therefore (runtime) properties sustain even for the complement problem. Further, the number of solutions to problem #NETight is contained in the ﬁfth component (counter c) of this record u. Example 12. Consider the knowledge-base K, domain and program P from Example 2 as well as TD T of G K,P . Then, table τ4 for node t4 is the result of introducing symbols (individual names) P1, P2, P3 as well as role name Meet. Consequently, due to Line 3 of Figure 2, we have {P17 donald, P27 emanuel, P37 silvio}, , {Meet 7 {(donald, emanuel), (emanuel, silvio)}}, { , }, 1 τ4. In total there are 3! = 3 2 1 = 6 many records of similar kind in τ4, corresponding to the possibilities of mapping individuals P1, P2, P3 to without overlaps. For node t2, we introduce superspread as well as Contagious. Note that superspread / χ(t3) and therefore only those records of table τ2 have successor records in table τ3 for node t3, where we have justiﬁcation for the atom superspread of arity 0 over predicate superspread, cf., Line 5 of Figure 2. Among these sustaining records we have , {Contagious7 {donald, emanuel, silvio}}, , { { superspread}, {superspread} }, 1 of τ2 as well as 3 2 = 3 many records according to the possibilities of selecting two contagious people over domain in order to be able to derive and justify superspread as required by program P. Then, node t3 is the result of removing from table τ2 predicate name superspread and merging the result (cf., Line 8) with the table obtained from table τ1 for node t1, where interpretations for concept name Fever have been removed, cf., Line 5. Similarly, one continues with computing the table for node t6 in order to ﬁnally obtain that there are anti-witnesses of K |= P and the solution to NETight. Overall, the algorithm established in Figure 2 leads to the following result due to the number of records and since a TD of GK,P with a linear number of nodes can be 5-

approximated (Bodlaender et al. 2016) in linear time. Theorem 13. Given a KB K and a program P Tight, both over ﬁxed domain , where k is the treewidth of the knowledge-program graph G K,P . Then, we can decide NETight in time tower(2, | |O(k)) |N(K) NP(P)|. This approach can be used for the class Strat of stratiﬁed programs, where the fourth components J of the records only need to be of cardinality 1, since stratiﬁed programs have one unique stable model (Apt, Blair, and Walker 1988). Further, the algorithm can be extended to more expressive datalog programs, namely normal and disjunctive programs, thereby obtaining runtimes of tower(2, | |O(k log(k))) |N(K) NP(P)| and tower(3, | |O(k)) |N(K) NP(P)|, respectively. For counting, we need to keep track of counts, which slightly increases runtimes from being linear in the instance size |N(K) NP(P)| to a runtime that is subquadratic in the instance size. The reason is that the multiplication of two n-bit numbers, if not assumed to be constant-time by deﬁnition, runs in time n log(n) log(log(n)) (Knuth 1998). Similarly, one can provide dynamic programming algorithms for problem #p NEC by lifting algorithms for projected counting of the literature (Fichte and Hecher 2019). Thereby, the runtime results are exponentially worsened in the treewidth, cf., complexity results summarized in Table 2.

Hardness Results via Conditional Lower Bounds However, if we believe in reasonable assumptions in computational complexity, namely the exponential time hypothesis (ETH) (Impagliazzo, Paturi, and Zane 2001), it turns out that one can show that these runtimes can probably not be signiﬁcantly improved in the worst case. ETH is a widely accepted standard hypothesis in algorithms and complexity, which implies that one cannot solve the Boolean satisﬁability problem in sub-exponential time. To this end, we rely on very recent conditional lower bounds (Fichte, Hecher, and Kieler 2020, Thm. 15) for quantiﬁed constraint satisfaction and show the following. Theorem 14. Given a knowledge-base K = (A, T , R) and a datalog program P, both over ﬁxed domain , such that the treewidth of the knowledge-program graph GK,P is k and assume ETH. Then, problems NEC, #NEC for C = Strat and C {Tight, Normal} can not be solved in time f(k) poly(|N(K) NP(P)|) with f(k) = 2| |o(k) and f(k) = tower(2, | |o(k)), respectively. Further, problems NEDisj, #NEDisj can not be solved in time tower(3, | |o(k)) poly(|N(K) NP(P)|).

Proof (Sketch). We show the case for C = Disj by reducing QCSPVAL ,4 to the complement of NEDisj. Let k, m, h, o N, P := {p1, . . . , pk}, Q := {q1, . . . , qm}, R := {r1, . . . , rh}, and S := {s1, . . . , so}. Further, let Φ = p1, . . . , pk q1, . . . , qm r1, . . . , rh s1, . . . , so C, where each constraint Ci in C = {C1, . . . , Cn} is over three variables vi,1, . . . , vi,li P Q R and vi,li+1, . . . vi,3 S, and forms allowed assignments {σ1, . . . , σ|Ci|} over . Now, we will deﬁne a DLmin knowledge-base K = (A, , ) over domain , and a non-ground Datalog program P such that K |= P if and only if Φ is valid.

Strat Tight Normal Disj

NEC ΣP 2 ΣP 3 ΣP 3 ΣP 4

(#)NEC[tw] 2| |Θ(k) 22| |Θ(k) 22| |O(k log(k)) 222| |Θ(k)

#NEC # NP # ΣP 2 # ΣP 2 # ΣP 3 #p NEC # ΣP 2 # ΣP 3 # ΣP 3 # ΣP 4

#p NEC[tw] 22| |Θ(k) 222| |Θ(k) 222| |O(k log(k)) 2222| |Θ(k)

Table 2: Combined complexity overview of the nonentailment problem variants over ﬁxed domain on speciﬁc bounded-arity Datalog programs from class C w.r.t. a SROIQ or DLmin knowledge-bases. For the tw-result, we assume ETH and omit polynomial factors in the instance size. All entries are completeness results or provide matching and lower bounds (under ETH), except parameterized results for class Normal, where we only have the slightly weaker lower bounds as for Tight.

Further, let the ABox A contain the following axioms: Selectv(xv) for all v {p1, . . . , pk}. We deﬁne program P as the union of following programs { W d Selectv(d) | v Q }, { W d Selectv(d) | v R }, Sn i=1{ sat Ci(θ) Selectvi,1(σ(vi,1)), . . . , Selectvi,li (σ(vi,li)) | θ: S(Ci) , σ Ci, li 1, θ = σ| S(Ci) }, Sn i=1{ sat Ci(θ) | θ: S(Ci) , σ Ci, li = 0, θ = σ| S(Ci) }, {sat sat C1( S(C1)), . . . , sat Cn( S(Cn)); sat}, {Selectv(d) sat | v R, d },where σ|X is function σ, but restricted to variables in X. Then, Φ is valid if and only if the entailment holds (also for every subset-minimal model). Observe that this also shows hardness for #NEDisj. Further, compared to the treewidth k of instance Σ, the treewidth k of GK,P is linear in k. The only large rule r P is the one with sat Hr, which can be split up in auxiliary rules such that k is linear in k.

The same idea can be used to lift these lower bounds (cf., Theorem 9) for the problem #p NE, as provided in Table 2.

5 Conclusion We provide a wide view on the combined complexity of the ﬁxed-domain non-entailment problem NE on speciﬁc bounded-arity Datalog programs with respect to a SROIQ or DLmin knowledge-bases. This approach combines open and closed world semantics in a very general way. We investigate the classical decision and counting complexity as well as the parameterized complexity of this problem when allowing for arbitrary disjunctive Datalog programs or restricting the program to be stratiﬁed, normal, or tight. Interestingly, by applying very recent advances in parameterized complexity, we immodestly obtain tight complexity results. A further research direction is to study our algorithm for practical applications and stronger parameters, e.g., (Grohe and Marx 2014; Greco et al. 2018), particularly, in the light of recent decomposition techniques (Gottlob, Okulmus, and Pichler 2020). Also enumeration complexity (Creignou et al. 2017, 2019; Meier 2020) is worth studying in this context.

Acknowledgements The work has been supported by FWF, Grants Y698, and P32830, WWTF Grant ICT19-065, and the German Research Foundation (DFG) under the project number ME 4279/1-2. Markus Hecher is also afﬁliated with the University of Potsdam, Germany. The authors would like to thank the anonymous reviewers for the valuable feedback they have provided.

References Apt, K. R.; Blair, H. A.; and Walker, A. 1988. Towards a theory of declarative knowledge. Foundations of deductive databases and logic programming 89 148.

Baader, F.; Horrocks, I.; Lutz, C.; and Sattler, U. 2017. An Introduction to Description Logic. Cambridge University Press, Cambridge. ISBN 9781139025355.

Baader, F.; Küsters, R.; and Wolter, F. 2003. Extensions to Description Logics. In Description Logic Handbook, 219 261. Cambridge University Press.

Baader, F.; Lutz, C.; Milicic, M.; Sattler, U.; and Wolter, F. 2005. Integrating Description Logics and Action Formalisms: First Results. In AAAI 05, 572 577.

Barceló, P.; Feier, C.; Lutz, C.; and Pieris, A. 2019. When is Ontology-Mediated Querying Efﬁcient? In LICS 19, 1 13.

Bienvenu, M.; Kikot, S.; Kontchakov, R.; Ryzhikov, V.; and Zakharyaschev, M. 2017. Optimal Nonrecursive Datalog Rewritings of Linear TGDs and Bounded (Hyper)Tree Width Queries. In Artale, A.; Glimm, B.; and Kontchakov, R., eds., In DL 17.

Bienvenu, M.; Ortiz, M.; Šimkus, M.; and Xiao, G. 2013. Tractable Queries for Lightweight Description Logics. In IJCAI 13, 768 774. AAAI Press. ISBN 9781577356332.

Bodlaender, H. L.; Drange, P. G.; Dregi, M. S.; Fomin, F. V.; Lokshtanov, D.; and Pilipczuk, M. 2016. A ck n 5Approximation Algorithm for Treewidth. SIAM J. Comput. 45(2): 317 378.

Bodlaender, H. L.; and Kloks, T. 1996. Efﬁcient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2): 358 402.

Calvanese, D. 2006. Finite Model Reasoning in Description Logics. In Patrick Doherty, John Mylopoulos, C. A. W., ed., KR 06, 292 303.

Creignou, N.; Ktari, R.; Meier, A.; Müller, J.; Olive, F.; and Vollmer, H. 2019. Parameterised Enumeration for Modiﬁcation Problems. Algorithms 12(9): 189.

Creignou, N.; Meier, A.; Müller, J.; Schmidt, J.; and Vollmer, H. 2017. Paradigms for Parameterized Enumeration. Theory Comput. Syst. 60(4): 737 758.

de Haan, R. 2018. Hunting for Tractable Languages for Judgment Aggregation. In Thielscher, M.; Toni, F.; and Wolter, F., eds., KR 18, 194 203. AAAI Press.

Dudek, J. M.; Phan, V. H. N.; and Vardi, M. Y. 2020. ADDMC: Weighted Model Counting with Algebraic Decision

Diagrams. In Conitzer, V.; and Sha, F., eds., AAAI 20, 1468 1476. Durand, A.; Hermann, M.; and Kolaitis, P. G. 2005. Subtractive reductions and complete problems for counting complexity classes. Theoretical Computer Science 340(3): 496 513. ISSN 0304 3975. 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. Eiter, T.; Ianni, G.; Lukasiewicz, T.; Schindlauer, R.; and Tompits, H. 2008. Combining answer set programming with description logics for the Semantic Web. Artiﬁcial Intelligence 172(12): 1495 1539. ISSN 0004-3702.

Eiter, T.; Pan, J. Z.; Schneider, P.; Šimkus, M.; and Xiao, G. 2015. A Rule-based Framework for Creating Instance Data from Open Street Map. In ten Cate, B.; and Mileo, A., eds., RR 15, 93 104. Springer. ISBN 978-3-319-22002-4. Fichte, J. K.; and Hecher, M. 2019. Treewidth and Counting Projected Answer Sets. In LPNMR 19, volume 11481 of LNCS, 105 119. Springer. Fichte, J. K.; Hecher, M.; and Hamiti, F. 2020. The Model Counting Competition 2020. Co RR 2012.01323. Fichte, J. K.; Hecher, M.; and Kieler, M. F. I. 2020. Treewidth-Aware Quantiﬁer Elimination and Expansion for QCSP. In CP 20. Springer. Fichte, J. K.; Hecher, M.; and Meier, A. 2018. Counting Complexity for Reasoning in Abstract Argumentation. In Hentenryck, P. V.; and Zhou, Z.-H., eds., AAAI 19. Fichte, J. K.; Hecher, M.; Morak, M.; and Woltran, S. 2017. Answer Set Solving with Bounded Treewidth Revisited. In Balduccini, M.; and Janhunen, T., eds., LPNMR 17, volume 10377 of LNCS, 132 145. Springer. ISBN 978-3-31961660-5. Fichte, J. K.; Hecher, M.; Morak, M.; and Woltran, S. 2018a. Exploiting Treewidth for Projected Model Counting and its Limits. In SAT 18, volume 10929 of LNCS, 165 184. Springer. ISBN 978-3-319-94144-8. Fichte, J. K.; Hecher, M.; and Pfandler, A. 2020. Lower Bounds for QBFs of Bounded Treewidth. In Kobayashi, N., ed., LICS 20, 410 424. Assoc. Comput. Mach., New York. Fichte, J. K.; Hecher, M.; and Schindler, I. 2018. Default Logic and Bounded Treewidth. In Klein, S. T.; and Martín Vide, C., eds., LATA 18, LNCS. Springer. Fichte, J. K.; Hecher, M.; Thier, P.; and Woltran, S. 2020. Exploiting Database Management Systems and Treewidth for Counting. In PADL, volume 12007 of LNCS, 151 167. Springer. Fichte, J. K.; Hecher, M.; Woltran, S.; and Zisser, M. 2018b. Weighted Model Counting on the GPU by Exploiting Small Treewidth. In Azar, Y.; Bast, H.; and Herman, G.,

eds., ESA 18, volume 112, 28:1 28:16. Dagstuhl Publishing. ISBN 978-3-95977-081-1.

Gaggl, S. A.; Rudolph, S.; and Schweizer, L. 2016. Fixed Domain Reasoning for Description Logics. In Kaminka, G. A.; Fox, M.; Bouquet, P.; Hüllermeier, E.; Dignum, V.; Dignum, F.; and van Harmelen, F., eds., ECAI 16, volume 285 of Frontiers in Artiﬁcial Intelligence and Applications, 819 827.

Gelfond, M.; and Lifschitz, V. 1991. Classical Negation in Logic Programs and Disjunctive Databases. New Generation Comput. 9(3/4): 365 386.

Gottlob, G.; Okulmus, C.; and Pichler, R. 2020. Fast and Parallel Decomposition of Constraint Satisfaction Problems. In Bessiere, C., ed., IJCAI 20, 1155 1162.

Gottlob, G.; Pichler, R.; and Wei, F. 2006. Bounded Treewidth as a Key to Tractability of Knowledge Representation and Reasoning. In AAAI 06, 250 256.

Gottlob, G.; Pichler, R.; and Wei, F. 2007. Efﬁcient datalog abduction through bounded treewidth. In AAAI, 1626 1631.

Gottlob, G.; and Szeider, S. 2007. Fixed-Parameter Algorithms For Artiﬁcial Intelligence, Constraint Satisfaction and Database Problems. The Computer Journal 51(3): 303 325. ISSN 0010-4620.

Greco, G.; Leone, N.; Scarcello, F.; and Terracina, G. 2018. Structural Decomposition Methods: Key Notions and Database Applications. In Flesca, S.; Greco, S.; Masciari, E.; and Saccà, D., eds., A Comprehensive Guide Through the Italian Database Research Over the Last 25 Years, 253 267. Springer Verlag. ISBN 978-3-319-61893-7.

Grohe, M. 2007. The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side. J. ACM 54(1). ISSN 0004-5411.

Grohe, M.; and Marx, D. 2014. Constraint solving via fractional edge covers. ACM Transactions on Algorithms 11(1): Art. 4, 20.

Hecher, M.; Thier, P.; and Woltran, S. 2020. Taming High Treewidth with Abstraction, Nested Dynamic Programming, and Database Technology. In Proceedings of the 23rd International Conference on Theory and Applications of Satisﬁability Testing (SAT 20), 343 360. Springer Verlag.

Hitzler, P.; Parsia, K. B.; Patel-Schneider, P. F.; and Rudolph, S. 2012. OWL 2 Web Ontology Language Primer. Technical report, W3C.

Horrocks, I.; Kutz, O.; and Sattler, U. 2006. The Even More Irresistible SROIQ. In Patrick Doherty, John Mylopoulos, C. A. W., ed., KR 06,57 67. AAAI Press. ISBN 9781577352716.

Horrocks, I.; and Sattler, U. 2007. A Tableau Decision Procedure for SHOIQ. J. Autom. Reason. 39(3): 249 276. ISSN 0168-7433.

Huang, S.; Li, Q.; and Hitzler, P. 2012. Reasoning with inconsistencies in hybrid MKNF knowledge bases. Logic Journal of the IGPL 21(2): 263 290. ISSN 1367-0751.

Impagliazzo, R.; Paturi, R.; and Zane, F. 2001. Which Problems Have Strongly Exponential Complexity? J. of Computer and System Sciences 63(4): 512 530. ISSN 00220000. Klinov, P. 2008. Pronto: A Non-monotonic Probabilistic Description Logic Reasoner. In Bechhofer, S.; Hauswirth, M.; Hoffmann, J.; and Koubarakis, M., eds., ESWC 08, 822 826. Springer. ISBN 978-3-540-68234-9. Kloks, T. 1994. Treewidth. Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer Verlag. ISBN 3-540-58356-4. Knublauch, H.; Musen, M. A.; and Rector, A. L. 2004. Editing Description Logic Ontologies with the Protégé OWL Plugin. In Haarslev, V.; and Möller, R., eds., DL 04, volume 104. Knuth, D. E. 1998. How fast can we multiply? In The Art of Computer Programming, volume 2 of Seminumerical Algorithms, chapter 4.3.3, 294 318. Addison-Wesley, 3 edition. Krötzsch, M.; Simancik, F.; and Horrocks, I. 2012. A Description Logic Primer. Co RR abs/1201.4089. Lin, F.; and Zhao, J. 2003. On tight logic programs and yet another translation from normal logic programs to propositional logic. In Gottlob, G.; and Walsh, T., eds., IJCAI 03, 853 858. Morgan Kaufmann. Ma, Y.; and Hitzler, P. 2010. Distance-based Measures of Inconsistency and Incoherency for Description Logics. In Haarslev, V.; Toman, D.; and Weddell, G. E., eds., DL 10, volume 573. Ma, Y.; Qi, G.; and Hitzler, P. 2011. Computing inconsistency measure based on paraconsistent semantics. J. Logic Comput. 21(6): 1257 1281. ISSN 0955-792X. Meier, A. 2020. Parametrised enumeration. Habilitation thesis, Leibniz Universität Hannover. Motik, B. 2006. Reasoning in description logics using resolution and deductive databases. Ph.D. thesis, Karlsruhe Institute of Technology, Germany. Pan, G.; and Vardi, M. Y. 2006. Fixed-Parameter Hierarchies inside PSPACE. In LICS 06, 27 36. IEEE Computer Society. Rosati, R. 2011. On the Complexity of Dealing with Inconsistency in Description Logic Ontologies. In Walsh, T., ed., IJCAI 11, 1057 1062. Simanˇcík, F.; Motik, B.; and Horrocks, I. 2014. Consequence-Based and Fixed-Parameter Tractable Reasoning in Description Logics. Artiﬁcial Intelligence 209: 29 77. ISSN 0004-3702.