=Paper=
{{Paper
|id=Vol-477/paper-9
|storemode=property
|title=Axiom Pinpointing is Hard
|pdfUrl=https://ceur-ws.org/Vol-477/paper_39.pdf
|volume=Vol-477
|dblpUrl=https://dblp.org/rec/conf/dlog/PenalozaS09
}}
==Axiom Pinpointing is Hard==
https://ceur-ws.org/Vol-477/paper_39.pdf
Axiom Pinpointing is Hard
Rafael Peñaloza and Barış Sertkaya?
Theoretical Computer Science TU Dresden, Germany
{penaloza,sertkaya}@tcs.inf.tu-dresden.de
Abstract. We investigate the complexity of several decision, enumera-
tion and counting problems in axiom pinpointing in Description Logics.
We prove hardness results that already hold for the propositional Horn
fragment. We show that for this fragment, unless p = np, all minimal
subsets of a given TBox that have a given consequence, i.e. MinAs, can-
not be enumerated in a specified lexicographic order with polynomial
delay. Moreover, we show that recognizing the set of all MinAs is at least
as hard as recognizing the set of all minimal transversals of a given hy-
pergraph, however whether this problem is intractable remains open. We
also show that checking the existence of a MinA that does not contain
any of the given sets of axioms, as well as checking the existence of a
MinA that contains a specified axiom are both np-hard. In addition we
show that counting all MinAs and counting the MinAs that contain a
certain axiom are both #p-hard.
1 Introduction
As the number and the size of DL-based ontologies grow, tools that support
knowledge engineers in improving and maintaining the quality of these ontologies
become more important. In real world applications often the knowledge engineer
not only wants to know whether her knowledge base has a certain (unwanted)
consequence or not, but also wants to know the reasons of this consequence.
Even for knowledge bases of moderate size, finding explanations for a given
consequence is not an easy task without getting support from an automated tool.
The task of finding explanations for a given consequence, i.e., finding minimal
subsets of the original knowledge base that have the given consequence is called
axiom pinpointing in the literature.
Axiom pinpointing has been considered by several authors. In [18] Schlobach
and Cornet have described an extension of the tableau-based satisfiability al-
gorithm for ALC that given an ALC knowledge base and a consequence of this
knowledge base computes all minimal subsets of the original knowledge base that
have the given consequence. The same problem had been addressed earlier in [1]
in the context of extending DLs by default rules. Later in [15] Parsia et al. have
extended the approach in [18] to more expressive DLs, and in [14] Lee et al. have
extended the approach in [1] to ALC knowledge bases with GCIs. In contrast to
?
Supported by the German Research Foundation (DFG) under grant BA 1122/12-1
these works on axiom pinpointing in expressive DLs, in [2] Baader et al. have ad-
dressed axiom pinpointing in the less expressive DL EL+ . They have investigated
the complexity of finding minimal subsets of a given EL+ TBox (there called
MinAs) that have a given consequence. They have shown that checking the exis-
tence of a MinA within a specified cardinality bound is np-complete. Moreover,
they have shown that a given consequence can have exponentially many MinAs
in a given EL+ TBox. Given this fact, it is definitely not possible to compute
all MinAs in polynomial time. Baader et al. have considered this problem in a
setting where the TBox has a so-called static part which is always present, and
a refutable part from which MinAs are computed. They have shown that in this
setting computing all MinAs cannot be performed in output polynomial time
unless p = np. In fact, all these hardness results are shown for the propositional
Horn fragment (there called HL), that allows for only conjunction and GCIs.
In the present paper we investigate the complexity of several decision, enu-
meration and counting problems related to MinAs. Following [2], we show our
hardness results for the logic HL. First we examine whether MinAs can be
enumerated in a specified lexicographic order with polynomial delay. It turns
out that even for HL already generating the lexicographically first MinA is
intractable, thus unless p = np, MinAs cannot be enumerated in a specified lexi-
cographic order with polynomial delay. Next we examine whether all MinAs can
be computed in output polynomial time without the static part considered in
the setting in [2]. We show that for this setting recognizing the set of all MinAs
is at least as hard as recognizing the set of all minimal transversals of a given
hypergraph, which is a prominent open problem [8] in hypergraph theory [4].
However, whether this problem is intractable remains open. Next we investigate
the problem of existence of a MinA that does not contain any of the given sets
of axioms. This problem, which can be useful in practical applications where one
wants to avoid certain combinations of axioms in the MinAs, turns out to be
np-hard. We also consider the problem of checking the existence of a MinA that
contains a specified axiom. We show that this problem is also np-hard. Finally,
we show that both counting all MinAs and counting the MinAs that contain a
certain axiom are #p-hard problems.
2 Complexity of computing all MinAs
In the present section we examine the complexity of computing all MinAs. The
hardness results we show in this work actually already hold for the propositional
Horn fragment HL. For this reason, from now on we are going to formulate our
problems for HL TBoxes. Note that HL is a sublogic of EL, which implies that
the lower bounds for the complexity found for HL also hold for EL and EL+ .
We start with formally defining some basic notions.
Definition 1. Let T be an HL TBox and C and D be two HL concept descrip-
tions such that C vT D. We call a set T 0 ⊆ T a minimal axiom set or MinA
for T w.r.t. C v D if C vT 0 D and it is minimal w.r.t. set inclusion. In this
case we also say that T ’ explains C v D.
Based on this, our problem is formulated as follows:
Problem: mina-enum
Input: An HL TBox T and a GCI C v D such that T |= C v D.
Output: The set of all MinAs for T w.r.t. C v D.
2.1 Enumerability with polynomial delay
In [2] it has been shown that there can be exponentially many MinAs for a given
HL TBox w.r.t. a given consequence of this TBox. Given this fact, it is definitely
not possible to solve mina-enum in polynomial time. In complexity theory, for
analyzing the performance of enumeration algorithms where the number of solu-
tions can be exponential in the size of the input, one considers other measures.
One such measure is the time the algorithm spends between two consequent
solutions. An algorithm is said to run with polynomial delay [13] if the time
until the first solution is generated, and thereafter the time between any two
consecutive solutions is bounded by a polynomial in the size of the input.
In the following we investigate whether it is possible to enumerate all MinAs
in a specified lexicographic order with polynomial delay. The lexicographic order
we will use is defined as follows:
Definition 2. Let the elements of a set S be linearly ordered. This order induces
another linear strict order on P(S), which is called the lexicographic order. We
say that a set R ⊆ S is lexicographically smaller than a set T ⊆ S where R 6= T
if the first element at which they disagree is in R.
Problem: first-mina
Input: An HL TBox T , a GCI C v D such that T |= C v D, a set S ⊆ T such
that S |= C v D, and a linear order on T .
Question: Is S the first MinA w.r.t. the lexicographic order induced by the given
linear order?
Theorem 1. first-mina is conp-complete.
Proof. The problem is in conp since if S is not the lexicographically first MinA,
a proof of this can be given by nondeterministically guessing a subset of T and
verifying in polynomial time that it is a MinA that is lexicographically smaller
than S.
In order to show conp-hardness, we are going to give a reduction from the
problem of checking whether a given maximal independent set is the lexicograph-
ically last maximal independent set of a given graph. Recall that a maximal
independent set of a graph G = (V, E) is a subset V 0 ⊆ V of the vertices such
that no two vertices in V 0 are joined by an edge in E, and each vertex in V \ V 0
is joined by an edge to some vertex in V 0 . This problem has been shown to be
conp-complete in [13].
Problem: last maximal independent set (last-mis)
Input: A graph G = (V, E), a maximal independent set S ⊆ V , and a linear order
on V .
Question: Is S the last maximal independent set w.r.t. the lexicographic order
induced by the given linear order?
Let an instance of last-mis be given with the graph G = (V, E) and the
maximal independent set S. From G and S we construct an instance of first-
mina as follows: For every v ∈ V we introduce a concept name Pv , for every edge
E ∈ E we introduce a concept name PE , and finally one more concept name A.
Using these we construct the TBox
l l
T := {Pv v PE | v ∈ V } ∪ { PE v A},
v∈E,E∈E E∈E
d
and the GCI v∈V Pv v A that obviously follows from T . Additionally, by
using S we construct a set S ⊆ T as:
l l
S := {Pv v PE | v ∈ (V \ S)} ∪ { PE v A}.
v∈E,E∈E E∈E
Note that T contains exactly |V | + 1 axioms. We order these axioms such that
an axiom with premise Pv comes before the axiom with premise Pv0 if and only
if the vertex v comes before thed vertex v 0 in the originally given linear order on
V . Finally we place the axiom E∈E PE v A as the last one. It is easy to see
that this construction indeed creates an instance
d of first-mina and the TBox
T , as well as the MinA S and the GCI v∈V Pv v A can be created in time
polynomial in the sizes of G and S. We claim that S is lexicographically the last
maximal independent set if and only if S is the lexicographically first MinA.
(⇒) Assume S is the lexicographically last maximal independent set. Then
V \S contains at least one vertex from every edge (i.e., it is a vertex cover), since
otherwise S would not be an independent set. Thus every d PE , for E ∈ E,
d appears
on thedrighthand side of at least one axiom in S. That is v∈V Pv vS E∈E PE ,
thus v∈V Pv vS A, i.e., S explains this axiom. Since S is maximal, V \ S is
minimal, and thus S is minimal, i.e., S is a MinA. Moreover, it is the lexico-
graphically first one since S is the lexicographically last maximal independent
set.
(⇐) Assume S is the lexicographically first MinA. Then every PE , for E ∈ E,
appears on the righthand side of at least one axiom in S, since otherwise it would
not be an explanation. That is, V \S contains at least one vertex from every edge.
Then S contains at most one vertex from every edge, i.e., it is an independent
set. Since S is minimal V \ S is minimal, and thus S is maximal, i.e., S is a
maximal independent set. Moreover it is the lexicographically last one since S
is the lexicographically first MinA. 2
Theorem 1 has the following consequence: Since generating the lexicograph-
ically first MinA is already intractable, unless p = np, all MinAs cannot be
enumerated in lexicographic order with polynomial delay.
Corollary 1. Unless p = np, there is no algorithm that enumerates MinAs in
a given lexicographic order with polynomial delay.
Interestingly, it is easy to generate the lexicographically last MinA for a given
TBox w.r.t. a given GCI. We start with the axioms in the specified order, and
remove an axiom if the resulting set of axioms still explains the given GCI. Once
we have scanned all axioms in this way, the resulting set of axioms is a MinA, and
it is the lexicographically last one. For a TBox of size n, i. e. having n axioms,
this operation requires at most n subsumption tests each of which can be done
in polynomial time for EL and EL+ . Nonetheless, it is still unclear whether this
fact can be used to enumerate all MinAs in the reverse lexicographical order.
2.2 Computability in output polynomial time
One other measure for analyzing the performance of enumeration algorithms
is to take into account not only the size of the input, but also the size of the
output. An algorithm is said to run in output polynomial time (or polynomial total
time) [13] if it outputs all solutions in time polynomial in the size of the input
and the output. One advantage of an output polynomial algorithm is that it runs
in polynomial time (in the size of the input) when there are only polynomially
many solutions.
In the following we investigate whether mina-enum can be solved in output
polynomial time. For solving this enumeration problem, the following decision
problem has crucial importance:
Problem: all-minas
Input: An HL TBox T , a GCI C v D such that T |= C v D, and T ⊆ P(T ).
Question: Is T precisely the set of all MinAs of T w.r.t. C v D?
As Proposition 1 below shows, if this problem cannot be decided in polynomial
time, then unless p = np, mina-enum cannot be solved in output polynomial
time.
Proposition 1. If all-minas cannot be decided in polynomial time, then unless
p = np, mina-enum cannot be solved in output-polynomial time.
Proof. Assume that we have an algorithm A that solves mina-enum in output-
polynomial time. Let its runtime be bounded by a polynomial p(IS, OS) where
IS denotes the size of the input TBox and OS denotes the size of the output,
i.e., the set of all MinAs.
In order to decide all-minas for an instance given by the TBox T , the GCI
C v D, and a set T ⊆ P(T ), we construct another algorithm A0 that works
as follows: it runs A on T and C v D for at most p(|T |, |T |)-many steps. If A
terminates within this many steps, then A0 compares the output of A with T
and returns yes if and only if they are equal. If they are not equal, A0 returns
no. If A has not yet terminated after p(|T |, |T |)-many steps, this implies that
there is at least one MinA that is not contained in T , so A0 returns no. It is easy
to see that the runtime of A0 is bounded by a polynomial in |T | and |T |, that is
A0 decides all-minas in time polynomial in the size of the input. 2
The proposition shows that determining the complexity of all-minas is in-
deed crucial for determining the enumeration complexity of mina-enum. It is
not difficult to see that all-minas is in conp. Given an instance of all-minas,
a nondeterministic algorithm can guess a subset of T that is not in T , and in
polynomial time verify that this is a MinA, thus T is not the set of all MinAs.
In the following we show that all-minas is at least as hard as recognizing the
set of all minimal transversals of a given hypergraph. However, whether it is
conp-hard remains unfortunately open.
First we briefly recall some notions of hypergraphs. A hypergraph H = (V, E)
consists of a set of vertices V = {vi | 1 ≤ i ≤ n}, and a set of (hyper)edges
E = {Ej | 1 ≤ j ≤ m} where Ej ⊆ V . Following the convention in [4], we assume
that the set of edges as well as the set of vertices is nonempty, and the union
of all edges yields the vertex set. A set W ⊆ V is called a transversal of H if it
intersects all edges of H, i.e., ∀E ∈ E. E ∩W 6= ∅. A transversal is called minimal
if no proper subset of it is a transversal. The set of all minimal transversals of
H constitute another hypergraph on V called the transversal hypergraph of H,
which is denoted by T r(H). Generating T r(H) is an important problem which
has applications in many fields of computer science (see e.g. [9]). The well-known
decision problem associated to this computation problem is defined as follows:
Problem: transversal hypergraph (trans-hyp)
Input: Two hypergraphs H = (V, EH ) and G = (V, EG ).
Question: Is G the transversal hypergraph of H, i.e., does T r(H) = G hold?
trans-hyp is known to be in conp, but so far neither a polynomial time algo-
rithm has been found, nor has it been proved to be conp-hard. In a landmark
paper [10] Fredman and Khachiyan proved that trans-hyp can be solved in
no(log n) time, which implies that this problem is most likely not conp-hard. It is
conjectured that this problem, together with several computationally equivalent
problems, forms a class properly contained between p and conp [10].
Theorem 2. all-minas is trans-hyp-hard.
Proof. Let an instance of trans-hyp be given by the hypergraphs H = (V, EH )
and G = (V, EG ). From H and G we construct an instance of all-minas as
follows: for every vertex v ∈ V we introduce a concept name Pv , for every edge
E ∈ EH of H a concept name PE , and finally one additional concept name A.
For a set of vertices F ⊆ V , we define the TBox
l l
TF := {Pv v PE | v ∈ F } ∪ { PE v A}.
v∈E,E∈EH E∈EH
Using these we construct the d TBox T := TV , a set of TBoxes T := {TF | F ∈
EG } ⊆ P(T ), and the GCI v∈V Pv v A that obviously follows from T .
It is easy to see that this construction indeed creates d
an instance of all-
minas, and the TBox T , as well as the set T and the GCI v∈V Pv v A can be
constructed in time polynomial in the sizes of H and G. We claim that G is the
transversaldhypergraph of H if and only if T is precisely the set of all MinAs.
Note that E∈EH PE v A is the only axiom in T that has A in its right-hand
side; this implies that every MinA must contain this axiom. Hence, every MinA
is of the form TF for some F ⊆ V . To prove our claim, it suffices to show that a
set of vertices F ⊆ V is a minimal transversal of H if and only if the TBox TF
is a MinA.
(⇒) Assume that F is a minimal transversal of H. By definition F satisfies
F ∩ E 6= ∅ for every E ∈ EH . Then TF is an axiom set explaining the above
GCI. Moreover,
d it is minimal since F is minimal. Thus, it is indeed a MinA for
T w.r.t. v∈V Pv v A.
(⇐) Now assume that TF is a MinA. Then for every PE (where E ∈ EH )
there is at least one axiom in TF with lefthand side Pv (where v ∈ F and F ∈ EG )
such that Pv is subsumed by PE . That is F intersects every E ∈ EH , i.e., F is
a transversal. Moreover, it is minimal since the original set of axioms TF is a
minimal axiom set.
It is not difficult to see that from the above it follows that G is the transversal
hypergraph of H if and only if T := {TF | F ∈ EG } is the set of all MinAs. 2
3 Preferred and unwanted axioms
Next we consider the problem of computing MinAs that contain a preferred
axiom and MinAs that do not contain some unwanted combination of axioms.
First we investigate the problem of existence of a MinA that does not contain
any of the given sets of axioms. This problem can be useful in applications where
one wants to avoid certain combinations of axioms in the MinAs. It is defined
as follows:
Problem: add-mina
Input: An HL TBox T , a GCI C v D such that T |= C v D, and T ⊆ P(T ).
Question: Is there a MinA T 0 that satisfies S 6⊆ T 0 for every S ∈ T ?
Theorem 3. add-mina is np-complete.
Proof. The problem is clearly in np. A nondeterministic algorithm for solving it
first guesses a T 0 ⊆ T , then tests in polynomial time whether T 0 is a MinA that
does not contain any of the S in T .
Hardness is shown by a reduction from the following np-hard problem [12]:
Problem: hypergraph 2-coloring
Input: A hypergraph H = (V, E).
Question: Is H 2-colorable, i.e., is there a W ⊆ V such that for all E ∈ E,
W ∩ E 6= ∅ and (V \ W ) ∩ E 6= ∅?
Let an instance of hypergraph 2-coloring be given with the hypergraph
H = (V, E). From H we construct an instance of add-mina as follows: just like
in the construction in the proof of Theorem 2, we introduce a concept name
Pv for every v ∈ V , a concept name PE for every edge E ∈ E, and finally one
more
d concept name A. We also construct exactly the same TBox T and the GCI
v∈V Pv v A constructed there. In addition to these, for an edge E ∈ E we
define the set
l l
VE := {Pv v PF | v ∈ E} ∪ { PF v A},
v∈F,F ∈E F ∈E
and using this construct the set
T := {VE | E ∈ E}.
It is easy to see that the TBox T , the GCI above and the set T can be constructed
in time polynomial in the size of d H. We claim that H is 2-colorable if and only
if there is a MinA T 0 for T w.r.t. v∈V Pv v A such that T 0 satisfies S 6⊆ T 0 for
every S ∈ T .
(⇒) Assume H is 2-colorable. Then there is a W ⊆ V such that W ∩ E 6= ∅
and (V \ W ) ∩ E 6= ∅ for every E ∈ E, i.e., both W and its complement are
transversals of H. Assume
d w.l.o.g. that W is minimal.
d Using W we define the
set TW := {Pv v v∈E,E∈E PE | v ∈ W } ∪ { E∈E PE v A} and claim that
this is the MinA we are looking for. Since W is a transversal every PE , for
E ∈ E, appearsd on the righthand
d d side of at least one axiom in TW . That is
v∈V P v v T W E∈E P E , thus v∈V Pv vTW A, i.e., TW explains this axiom.
TW is minimal since W is minimal. Moreover, since V \ W is also a transversal,
every edge E ∈ E contains at least one vertex d v that is not in W . Thus, every
VE ∈ T contains at least one axiom Pv v v∈F,F ∈E PF that is not in TW . That
is TW is a MinA that is not a superset of any VE ∈ T .
(⇐) Assume there is adMinA T 0 that is not a superset of any VE ∈ T . Define
the set WT 0 := {v | Pv v v∈E,E∈E PE ∈ T 0 }. Since T 0 explains the constructed
GCI, for every E ∈ E it contains at least one axiom in whose righthandside
PE occurs. That is, WT 0 intersects every E ∈ E. Since T 0 is not a superset of
any VE ∈ T , every such VE contains at least one axiom that is not in T 0 . This
means that every E ∈ E contains at least one vertex that is not in WT 0 . That is,
V \ WT 0 intersects every E ∈ E. Thus we have shown that WT 0 is a 2-coloring
of H. 2
Next we consider the dual problem, which is checking the existence of a MinA
that contains a certain axiom. This problem can be useful in applications where
one is interested in MinAs that contain a specific axiom, and is known as the
relevance problem:
Problem: mina-relevance
Input: An HL TBox T , a GCI C v D such that T |= C v D, and an axiom
t∈T.
Question: Is there a MinA S of T w.r.t. C v D such that t ∈ S?
If one could efficiently solve the relevance problem, then black-box techniques
for computing the set of all MinAs (see, e.g. [3, 20]) based on Reiter’s Hitting
Set Tree algorithm [16] could benefit from Rymon’s further optimizations [17].
As we will show next, this problem is also np-hard.
Theorem 4. mina-relevance is np-complete.
Proof. The problem is clearly in np. A nondeterministic algorithm for solving it
first guesses a subset of T , then tests in polynomial time whether it is a MinA
containing t. For showing hardness we are going to give a reduction from the
following np-complete problem in [11, 7]:
Problem: horn-relevance
Input: Two sets of propositional variables H and M , a set T of definite Horn
clauses over H ∪ M , and a propositional variable p ∈ H.
Question: Is there a minimal H 0 ⊆ H such that H 0 ∪ T |= M and p ∈ H 0 ?
Recall that a definite Horn clause is a Horn clause with V exactly one positive
literal, i.e., the elements of T are formulae of the form g∈G g → f , where
G ⊆ H ∪ M and f ∈ H ∪ M . Given an instance of horn relevance we
construct an instance of mina-relevance as follows: for every propositional
variable h ∈ H we introduce a concept name Ph , for every propositional variable
m ∈ M we introduce a concept name Pm , and finally two more fresh concept
names A and B. Using these we construct the TBox
l ^ l
T := {A v Ph | h ∈ H} ∪ { P g v Pf | g → f ∈ T} ∪ { Pm v B}
g∈G g∈G m∈M
where G ⊆ H ∪ M and f ∈ H ∪ M . Using A and B we construct the GCI A v B.
This construction indeed creates an instance of mina-relevance and it can be
done in polynomial time. We claim that there is a minimal H 0 ⊆ H such that
H 0 ∪ T |= M and p ∈ H 0 if and only if there is a MinA S of T w.r.t. A v B such
that A v Pp ∈ S.
(⇒) Assume there is a minimal H 0 ⊆ H such that H 0 ∪ T |= M and p ∈ H 0 .
Using H 0 define the set
l ^ l
TH 0 := {A v Ph | h ∈ H 0 } ∪ { Pg v P f | g → f ∈ T} ∪ { Pm v B}.
g∈G g∈G m∈M
TH 0 explains A v B since H 0 ∪ T |= M . It is minimal since H 0 is minimal, and
A v Pp ∈ TH 0 since p ∈ H 0 .
(⇐) Assume there is a MinA d S such that A v Pp ∈ S. Since it explains
A
d v B it contains the axiom m∈M Pm v B, contains axioms of the form
g∈G P g v P f such that for every m ∈ M the concept name Pm occurs on the
righthand side of at least one such
d axiom. Additionally S contains axioms of the
form A v Ph such that A vS m∈M Pm . Then the set S = {h | A v Ph ∈ S}
satisfies S ∪ T |= M . Moreover p ∈ S since A v Pp ∈ S, and S is minimal since
S is minimal. 2
4 Counting MinAs
In applications where one is interested in computing all MinAs, it might also
be useful to know in advance how many of them exist. Next we consider this
counting problem. It turns out that this is hard for the counting complexity
class #p [21], which is defined as the class of functions counting the number of
accepting paths of nondeterministic Turing machines.
Problem: #mina
Input: An HL TBox T and a GCI C v D such that T |= C v D.
Output: The number of all MinAs of T w.r.t. C v D.
Theorem 5. #mina is #p-complete.
Proof. The problem is clearly in #p. Given an HL TBox T , a GCI C v D that
follows from T and a candidate solution T 0 ⊆ T , we can in polynomial time
verify that T 0 is a MinA.
For showing #p-hardness, we are going to give a parsimonious reduction from
#hypergraph transversal, which is the problem of counting the minimal
transversals of a given hypergraph H. It has been shown to be #p-complete in
[6]. In the reduction, from a given hypergraph H we construct the same TBox
and the GCI constructed in the proof of Theorem 2. Note that this construction
establishes
d a bijection between the minimal transversals of H and MinAs of T
w.r.t. v∈V Pv v A. That d is, a W ⊆ V is a minimal d transversal of H if and only
if the set T := {Pv v v∈E,E∈EH PE | v ∈ W } ∪ { E∈EH PE v A} defined using
W is a MinA. That is, this construction preserves the number of solutions, i.e.,
it is parsimonious. 2
Instead of counting all MinAs, one can also try to count the MinAs that
contain a specific axiom. If we are trying to explain an unwanted consequence,
the solution of this counting problem will allow us to detect axioms that are
most likely to be faulty, i. e. those that appear in the most MinAs. This idea has
been proposed in [19] as a heuristic for correcting an error while minimizing the
changes in the set of axioms.
Problem: #mina-relevance
Input: An HL TBox T , a GCI C v D such that T |= C v D and an axiom
t∈T.
Output: The number of all MinAs of T w.r.t. C v D that contain t.
Theorem 6. #mina-relevance is #p-complete.
Proof. The problem is in #p since given an HL TBox T , a GCI C v D that
follows from T an axiom t ∈ T and a candidate solution T 0 ⊆ T , we can in
polynomial time verify that T 0 is a MinA and it contains t.
We show #p-hardness by a parsimonious reduction from #mina, which has
been shown to be #p-complete above. Given an instance of #mina with the
TBox T and the GCI A v B we construct the TBox T 0 := T ∪ S0 , where
S0 = {A v C, B u C v D}, and C and D are two concept names not occurring
in T . It is not difficult to see that a set S ⊆ T is a MinA for T w.r.t. A v B
if and only if S ∪ S0 is a MinA for T 0 w.r.t. A v D. Moreover, every MinA for
T 0 w.r.t. A v D contains the axioms in S0 . Thus, there are exactly as many
MinAs for T w.r.t. A v B as there are for T 0 w.r.t. A v D containing the axiom
A v C. 2
5 Concluding remarks and future work
We have analyzed the complexity of finding all the MinAs for a given HL TBox,
and some other related problems in axiom pinpointing. The bottom line of this
analysis is that axiom pinpointing is hard, even in this restricted setting, where
we can only express conjunctions and implications. Obviously, the hardness re-
sults transfer to any logic more expressive than HL with GCIs. It is however
unclear whether better bounds can be obtained if we restrict our attention to
acyclic TBoxes, or to logics like DL-Lite [5] in which conjunction is not allowed
on the lefthand side of the axioms.
One problem that remains open is the exact complexity of computing all
MinAs. In [2] it was shown that if we allow for an irrefutable portion of the
TBox, then there cannot be an algorithm that outputs all MinAs in output
polynomial time. Here we show that if all axioms are refutable then this problem
is at least as hard as generating the minimal transversals of a given hypergraph.
However, whether it is intractable remains open. As future work, we are going to
work on determining whether this problem is intractable or it is computationally
equivalent to generating minimal transversals.
Another branch for future work refers to efficiently finding approximate so-
lutions for the hard problems presented here. For instance finding an approxi-
mation to the total number of MinAs allows us at least to get an idea on how
problematic is a given (unwanted) consequence. Alternatively, a set of axioms
that explains a given consequence but is not necessarily minimal, can be helpful
for a better understanding of the given consequence.
References
1. F. Baader and B. Hollunder. Embedding defaults into terminological representation
systems. Journal of Automated Reasoning, 14:149–180, 1995.
2. F. Baader, R. Peñaloza, and B. Suntisrivaraporn. Pinpointing in the description
logic EL+ . In J. Hertzberg, M. Beetz, and R. Englert, editors, Proceedings of
the 30th German Conference on Artificial Intelligence (KI2007), volume 4667 of
Lecture Notes in Artificial Intelligence, pages 52–67. Springer-Verlag, 2007.
3. F. Baader and B. Suntisrivaraporn. Debugging SNOMED CT using axiom pin-
pointing in the description logic EL+ . In Proceedings of the International Con-
ference on Representing and Sharing Knowledge Using SNOMED (KR-MED’08),
Phoenix, Arizona, 2008.
4. C. Berge. Hypergraphs. Elsevier Science Publishers B.V. (North Holland), 1989.
5. D. Calvanese, G. D. Giacomo, M. Lenzerini, R. Rosati, and G. Vetere. DL-Lite:
Practical reasoning for rich DLs. In Proceedings of the 2004 Description Logic
Workshop (DL 2004), volume 104 of CEUR Electronic Workshop Proceedings,
http://ceur-ws.org/, 2004.
6. A. Durand and M. Hermann. On the counting complexity of propositional circum-
scription. Information Processing Letters, 106(4):164–170, 2008.
7. T. Eiter and G. Gottlob. The complexity of logic-based abduction. Journal of the
ACM, 42(1):3–42, 1995.
8. T. Eiter and G. Gottlob. Identifying the minimal transversals of a hypergraph and
related problems. SIAM Journal on Computing, 24(6):1278–1304, 1995.
9. T. Eiter and G. Gottlob. Hypergraph transversal computation and related prob-
lems in logic and AI. In S. Flesca, S. Greco, N. Leone, and G. Ianni, editors,
Proceedings of the European Conference on Logics in Artificial Intelligence (JELIA
2002), volume 2424 of Lecture Notes in Computer Science, pages 549–564. Springer-
Verlag, 2002.
10. M. L. Fredman and L. Khachiyan. On the complexity of dualization of monotone
disjunctive normal forms. Journal of Algorithms, 21(3):618–628, 1996.
11. G. Friedrich, G. Gottlob, and W. Nejdl. Hypothesis classification, abductive di-
agnosis and therapy. In G. Gottlob and W. Nejdl, editors, Proceedings of the
International Workshop on Expert Systems in Engineering, Principles and Appli-
cations, volume 462 of Lecture Notes in Computer Science, pages 69–78, Viena,
Austria, 1990. Springer-Verlag.
12. M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the
Theory of NP-Completeness. W. H. Freeman & Company, New York, NY, USA,
1990.
13. D. S. Johnson, M. Yannakakis, and C. H. Papadimitriou. On generating all maxi-
mal independent sets. Information Processing Letters, 27(3):119–123, 1988.
14. K. Lee, T. Meyer, and J. Z. Pan. Computing maximally satisfiable terminologies
for the description logic ALC with GCIs. In B. Parsia, U. Sattler, and D. Toman,
editors, Proceedings of the International Workshop on Description Logics (DL’06),
Lake District, UK, 2006.
15. B. Parsia, E. Sirin, and A. Kalyanpur. Debugging OWL ontologies. In A. Ellis
and T. Hagino, editors, Proceedings of the 14th international conference on World
Wide Web (WWW 2005), pages 633–640. ACM, 2005.
16. R. Reiter. A theory of diagnosis from first principles. Artificial Intelligence,
32(1):57–95, 1987.
17. R. Rymon. Search through systematic set enumeration. In B. Nebel, C. Rich, and
W. Swartout, editors, Proceedings of the International Conference on the Principles
of Knowledge Representation and Reasoning (KR’92), pages 539–550, Cambridge,
MA, USA, 1992.
18. S. Schlobach and R. Cornet. Non-standard reasoning services for the debugging
of description logic terminologies. In G. Gottlob and T. Walsh, editors, Proceed-
ings of the Eighteenth International Joint Conference on Artificial Intelligence (IJ-
CAI’03), pages 355–362. Morgan Kaufmann, 2003.
19. S. Schlobach, Z. Huang, R. Cornet, and F. Harmelen. Debugging incoherent ter-
minologies. Journal of Automated Reasoning, 39(3):317–349, 2007.
20. B. Suntisrivaraporn, G. Qi, Q. Ji, and P. Haase. A modularization-based ap-
proach to finding all justifications for OWL DL entailments. In J. Domingue
and C. Anutariya, editors, Proceedings of the 3rd Asian Semantic Web Confer-
ence (ASWC’08), volume 5367 of Lecture Notes in Computer Science, pages 1–15.
Springer-Verlag, 2008.
21. L. G. Valiant. The complexity of computing the permanent. Theoretical Computer
Science, 8(2):189–201, 1979.