We show that ELI queries (ELIQs) are learnable in polynomial time in the presence of a DL-Lite ontology O, in Angluin's framework of active learning. When initially provided with a conjunctive query (CQ) that implies the target ELIQ under O (in the sense of query containment), it su ces for the learner to only pose membership queries to the oracle, but no equivalence queries. The initial CQ can be obtained by a single equivalence query and is available `for free' in case that O does not pose any disjointness constraints on concepts. Our main technical result is that every ELI concept has only polynomially many most speci c subsumers w.r.t. a DL-Lite ontology, generalizing a recent result about homomorphism frontiers by ten Cate and Dalmau.
Constructing description logic (DL) concepts, ontologies, and queries can be
challenging and costly, especially when logic expertise and domain knowledge
are not in the same hands. This has prompted many approaches to learning such
objects, including PAC learning [
The interest in exact learning in DLs started with an investigation of ontology
learning in (the conference version of) [
Learner and oracle both know and agree on the ontology O and the concept and role names that are available for constructing the target ELIQ qT which must be satis able w.r.t. O; we assume that this includes all concept and role names in O. In a membership query, the learner provides an ABox A and a candidate answer a and asks whether A; O j= qT (a); the oracle faithfully answers \yes" or \no". In an equivalence query, the learner provides a hypothesis ELIQ qH and asks whether qH is equivalent to qT under O; the oracle answers \yes" or provides a counterexample, that is, an ABox A and tuple a such that A; O j= qT (a) and A; O 6j= qH (a) (positive counterexample) or vice versa (negative counterexample). One is then interested in polynomial time learnability, that is, whether there is a learning algorithm that constructs qT (x), up to equivalence w.r.t. O, such that at any given time, the running time of the algorithm is bounded by a polynomial in the sizes of qT , of O, and of the largest counterexample given by the oracle so far. A weaker requirement is polynomial query learnability where only the sum of the sizes of the queries posed to the oracle up to the current time point has to be bounded by such a polynomial.
We can now state our main result more precisely. With DL-Lite, we generally
refer to the basic member of the DL-Lite family [
Let us mention two interesting perspectives on our results. First, they
generalize the results in [
A core technical result underlying our approach is that the frontier of an
ELIQ q w.r.t. a DL-Lite ontology is only of polynomial size and can be computed
in polynomial time, generalizing a similar result from [
Proof details are given in the appendix of the long version of this paper, available at http://www.informatik.uni-bremen.de/tdki/research/papers. html. 2
Ontologies and ABoxes. Let NC, NR, and NI be countably in nite sets of concept, role and individual names. A role R is a role name r or the inverse r of a role name. A basic concept B is >, a concept name A, or of the form 9R, R a role. A DL-Lite ontology O is a nite set of (basic) concept inclusions B1 v B2, concept disjointness constraints B1 u B2 v ?, and role disjointness constraints R1 u R2 v ?. A DL-Lite ontology is a DL-Lite ontology that contains no concept disjointness constraints. A DL-Lite ontology is in normal form if all concept inclusions in it are of the form A v B or B v A with A a concept name or > and B a basic concept. An ABox A is a nite set of concept assertions A(a) and role assertions r(a; b) with A a concept name or >, r a role name, and a; b individual names. We use ind(A) to denote the set of individual names used in A.
The semantics is de ned as usual in terms of interpretations I, which we de ne to be a (possibly in nite and) non-empty set of concept and role assertions. We use I to denote the set of individual names in I, de ne AI = fa j A(a) 2 Ig for all A 2 NC, and rI = f(a; b) j r(a; b) 2 Ig and (r )I = f(b; a) j r(a; b) 2 Ig for all r 2 NR. We further set >I = I and (9R)I = fa 2 I j 9(a; b) 2 RI g for all roles R. This de nition of interpretation is slightly di erent from the usual one, but equivalent;2 its virtue is uniformity as every ABox is a nite interpretation. An interpretation I satis es a concept inclusion B1 v B2 if B1I B2I , a concept 1 One could equivalently say that F is the set of LCSs of a single concept which strictly generalize that concept. 2 This depends on admitting assertions >(a) in ABoxes. disjointness constraint B1 u B2 v ? if B1I \ B2I = ;, and a role disjointness constraint R1 u R2 v ? if R1I \ R2I = ;.
An interpretation is a model of a DL-Lite ontology or an ABox if it satis es all concept inclusions, disjointness constraints and assertions in it. We write O j= B1 v B2 if every model of O satis es the basic concept inclusion B1 v B2 and A; O j= B(a) if every model of A and O satis es the concept assertion B(a). An ABox A is satis able w.r.t. a DL-Lite ontology O if A and O have a common model.
A signature is a set of concept and role names, uniformly referred to as symbols. For any syntactic object O such as an ontology or an ABox, we use sig(O) to denote the symbols used in O and jjOjj to denote the size of O, that is, the length of a representation of O as a word in a suitable alphabet. Conjunctive Queries, ELIQs, Homomorphisms. A conjunctive query (CQ) takes the form q(x) (x; y) where is a conjunction of concept atoms A(x), with A 2 NC, and role atoms r(x; y), with r 2 NR over variables x; y 2 x [ y. We may write r (x; y) in place of r(y; x). We refer to the variables in x as answer variables and to the variables in y as quanti ed variables. We use var(q) to denote the set of all variables in x and y. We may view a CQ q(x) as a set of atoms when convenient and write r(x; y) 2 q(x) to mean that r(x; y) occurs in the conjunction .
A conjunctive query q(x) is unary if q(x) only has a single answer variable. A
cycle in a CQ q is a sequence R1(x1; x2); : : : ; Rn(xn; x1) of distinct role atoms in q
such that x1; : : : xn are distinct. An ELIQ is a unary CQ q that does not contain
a cycle and such that the undirected graph Gq = (var(q); ffy; zg j r(y; z) 2
qg) is connected. Note that every ELIQ can be seen as an ELI concept in a
straightforward way and vice versa; see [
A homomorphism h from interpretation I1 to interpretation I2 is a mapping from I1 to I2 such that d 2 AI1 implies h(d) 2 AI2 and (d; e) 2 rI1 implies (h(d); h(e)) 2 rI2 . We use img(h) to denote the set fe 2 I2 j 9d 2 I1 : h(d) = eg. For di 2 Ii , i 2 f1; 2g, we write I1; d1 ! I2; d2 if there is a homomorphism h from I1 to I2 with h(d1) = d2. With a homomorphism from a CQ q to an interpretation I, we mean a homomorphism from Aq to I. For a unary CQ q(x), we write q(x) ! (I; d) if there is a homomorphism h from q to I with h(x) = d. Let q(x) be a unary CQ and I an interpretation. An element d 2 I is an answer to q in I, written I j= q(d), if q(x) ! (I; d). Now let O be a DL-Lite ontology and A an ABox. An individual a 2 ind(A) is an answer to q on A w.r.t. O, written A; O j= q(a), if a is an answer to q in every model of O and A.
For q1 and q2 unary CQs and O a DL-Lite ontology, we say that q1 is contained in q2 w.r.t. O, written q1 O q2 if for all ABoxes A and a 2 ind(A), A; O j= q1(a) implies A; O j= q2(a). We call q1 and q2 equivalent w.r.t. O, written q1 O q2, if
O q1.
O-saturatedness and O-minimality. The following two technical notions are used throughout this paper. A CQ q is O-saturated, with O a DL-Lite ontology, if Aq; O j= A(y) implies A(y) 2 q for all y 2 var(q) and A 2 NC. It is O-minimal if there is no S ( var(q) such that q O qjS with qjS the restriction of q to the atoms that only contain variables in S.
The following is a consequence of the fact that acyclic CQs over DL-Lite
ontologies can be answered in polynomial time [
Lemma 1. Given an ELIQ q and a DL-Lite ontology O, we can nd in polynomial time an O-saturated and O-minimal ELIQ q0 with q O q0. Universal Model. Let O be a DL-Lite ontology and A an ABox that is satis able w.r.t. O. A trace for A and O is a sequence t = aR1 : : : Rn, n 0, such that a 2 ind(A), the basic concepts 9R1; : : : ; 9Rn occur in O, A; O j= 9R1(a), and O j= 9Ri v 9Ri+1 for 1 i < n. Let T denote the set of all traces for A and O. Then the universal model of A and O is
UA;O = A [ fA(a) j A; O j= A(a)g [ fA(tR) j tR 2 T and O j= 9R v Ag [ fR(t; tR) j tR 2 Tg: For brevity, we write Uq;O instead of UAq;O for any conjunctive query q. 3
We show that for every ELIQ q and DL-Lite ontology O such that q is satis able
w.r.t. O, there is a frontier of polynomial size that can be computed in polynomial
time. This generalizes a result from [
De nition 1. A frontier of an ELIQ q w.r.t. a DL-Lite ontology O is a nite set of ELIQs F such that 1. q O qF for all qF 2 F ; 2. qF 6 O q for all qF 2 F ; 3. for all ELIQs q0 with q
O q0.
It is not hard to see that frontiers that are minimal w.r.t. set inclusion are unique up to equivalence of the ELIQs in them, that is, if F1 and F2 are minimal frontiers of q w.r.t. O, then for every qF 2 F1, there is a qF0 2 F2 such that qF O qF0 , and vice versa. The following is the main result of this section.
Theorem 1. Let O be a DL-Lite ontology and q an ELIQ that is satis able w.r.t. O. Then a frontier of q w.r.t. O can be computed in polynomial time. For proving Theorem 1, we rst observe that we can concentrate on ontologies that are in normal form.
Lemma 2. For every DL-Lite ontology O, we can construct in polynomial time a DL-Lite ontology O0 in normal form such that for every ELIQ q, a frontier of q w.r.t. O can be constructed in polynomial time given a frontier of q w.r.t. O0.
The normalization of O introduces fresh concept names X9R that represent the basic concept 9R. In the proof of Lemma 2, we construct the frontier of q w.r.t. O0 by replacing atoms X9R(x) with atoms R(x; y), y a fresh variable.
Now we start with the proof of Theorem 1. Let O and q(x) be as in the formulation of the theorem, O in normal form. By Lemma 1 and the fact that equivalent queries have the same frontiers, we can assume that q is O-saturated and O-minimal. To construct a frontier of q w.r.t. O, we consider all ways to weaken q in a minimal way where weakening means to construct from q an ELIQ q0 such that q O q0 and q0 6 O q.
We start with some notation. We view the answer variable x of q as the root of the undirected tree Gq, thus imposing a direction on this tree which allows us to use notions for directed trees, such as successor, predecessor, and leaf, for the variables in q. Note that the imposed direction is unrelated to the direction of (inverse) roles in atoms in q. For every z 2 var(q), we use qz to denote the ELIQ obtained from q by taking the subtree of Gq rooted at z and making z the answer variable. For each variable y 2 var(q), we de ne a set y of atoms in q that mention y and represent options that we have for weakening q. Formally, y contains { all role atoms R(y; z) 2 qy and { all concept atoms A(y) 2 q such that (i) there is no B(y) 2 q with O j= B v A and O 6j= A v B and (ii) there is no R(y; z) 2 q with O j= 9R v A.
Informally, we can weaken q by choosing a y 2 var(q) and then removing a concept atom A(y) 2 y or a role atom R(y; z) 2 y as well as the subtree of q rooted at variable z. However, such removals alone are not enough to obtain a minimal weakening of q and must be accompanied by certain additions, as detailed below. Note that Conditions (i) and (ii) are needed to ensure that removing A(y) indeed weakens q, that is, the resulting query is not equivalent to q w.r.t. O.
We de ne a set of ELIQs Fq(y) for every variable y 2 var(q), by induction on the codepth of y in q. The set Fq(x) ultimately obtained is a frontier of q w.r.t. O. For every y 2 var(q), set
Fq(y) = fq (y) j 2 yg where q (y) is constructed by starting with qy(y) and then doing the following: 1. if = A(y), remove all atoms B(y) with O j= A B (including ); 2. if = R(y; z), remove and all atoms of qz. For each q (z) 2 Fq(z), add a disjoint copy q~ of q and the role atom R(y; z~) where z~ is the copy of z in q~ ; 3. for each S(y; z1) 2 qy with S(y; z1) 6= , add a disjoint copy q0 of q and the role atom S(y0; z1) where y0 is the copy of y in q0;
R3
R y^ y z qz z1 qz1
R1
R2 yR2
R1 q y0 z1 qz1
R1 z0 q 1 y^0 y R : : : : : :
R3
R
R2 z0 q n q y0
R2
yR2
4. for each S(y; yS) 2 Uqy;O with yS a trace such that O 6j= 9S v A if = A(y),
add a disjoint copy q0 of q and the role atoms S(y; z1); S(y0; z1), where y0 is
the copy of y in q0 and z1 is a fresh variable name;
5. if there is a S(y^; y) 2 q with y^ the predecessor of y, then add a disjoint copy
q0 of q and the role atom S(y^0; y) where y^0 is the copy of y^ in q0.
Note that Step 2 is the inductive step, where every subtree rooted at a successor
z of y is replaced with all ELIQs from Fq(z). The construction is illustrated
in Figure 1 which on the left side shows a variable y in q with predecessor y^,
two successors z1 and z in q, and one additional successor yR2 (a trace) in the
universal model Uq;O. On the right side, it displays the ELIQ qR(y;z)(y) 2 Fq(y),
assuming that Fq(z) = fq 1 ; : : : ; q n g. We remark that for y 6= x, the set Fq(y) is
not necessarily a frontier of the ELIQ qy(y) because the part of q that is outside
of subtree qy is taken into account in the construction of Fq(y), in Steps 3-5. Our
construction generalizes the construction of frontiers of ELIQs without ontologies
given in [
We next observe that the obtained frontier Fq(x) is of polynomial size. It is
then clear that it can be computed in polynomial time as described above since
subsumption between basic concepts in DL-Lite can be decided in polynomial
time [
jvar(q )j jsig(q)j jvar(q)j3 (jvar(q)j + 1) (jjOjj + 1):
We next observe that adding conjunction to DL-Lite destroys polynomial
frontiers and thus Theorem 1 does not extend to DL-Litehorn ontologies [
Theorem 2. There are families of AQ^s q1; q2; : : : and conjunctive ontologies O1; O2; : : : such that for all n 1, any frontier of qn w.r.t. On has size at least 2n.
The proof is a variation of a proof given in [
A1(x) ^ A01(x) ^
^ An(x) ^ A0n(x) On = fAi u A0i v A1 u A01 u u An u A0n j 1 i ng: In fact, the minimal frontier contains all AQ^s that contain exactly one of the conjuncts Ai and A0i, for 1 i n. Observe that in the proof of Theorem 1, there are only polynomially many choices for weakening an ELIQ, represented by the sets y, y 2 var(q). In contrast, weakening the AQ^ qn w.r.t. ontology On in a minimal way requires to choose for each i 2 f1; : : : ; ng whether Ai or A0i should be removed, and there are exponentially many such choices.
To close this section, we brie y consider the unique characterization of ELIQs in terms of polynomially many data examples. A data example takes the form (A; a) where A is an ABox and a 2 ind(A). Let E+, E be nite sets of data examples. An ELIQ q ts (E+; E ) w.r.t. a DL-Lite ontology O if (A; a) 2 E+ implies A; O j= q(a) and (A; a) 2 E implies A; O 6j= q(a). We say that (E+; E ) uniquely characterizes q w.r.t. O if q ts (E+; E ) and every ELIQ q0 that also ts (E+; E ) satis es q O q0. The following is a consequence of Theorem 1. Theorem 3. For every DL-Lite ontology O and every ELIQ q that is satis able w.r.t. O, we can compute in polynomial time data examples (E+; E ) that uniquely characterize q w.r.t. O.
Note that unique characterizability is closely related to the reverse engineering
of CQs, also called query-by-example and studied in a DL context in [
We use the results from the previous section to show that ELIQs are polynomial time learnable using only membership queries under DL-Lite ontologies if the learner is provided with an initial CQ qH0 such that qH0 is satis able w.r.t. the ontology O and qH0 O qT where qT is the target ELIQ. Such a q can be constructed in polynomial time if O is formulated in DL-Lite . Otherwise, it can be produced by a single initial equivalence query with an ELIQ that is not satis able w.r.t. O, forcing the learner to provide a positive counterexample (A; a) from which we can extract the desired q0 . Before proving these positive results, H however, we rst observe that polynomial time learning using only membership queries (but no initial equivalence query) is not possible when O contains concept disjointness constraints.
A disjointness ontology is a DL-Lite ontology that only consists of concept disjointness constraints.
Theorem 4. AQ^s are not polynomial query learnable under disjointness ontologies using only membership queries.
The proof of Theorem 4 is a variation of that of Theorem 2. We next present the main results of this section.
1. ELIQs are polynomial time learnable under DL-Lite ontologies using only membership queries and a single initial equivalence query. 2. ELIQs are polynomial time learnable under DL-Lite ontologies using only membership queries.
Throughout this section, we may assume the ontology to be in normal form. Lemma 5. If ELIQs are polynomial time learnable under DL-Lite ontologies in normal form using membership queries and a single initial equivalence query, then this is also true for unrestricted DL-Lite ontologies. The same holds for DL-Lite ontologies without the initial equivalence query.
The idea to prove Lemma 5 is to convert the given ontology into normal form and then run the learning algorithm for ontologies in normal form. Since that algorithm may pose membership queries and equivalence queries that involve fresh concept names introduced during normalization, we need to replace those concept names as described after Lemma 2 before forwarding the query to the oracle (which uses the original non-normalized ontology).
We prove Points 1 and 2 of Theorem 5 simultaneously. Let O be a DL-Lite ontology and a nite signature that contains all symbols in O, both known to the learner and the oracle. Further let qT (y) be the target ELIQ known to the oracle, formulated in signature and satis able w.r.t. O. The algorithm that enables the learner to learn qT in polynomial time is displayed as Algorithm 1. It takes as input a CQ qH0 that is satis able w.r.t. O and satis es qH0 O qT . Note that qH0 need not be an ELIQ. The algorithm then constructs and repeatedly updates a hypothesis ELIQ qH while maintaining that qH O qT . The initial call to subroutine treeify yields an ELIQ qH with qH0 O qH O qT to be used as the rst hypothesis. The algorithm then iteratively generalizes qH by constructing the frontier FqH of qH w.r.t. O in polynomial time and choosing from it a new ELIQ qH with qH O qT . Additionally, the algorithm applies the minimize subroutine Algorithm 1 Algorithm for learning ELIQs under DL-Lite ontologies Input A DL-Lite ontology O and a CQ qH0 satis able w.r.t. O such that qH0 Output An ELIQ qH such that qH O qT O qT qH := treeify(qH0) while there is a qF 2 FqH with qF
qH := minimize(qF ) end while return qH
O qT do to ensure that the new qH is O-minimal and to avoid an excessive blowup while iterating in the while loop.
Before we detail the subroutines treeify and minimize, we explain how to obtain the argument qH0 to the algorithm. Suppose rst that O contains neither concept disjointness constraints nor role disjointness constraints. Then qH0 (x) = fA(x) j A 2 \ NCg [ fr(x; x) j r 2 \ NRg: (1) If O contains concept or role disjointness constraints, then we cannot use the above qH0 because it is not satis able w.r.t. O. If, however, O contains only role disjointness constraints, then we can still nd a suitable q0 . Let R be the set H of all r 2 \ NR such that 9r is satis able w.r.t. O, introduce four variables xr0; xr1; xr0 ; xr1 for all r 2 R, and x a linear order on R0 = R [ fr j r 2 Rg. Fix any variable x := xiR. Then, qH0 is given by qH0 (x) = fA(xiR) j A 2
\ NC; R 2 R0; i 2 f0; 1gg [ fR(xiS; xiR) j R; S 2 R0; S
R; i 2 f0; 1gg [ fR(xiS; x1R i) j R; S 2 R0; S 6 R; i 2 f0; 1gg: Observe that every variable has an R-successor for every (satis able) role R. Therefore, there is a homomorphism from every satis able target ELIQ qT to qH0 , which shows that indeed qH0 O qT .
In the remaining case when O contains a concept disjointness constraint A u B v ?, we pose the ELIQ A(x) ^ B(x) as an equivalence query to the oracle. Since the target query is satis able w.r.t. O, the oracle returns a positive counterexample (A; a). The desired query qH0 is (A; a) viewed as a CQ with answer variable a. In the algorithm, we may w.l.o.g. assume that qH0 is O-saturated due to Lemma 1.
The minimize subroutine. The subroutine takes as input a unary CQ q(x) that is O-saturated, satis able w.r.t. O, and satis es q O qT . It computes an O-minimal unary CQ q0 with q O q0 O qT using membership queries. This is done by exhaustively applying the following operation: Remove successor. Choose a role atom r(x1; x2) 2 q and let q be the restriction of q n fr(x1; x2)g to the atoms that only contain variables which are reachable from x in Gqnfr(x1;x2)g. Pose the membership query Aq ; O j= qT (x). If the response is positive, continue with q in place of q.
This operation preserves O-saturation and satis ability w.r.t. O. Since the operation is applied at most once to each atom in q, the running time and number of membership queries is polynomial in jvar(q)j + j j. The following lemma summarizes important properties of q0 = minimize(q) that we need to show correctness and polynomial running time of Algorithm 1.
Lemma 6. Let q be a unary CQ that is O-saturated and satis able w.r.t. O such that q qT for the target query qT (y), and let q0 = minimize(q). Then 1. q O q0 and q0 O qT ; 2. var(q0) img(h) for every homomorphism h from qT to Uq0;O with h(y) = x (and consequently jvar(q0)j jvar(qT )j); 3. q0 is O-minimal.
When q is an ELIQ, minimize(q) is also an ELIQ. We de ne minimize on unrestricted CQs since it is applied to non-ELIQs as part of the treeify subroutine, described next.
The treeify subroutine. The subroutine takes as input a unary CQ q(x) that
is O-saturated, satis able w.r.t. O, and satis es q O qT . It computes an ELIQ
q0 = treeify(q) with q O q0 O qT by repeatedly increasing the length of
cycles in q and posing membership queries; similar constructions are used in
in [
Double cycle. Choose a cycle R1(x1; x2); : : : ; Rn(xn; x1) in pi and let p0i be the CQ obtained as follows: start with pi, introduce copies x01; : : : ; x0n of x1; : : : ; xn, and { remove all atoms R(xn; x1); { add A(x0j) if A(xj) 2 pi with 1 j n; { add R(x0j; z) if R(xj; z) 2 pi with 1 j n and z 2= fx1; : : : ; xng; { add R(x0j; x0k) if R(xj; xk) 2 pi with 1 j; k n and fj; kg 6= f1; ng; { add R(xn; x01) and R(x0n; x1) if R(xn; x1) 2 pi.
Once pi contains no more cycles, treeify stops and returns pi. The next lemma states the central properties of this construction.
1,
2. pi O qT ; 3. pi O pi+1 and jvar(pi+1)j > jvar(pi)j.
Point 3 of Lemma 7 and the `consequently' part of Point 2 of Lemma 6 imply that treeify terminates and thus eliminates all cycles in q while maintaining q O qT . The next lemma makes this precise.
Lemma 8. Let q be a CQ that is O-saturated, satis able w.r.t. O, and satis es q O qT . Then q0 = treeify(q) is an ELIQ that can be computed in time polynomial in jvar(qT )j + jjqjj using membership queries.
Returning to Algorithm 1, let q1; q2; : : : be the sequence of ELIQs that are assigned to qH during a run of the learning algorithm. Using the properties of frontiers, minimize, and treeify we can now show that the hypotheses approximate the target query in an increasingly closer way.
1, 1. qi O qT ; 2. qi O qi+1 and qi+1 6 O qi; 3. var(qi) img(h) for every homomorphism h from qi+1 to Uqi;O with h(x) = x.
Point 3 of Lemma 9 implies that jvar(qi+1)j jvar(qi)j, and this can be used to show that the while loop in Algorithm 1 terminates after a polynomial number of iterations, arriving at a hypothesis qH O qT such that there is no qF 2 FqH with qF O qT , that is, qH O qT .
qT for some n
p(jvar(qT )j + j j), p a polynomial.
It follows from Lemma 10, the `consequently' part of Point 2 of Lemma 6, and Lemma 8 that Algorithm 1 is a polynomial time learning algorithm, thus completing the proof of Theorem 5. 5
As future work, we are going to consider extensions of the setup studied in this
paper. We are optimistic that the approach presented here can be extended
to DL-Lite ontologies with role inclusions, yielding polynomial size frontiers
and polynomial query learnability also for that logic (but not polynomial time
learnability since subsumption becomes NP-complete). Natural next steps could
then be to replace DL-Lite with linear tuple-generating dependencies (TGDs) [
Acknowledgement. Carsten Lutz was supported by DFG CRC 1320 EASE. 23. Lehmann, J., Volker, J.: Perspectives on Ontology Learning, Studies on the Semantic
Web, vol. 18. IOS Press (2014) 24. Ortiz, M.: Ontology-mediated queries from examples: a glimpse at the DL-Lite case.
In: Proc. of GCAI. pp. 1{14 (2019) 25. Ozaki, A.: Learning description logic ontologies: Five approaches. where do they stand? KI - Kunstliche Intelligenz (2020) 26. Ozaki, A., Persia, C., Mazzullo, A.: Learning query inseparable ELH ontologies. In:
Proc. of AAAI. pp. 2959{2966 (2020) 27. Sarker, M.K., Hitzler, P.: E cient concept induction for description logics. In: Proc.
of AAAI. pp. 3036{3043 (2019) 28. Zarrie , B., Turhan, A.: Most speci c generalizations w.r.t. general EL-TBoxes. In: Proc. of IJCAI. pp. 1191{1197 (2013)