Learning Description Logic Concepts: When can Positive and Negative Examples be Separated?

1 Introduction

An important challenge for adopting ontologies in practical applications is the knowledge acquisition bottleneck, that is, the significant time and effort it takes to build the required ontologies. As a promising approach to help overcoming this difficulty, the varied field of ontology learning has received a lot of attention in the last two decades, see [Lehmann and V¨olker, 2014] for a recent overview. A prominent line of research within ontology learning is concept learning, also called concept induction, where the aim is to learn a structured class description (a concept) formulated in a relevant ontology language from positive and negative examples, given an already available ontology that contains background knowledge [Lehmann et al., 2014]. Applications of concept learning include the support of ontology development and the construction of concept based classifiers [B¨uhmann et al., 2016; Sarker et al., 2017].

Since description logics (DLs) form the basis for the OWL family of ontology languages, DL concept learning has received particularly much attention [Lehmann and Hitzler, 2010; Lisi, 2012; Tran et al., 2014; Fanizzi et al., 2018]. The precise formulation is as follows. Given a knowledge base (KB) K = (T ,A) where T is a TBox that is formulated in a DL LT and serves as an ontology providing background knowledge and A is an ABox in which individuals from designated sets P and N serve as positive and negative examples, respectively, find a concept C formulated in a DL LS that separates the positive from the negative examples, that is, K |= C(a) for all a ∈ P and K ̸|= C(a) for all a ∈ N. In addition to separation, one also wants to achieve that the learned concept C generalizes the positive examples in a meaningful way, classifying new examples accordingly.

As a prominent system for DL concept learning, we mention DL LEARNER. It encompasses several learning algorithms that support a range of DLs, including expressive ones such as ALC and ALCQ, Horn DLs such as EL, and even full OWL 2 [B¨uhmann et al., 2018; B¨uhmann et al., 2016]. Like competing systems such as DL-FOIL, YINYANG, and PFOIL-DL [Fanizzi et al., 2018; Iannone et al., 2007; Straccia and Mucci, 2015], DL LEARNER uses a carefully crafted refinement operator along with various heuristics to learn concepts that provide an as good as possible generalization of the given examples, avoiding overfitting. The study of such operators originated in [Badea and Nienhuys-Cheng, 2000], see also [Lehmann and Haase, 2009; Lehmann and Hitzler, 2010]. If possible, refinement operators are designed so that the resulting algorithm terminates on any input and is complete in the sense that whenever there is a concept that separates the positive and negative examples in the input, then such a concept is indeed learned.

The aim of this paper is to investigate the fundamental question of when a separating concept exists for a learning instance (K, P, N), considering the most popular choices of DLs for the TBox language LT and the separation language LS. Our main contributions are model-theoretic characterizations that give important insight into when this is the case and a precise analysis of the computational complexity of separability viewed as a decision problem, which we refer to as (LT ,LS) concept separability and as L concept separability when LT = LS = L. We also consider concept definability, the special case of concept separability in which P ∪N comprises all individuals fromA. In fact, all our complexity results hold for both separability and definability.

We believe that these problems are relevant both from a practical and from a theoretical perspective. In fact, complexity lower bounds for concept separability point to an inherent complexity that no practical system that aims for completeness can avoid. Undecidability results even mean that there can be no practical learning system that is both terminating and complete. From the viewpoint of machine learning theory, a separating concept corresponds to a consistent hypothesis and understanding the existence of such a hypothesis is considered the most fundamental problem for exploring the version space which in our setup is the space of all separating concepts [Hirsh et al., 2004]. The associated decision problem is often called the consistency problem, and it is known to be closely related to PAC learnability [Pitt and Valiant, 1988; Kietz, 1993].

We cover the expressive DLs ALC, ALCI, ALCQ, and ALCQI as well as the Horn DLs EL and ELI. For the former, overfitting is a risk because the disjunction operator available in such DLs enables the construction of separating concepts that do not provide the desired generalization of the positive examples. Nevertheless, most practical systems such as DL LEARNER work with expressive DLs and avoid overfitting by using appropriate refinement operators. Horn DLs do not admit disjunction and therefore are not prone to overfitting. On the other hand, they provide less separating power and, as we show, tend to incur higher computational (worstcase) cost for learning.

For expressive DLs, we start with initial characterizations in terms of (some form of) bisimulations and then improve them to more refined characterizations based on homomorphisms. Interestingly and unexpectedly to us, these establish a tight link between concept separability and the evaluation of ontology-mediated queries (OMQs) based on unions of rooted conjunctive queries [Calvanese et al., 2013; Bienvenu et al., 2014]. Here, 'rooted' means that queries have at least one answer variable and are connected. We use the OMQ connection to obtain complexity upper and lower bounds. In fact, L concept separability is NEXPTIMEcomplete for L ∈ {ALC,ALCI,ALCQ} while ALCQI concept separability is only EXPTIME-complete. This refers to combined complexity where all components of the learning instance are part of the input. We also study data complexity where the ABox is the only input while the TBox is fixed and thus of constant size. In all expressive DLs mentioned above, concept separability is Σp2 -complete in data complexity.

The connection to OMQ evaluation does not extend to Horn DLs, for which we use characterizations based on products of universal models and simulations. Based on these, we show that (LT , EL) concept separability is EXPTIMEcomplete for LT ∈ {EL, ELI}, both in combined complexity and in data complexity. Rather surpsiringly, we also prove that ELI concept separability is undecidable, thus ruling out terminating and complete learning systems. The proof is by a subtle reduction of a tiling problem. We finally consider (LT ,LS) concept separability where LT is any of the expressive DLs mentioned above and LS is EL or ELI. These problems also turn out to be undecidable.

A stronger version of concept separability that is also considered in the literature requires that K |= ¬C(a) for all a ∈ N, rather than only K ̸|= C(a). Clearly, this is a meaningful notion only for DLs with negation. We present some first results also for this version of concept separability, giving model-theoretic characterizations for expressive DLs based on bisimulations and proving that for L ∈ {ALC,ALCI}, L concept separability is EXPTIME-complete in combined complexity and CONP-complete in data complexity.

The long version with appendix is available at http://www. informatik.uni-bremen.de/tdki/research/papers.html.

2 Preliminaries

We introduce the basics of DLs as required for this paper, for full details see [Baader et al., 2017]. Let NC be a set of concept names and NR a set of role names, both countably infinite. A role is either a role name or an inverse role r-, r a role name. For uniformity, we identify (r-)- with r. An ALCQI concept is formed according to the syntax rule

where A ranges over concept names, r over roles, and n over N. We use ∃r.C as an abbreviation for (⩾ 1 r C), C ⊔ D for ¬(¬C ⊓ ¬D), ∀r.C for ¬∃r.¬C, and (⩽ n r C) for ¬(⩾ n + 1 r C).

There are several fragments of ALCQI that are relevant for this paper. An EL concept admits as constructors only the top concept '⊤', conjunction '⊓', and existential restriction '∃r.C' with r a role name (but not an inverse role). ALC concepts additionally admit negation '¬'. Further constructors are indicated by concatenation of a corresponding letter where Q stands for at least restrictions '(⩾ n r C)' and I for inverse roles. This explains the name ALCQI and allows us to refer to fragments such as ELI and ALCI. We refer to ALC and extensions thereof as expressive DLs and to EL and ELI as Horn DLs.

For any of the DLs L introduced above, an L TBox is a finite set of concept inclusions (CIs) C ⊑ D, where C and D are L concepts. Let NI be a countably infinite set of individual names. An ABox A is a finite set of concept assertions A(a) and role assertions r(a, b) where A ∈ NC, r ∈ NR, and a, b ∈ NI. We use ind(A) to denote the set of all individual names that occur in A. An ABox is associated with a directed graph GA = (ind(A), {(a, b) | r(a, b) ∈ A}). We use graph theoretic terminology when speaking about ABoxes, implicitly referring to the graph GA, speaking for example about a being reachable from b for a, b ∈ ind(A). In technical constructions, we will sometimes use extended ABoxes in which concept assertions take the more general form C(a), C a concept of the DL under consideration. An L knowledge base (KB) (T , A) consists of an L TBox T and an ABox A, and extended KBs admit extended ABoxes. We use sub(K) to denote the set of subconcepts of concepts that occur in K.

As usual, the semantics of DLs is defined in terms of interpretations I = (∆I , ·I ), where ∆I is a non-empty set and ·I maps each concept name A ∈ NC to a subset AI of ∆I and each role name r ∈ NR to a binary relation rI on ∆I . We refer to [Baader et al., 2017] for details on how to extend ·I to compound concepts. An interpretation I satisfies a CI C ⊑ D if C I ⊆ DI and is a model of a TBox T if it satisfies all inclusions in T . An interpretation is a model of an ABox A if it satisfies all assertions in A, that is, a ∈ AI if A(a) ∈ A and (a, b) ∈ rI if r(a, b) ∈ A. We thus make the standard names assumption. An interpretation is a model of a KB K if it is a common model of its TBox and ABox and K is satisfiable if it has a model. The assertion C(a) is a consequence of the KB K, in symbols K |= C(a), if a ∈ C I for all models I if K.

We next recall model-theoretic characterizations of when elements in interpretations are indistinguishable by concepts formulated in one of the DLs L introduced above. A pointed interpretation is a pair I, d with I an interpretation and d ∈ ∆I . For pointed interpretations I, d and J , e, we write I, d ≡L J , e and say that I, d and J , e are L-equivalent if d ∈ C I iff e ∈ C J for all L concepts C.

As for the model-theoretic characterizations, we start with ALC. A relation S ⊆ ∆I × ∆J is a bisimulation if conditions [Atom], [Forth] and [Back] from Figure 1 hold, where A ranges over all concept names, r over all role names, succIr (d) = {d′ ∈ ∆I | (d, d′ ) ∈ rI }, and 'dual' refers to swapping I, d, d′ and J , e, e′ . We write I, d ∼ALC J , e and call I, d and J , e bisimilar if there exists a bisimulation S such that (d, e) ∈ S. For ALCQ, we define ∼ALCQ by replacing bisimulations with counting bisimulations, defined as bisimulations, but with [Forth] and [Back] replaced by [QForth] and [QBack]. For ALCI and ALCQI, we define ∼ALCI and ∼ALCQI analogously, but now demanding that in all conditions in Figure 1, r additionally ranges over inverse roles.

For L ∈ {EL, ELI}, rather than characterizing ≡L we consider the non-symmetric relation I, d ≤L J , e which holds if d ∈ C I implies e ∈ C J for all L concepts C. A relation S ⊆ ∆I ×∆J is an EL simulation from I to J if it satisfies [AtomR] and [Forth] from Figure 1 where again A ranges over all concept names and r over all role names. ELI simulations are defined in the same way, but with r ranging also over inverse roles. We write I, d ⪯L J , e if there exists an L simulation S from I to J with (d, e) ∈ S.

The next lemma summarizes the model-theoretic characterizations for all relevant DLs [Lutz et al., 2011; Goranko and Otto, 2007]. An interpretation I has finite outdegree if the directed graph GI = (∆I , ⋃r∈NR rI ) has.

Lemma 1 Let I, d and J , e be pointed interpretations and let J have finite outdegree. Then

1. for L ∈ {ALC,ALCI,ALCQ,ALCQI}, I, d ≡L J , e iff I, d ∼L J , e;
2. for L ∈ {EL, ELI}, I, d ≤L J , e iff I, d ⪯L J , e.

The 'if' directions also hold if J is of infinite outdegree.

3 Separability and Definability

We introduce concept separability and concept definability, the main notions studied in this paper. We also provide illustrating examples and give initial model-theoretic characterizations in all relevant DLs.

Definition 1 Let LT , LS be DLs. An LT learning instance is a triple (K, P,N) with K = (T ,A) an LT KB and P,N ⊆ ind(A) non-empty sets of positive and negative examples. An LS solution to (K, P, N) is an LS concept C such that

1. K |= C(a) for all a ∈ P and
2. K ̸|= C(a) for all a ∈ N.

Any TBox language LT and separation language LS give rise to a decision problem of concept separability.

We speak of L concept separability when LT = LS = L. We also study (LT , LS) concept definability, the special case of (LT , LS) concept separability in which P covers all positive examples in the KB, that is, inputs are learning instances (K, P, N) such that N = ind(A) \ P . We now give illustrating examples. When we claim that there is no solution, this is a direct consequence of the characterizations provided later. In the following examples and also later in this paper, we assume that K = (T , A) unless explicitly stated otherwise.

Example 1 (1) Let (K, P,N) be defined by T = ∅,

P = {a1, a2}, and N = {a3}. Then ∃authorOf.(IJCAIpub⊔ AIJpub) is an ALC solution, but there is neither an EL solution nor an ELI solution.

(2) Let (K, P,N) be as in (1), but with T replaced by the EL TBox

Then AIResearcher is an EL solution.

P = {a}, and N = {b}. Due to the standard names assumption, c1 and c2 are distinct objects and thus (⩾ 2 authorOf ⊤) is an ALCQ solution. However, there is no ALCI solution, even when T is replaced with any ALCI TBox.

(4) Let (K, P, N) be as in (3), but with P and N swapped. There is no ALCQI solution even when T is replaced with any ALCQI TBox. Note that (⩽ 1 authorOf ⊤) is not a solution as the semantics does not rule out additional authorOf successors in concrete models.

Observe that if LS is closed under conjunction, then (LT , LS) concept separability can be reduced in polynomial time to the special case of (LT ,LS) concept separability that admits only input instances (K, P,N) in which N is a singleton. Indeed, if C is a solution to a learning instance (K, P,N), then it is a solution to (K, P, {a}) for all a ∈ N. If, conversely, Ca is a solution to (K, P, {a}) for all a ∈ N, then da∈N Ca is a solution to (K, P,N). In what follows, we will thus mostly restrict our attention to this special case.

We study both the combined complexity of concept separability and definability and the data complexity, where only the ABox of the KB is regarded as the input to the decision problem while the TBox is fixed and thus of constant size. Note that the sizes of P and N are dominated by the size of the ABox. When not making explicit which complexity measure we speak about, we mean combined complexity.

We now give the announced characterizations of (LS, LT ) concept separability, starting with the case that LS is an expressive DL. The characterizations use the relations ∼L from Lemma 1, L being the separation language. The corresponding relation for the TBox language is not used.

Theorem 1 Let (K, P, {b}) be an ALCQI learning instance. For LS ∈ {ALC,ALCI,ALCQ,ALCQI}, the following are equivalent:

1. (K, P, {b}) has an LS solution;
2. there exists a model I of K of finite outdegree such that for all a ∈ P and all models J of K, J , a ̸∼LS I, b.

The proof of Theorem 1 is rather standard, based on Lemma 1 and compactness.

We now turn to the case where LS is a Horn DL. The main difference to Theorem 1 is that a product construction is involved. Interestingly, our characterization is rather flexible regarding LT , which can even be ALCQI. Let Ii, di, i ∈ I, be a family of pointed interpretations. The (direct) product ∏i∈I Ii, d is the pointed interpretation defined by

and d(i) = di, for all i ∈ I. We say that a set Mof models of a KB K is L complete if for every L concept C and every a ∈ ind(K), K |= C(a) iff a ∈ C I for all I ∈ M. If, for example, K is an ALCQI KB, then the class of all 'forest models' of K of finite outdegree is well-known to be ALCQI complete.

Theorem 2 Let (K, P, {b}) be an ALCQI learning instance. For LS ∈ {EL, ELI} and M a set of models of K that is LS complete, the following are equivalent:

1. (K, P, {b}) has an LS solution;
2. there exists a model I of K of finite outdegree such that ∏a∈P (∏J∈M(J , a)) ̸⪯LS I, b.

The proof uses Lemma 1 and the fact that for any ELI concept C and family of pointed interpretations (Ii, di)i∈I, d ∈ C∏i∈I Ii if and only if di ∈ C Ii for all i ∈ I.

4 Characterizations for Expressive DLs

We establish characterizations of concept separability that are more refined than the initial one presented in Theorem 1. The refined characterizations establish a suprising connection between concept separability and (U)CQ-evaluation on KBs. They also provide the foundation for decision procedures for concept separability that we develop later on. We start with ALCI and then proceed via ALCQI to ALC and ALCQ, for which the characterizations are slightly more technical.

A homomorphism h from an ABox A to an interpretation I is a mapping h from ind(A) to ∆I such that A(d) ∈ A implies h(d) ∈ AI and r(c, d) ∈ A implies (h(c), h(d)) ∈ rI . We write A, a → I, b if there exists a homomorphism h from A to I with h(a) = b.

Theorem 3 Let (K, P, {b}) be an ALCI learning instance. Then the following conditions are equivalent:

1. (K, P, {b}) has an ALCI solution;
2. there exists a model I of K such that for all a ∈ P, A, a ̸→ I, b.

Theorem 3 is proved by showing the equivalence of Condition 2 in Theorems 1 and 3. One first observes that it suffices to consider models I that contain no distinct d, e with I, d ∼ALCI I, e. Then the direction from Theorem 3 to Theorem 1 follows as the restriction of a bisimulation between J and I to the ABox individuals in A is a homomorphism to I. For the converse direction, one carefully constructs the required model J of K from I using the given homomorphism.

To adapt Theorem 3 from ALCI to ALCQI, we use homomorphisms h from A to I that are locally injective for all roles r, that is, the restriction of h to the set succAr (a) = {b | r(a, b) ∈ A} is injective for all a ∈ ind(A). Now A, a →i I, b is defined like A, a → I, b, but based on homomorphisms that are locally injective for all roles r.

Theorem 4 Let (K, P, {b}) be an ALCQI learning instance. Then the following conditions are equivalent:

1. (K, P, {b}) has an ALCQI solution;
2. there exists a model I of K such that for all a ∈ P, A, a ̸→i I, b.

Now for the adaptation of Theorems 3 and 4 to DLs without inverse roles. Let K = (T ,A) be an ALCQI KB and a ∈ ind(A). We use A↓a to denote the set of assertions in A that use only individual names from the set reachA(a) of individual names reachable from a in GA. Now A, a →r I, b means that there is a homomorphism h from A↓a to I with h(a) = b such that the extended KB KI,h, defined as

is satisfiable. We define A, a →ir I, b analogously, additionally requiring that h is locally injective for all role names r (but not necessarily for inverse roles).

Theorem 5 Let (K, P, {b}) be an ALC (resp. ALCQ) learning instance. Then the following conditions are equivalent:

1. (K, P, {b}) has an ALC (resp. ALCQ) solution;
2. there exists a model I of K such that for all a ∈ P, A, a ̸→r I, b (resp. A, a ̸→ir I, b).

The following example illustrates the reason for why the characterization in Theorem 5 requires KI,h to be satisfiable.

Example 2 Consider A = {r(c, a), A(a), A(b)}, P = {a}, N = {b}, T = {⊤ ⊑ ∀r.B}, and let K = (T ,A). Then K |= B(a) and K ̸|= B(b) and so B is an ALC solution for (K, P,N). Observe that h : a ↦→ b is a homomorphism from A↓a to any model I of K, but for any model I of K with b ∈ (¬B)I the extended KB KI,h is not satisfiable.

We observe a slightly surprising consequence of the above characterizations. Concept separability is TBox antimonotone in a DL L if extending the TBox cannot result in a solution for a learning instance to become available, that is, for all L learning instances (K1, P,N) and (K2, P,N) with T1 ⊆ T2 and A1 = A2, (K1, P,N) has an L solution if (K2, P, N) has an L solution.

Theorem 6 Concept separability is TBox anti-monotone in ALCI and ALCQI, but not in EL, ELI, ALC, and ALCQ.

Note that TBox anti-monotonicity in ALCI and ALCQI follows directly from Theorems 3 and 4. To show that concept separability is not TBox anti-monotone in ALC and ALCQ consider (K, P,N) from Example 2 and let K′ = (∅,A). Then (K′ , P,N) has no ALCQ solution (and thus no ALC solution), but (K, P, N) has an ALC solution. Example 1 (1) and (2) above shows that concept separability is not TBox anti-monotone in EL and ELI.

5 Complexity: Expressive DLs

We clarify the complexity of concept separability and concept definability in expressive DLs, which turn out to be NEXPTIME-complete in ALC, ALCI, and ALCQ, and EXPTIME-complete in ALCQI. In data complexity, they are Σp2 -complete in all four DLs. In both lower and upper bound proofs, we exploit a connection between separability and (appropriate versions of) UCQ evaluation on KBs that is suggested by the characterizations in the previous section.

Theorem 7 ALCI concept separability and ALCI concept definability are NEXPTIME-complete.

The upper bound in Theorem 7 is proved by a polynomial time reduction to the complement of rooted UCQ evaluation on ALCI KBs and the lower bound is proved by a polynomial time reduction from the complement of rooted CQ evaluation on ALCI KBs. Both problems are CONEXPTIMEcomplete [Lutz, 2008] and rather well known, so we refrain from giving definitions and only mention that a CQ is rooted if it is connected and has at least one answer variable, and that a UCQ is rooted if every CQ in it is.

For the first reduction, let (K, P, {b}) be an ALCI learning instance with K = (T ,A). For every a ∈ P, let qa be the maximal connected component Aa of A that contains a, viewed as a connected CQ with only answer variable a. Further, let q be the UCQ ∨a∈P qa. Then (K, P, {b}) has a solution iff K ̸|= q(b). In fact, K ̸|= q(b) iff there is a model I of K such that I ̸|= qa(b) for all a ∈ P, that is, Aa, a ̸→ I, b. This is equivalent to A, a ̸→ I, b as required by Point 2 of Theorem 3 since for all other connected components A′ of A, the identity is a homomorpshism to I.

For the second reduction, let K = (T , A) be an ALCI KB, q(x) a unary rooted CQ, and a ∈ ind(A). Let Aq be q viewed as an ABox where now x is an individual name, and let A′ be the disjoint union of A and Aq. Let further K′ = (T ,A′ ), P = {x}, and N = {a}. Using similar arguments as above, one can show that K ̸|= q(a) iff (K′ , P,N) has a solution. Note that this establishes hardness already for learning instances with a single positive example (and a single negative example). The reduction can be modified to show hardness of definability. In fact, the lower bound proof in [Lutz, 2008] applies already if we restrict ABoxes to be of the simple form {A0(a0)} and can easily be modified so that the CQ q(x) used is such that only the individual x can be an answer to q in Aq (by introducing a fresh concept name X, adding the atomX(x) to q and the assertion X(a0) to the ABox). Then we can set P = {x} as before and N is the set of all other individuals in A′ .

In the case of ALCQI, separability closely corresponds to a version of unary rooted (U)CQ evaluation that is based on locally injective homomorphisms from the CQ to models of the KB. We introduce this problem in the appendix and prove that, remarkably, it is only EXPTIME-complete. The intuitive reason is that the CONEXPTIME-lower bound for CQ evaluation on ALCI KBs requires to 'fold' the CQ in exponentially many different ways, which can only be done with locally non-injective homomorphisms. In ALCQI, concept separability is thus no harder than standard reasoning problems such as concept satisfiability w.r.t. a TBox-these are EXPTIME-complete for all expressive DLs considered in this paper [Baader et al., 2017].

Theorem 8 ALCQI concept separability and ALCQI concept definability are EXPTIME-complete.

For the case without inverse roles, we also introduce corresponding versions of (U)CQ evaluation, based on the kinds of homomorphism used in Theorem 5. These turn out to be CONEXPTIME-complete. The lower bound is proved by a reduction of a suitable version of the tiling problem and crucially exploits the satisfiability condition used in the homomorphisms in Theorem 5. We work with a single positive example in the case of ALC while in ALCQ the number of positive examples is not bounded by a constant.

Theorem 9 For L ∈ {ALC,ALCQ}, L concept separability and L concept definability are NEXPTIME-complete.

We close this section with clarifying data complexity.

Theorem 10 For L ∈ {ALC,ALCQ,ALCI,ALCQI}, L concept separability and L concept definability are Σp2 - complete in data complexity.

The upper bounds are proved by a 'guess-coguess and check' style procedure. The lower bounds are proved by reduction of the problem to decide whether for a given undirected graph G and k ≥ 1, there is a 2-coloring of G that does not generate a monochromatic k-clique [Rutenburg, 1986]. The proof requires two positive examples.

6 Complexity: Horn DLs

We study concept separability and concept definability in the case that the separation language is one of the Horn DLs EL and ELI. As the TBox language, we consider both Horn DLs and expressive DLs. It turns out that these problems tend to be undecidable, notable exceptions being the cases that the TBox language is EL or ELI and the separation language is EL.

We first refine the characterization from Theorem 2. For L ∈ {EL, ELI}, a model U of a knowledge base K is L universal if K |= C(a) iff U |= C(a), for all L concepts C and a ∈ ind(A).

Theorem 11 Let (K, P, {b}) be an ELI learning instance, LS ∈ {EL, ELI}, and U an LS universal model for K of finite outdegree. Then the following are equivalent:

1. (K, P, {b}) has an LS solution,

2. Πa∈P (U, a) ̸⪯LS U, b.

The absence of disjunction in Horn DLs forces the product in Point 2, which captures the commonalities of the positive examples and achieves true generalization, avoiding overfitting. It is, however, also responsible for the high complexity and even undecidability of concept separability in Horn DLs. This is in fact rather surprising given that standard reasoning problems such as subsumption are only PTIME-complete in EL and EXPTIME-complete in ELI.

We start with the separation language EL, considering both EL and ELI as the TBox language.

Theorem 12 Let LT ∈ {EL, ELI}. Then (LT , EL) concept separability and definability are EXPTIME-complete, both in combined complexity and in data complexity.

For the lower bound, we adapt a proof used in [Harel et al., 2002] to prove that the simulation problem between I, d and J , e is EXPTIME-hard when I is a synchronized product of given interpretations and J is an explicitly given interpretation. Remarkably, the lower bound holds already for empty TBoxes. The number of positive examples is not bounded by a constant. For the upper bound, we build on Point 2 of Theorem 11, constructing the product of (exponential size) EL universal models of ELI knowledge bases and then deciding EL similarity in polynomial time. The upper bound easily extends to the case where the learned concept can use only symbols from a given signature.

Surprisingly, separability and definability even become undecidable when we extend EL with inverse roles. This implies that no learning algorithm can be complete and terminating.

Theorem 13 ELI concept separability and definability are undecidable.

The proof is by a rather subtle reduction of the tiling problem of rectangles of unbounded size, borrowing and extending some ideas from the proof given in [Botoeva et al., 2019] that the CQ entailment problem between ALC KBs is undecidable. It requires only two positive examples.

We remark that ELI concept separability is closely related to the problem of learning conjunctive queries in the context of ELI KBs ('query by example'). That problem was stated to be 2EXPTIME-complete in [Guti´errez-Basulto et al., 2018], but the proof of the upper bound turns out to be incorrect. In the appendix, we use a minor variation of our proof of Theorem 13 to show that the problem is actually undecidable.

Another related problem is the existence of most specific concepts (MSCs) and least common subsumers (LCSs) [Baader, 2003; Lutz et al., 2010; Zarrieß and Turhan,

2013]. In fact, if (K, P, {b}) is a learning instance, MSCs Ma exist of all a ∈ P, and a LCS C of the Ma exists, then (K, P, {b}) has a solution if K ̸|= C(b). We conjecture that a variation of the proof of Theorem 13 can be used to show that in ELI, the existence of the LCS is undecidable in the presence of a TBox.

We now consider the case where the TBox is formulated in an expressive DL and the separation language is a Horn DL. For example, such a setup is natural if avoiding overfitting is a concern. Also here, separability turns out to be undecidable.

Theorem 14 Let LT ∈ {ALC,ALCQ,ALCI,ALCQI} and LS ∈ {EL, ELI}. Then (LT ,LS) concept separability and (LT , LS) concept definability are undecidable.

The proof is by reduction from the already mentioned CQ entailment problem between ALC KBs which undecidable already for (directed or undirected) tree-shaped CQs.

7 First Observations on Strong Separability

There is an alternative notion of concept learning that has been proposed in the literature [Lehmann et al., 2014; Badea and Nienhuys-Cheng, 2000; Fanizzi et al., 2018]. An L concept C is a strong L solution to a learning instance (K, P, N) if K |= C(a) for all a ∈ P and K |= ¬C(a) for all a ∈ N. We then define strong L concept separability in the expected way. While we leave a thorough investigation for future work, we observe the following characterization.

Theorem 15 For LS ∈ {ALC,ALCI,ALCQ,ALCQI}, an ALCQI learning instance (K, P, N) has a strong L solution iff for all models I and J of K, all a ∈ P and all b ∈ N, I, a ̸∼LS J , b.

Based on this result, one can show that for ALC and ALCI there is a tight link between strong concept separability and KB satisfiability (rather than to UCQ-evaluation on KBs) which can be used to prove the following.

Theorem 16 For L ∈ {ALC, ALCI}, strong L concept separability is EXPTIME-complete in combined complexity and CONP-complete in data complexity.

Note the drop in complexity compared to the non-strong version of concept separability, from NEXPTIME to EXPTIME and from Σp2 to CONP. For ALCQ and ALCQI, the complexity of strong L concept separability remains open.

8 Discussion

This paper provides characterizations and complexity results for concept separability in many important DLs. It would be interesting to further add other popular DL features such as role hierarchies, transitive roles, and nominals, and it might also be relevant to consider cases of (LT ,LS) concept separability in which LT is less expressive than LS. We also plan to investigate strong separability and in how the characterizations given in this paper can be used or extended to analyse the version space beyond emptiness and whether they can also be used to analyse or craft refinement operators.

Acknowledgements

Lutz was supported by DFG CRC 1320 Ease.