On the Power and Limitations of Examples for Description Logic Concepts

1 Introduction

Labeled examples (i.e., positive and negative examples) are an attractive medium for communicating complex concepts. They are useful as data for deriving concept expressions (such as in concept learning, interactive concept specification, and example-driven concept refinement) as well as for illustrating concept expressions to a user or domain expert [Lehmann, 2009; Funk et al., 2019; Funk et al., 2021; Ozaki, 2020; Fanizzi et al., 2008; Iannone et al., 2007; Lehmann and Hitzler, 2010]. Here, we study the utility of labelled examples for characterising description logic concepts, where examples are finite interpretations that can be either positively or negatively labelled.

Example 1.1. In the description logic EL, we may define the concept of an e-bike by means of the concept expression

Suppose we wish to illustrate C by a collection of positive and negative examples. What would be a good choice of examples? Take the interpretation I consisting of the following facts.

✟

✠

In the context of this interpretation I, it is clear that

• soltera2 is a positive example for C, and
• px10 and teslaY are negative examples for C

In fact, as it turns out, C is the only EL-concept (up to equivalence) that fits these three labeled examples. In other words, these three labeled examples "uniquely characterize" C within the class of all EL-concepts. This shows that the above three labeled examples are a good choice of examples. Adding any additional examples would be redundant. Note, however, that this depends on the choice of description logic. For instance, the richer concept language ALC allows for other concept expressions such as Bicycle ⊓¬∃Contains.Basket that also fit.

Motivated by the above example, we investigate the existence and efficient computability of finite characterisations, i.e., finite sets of labeled examples that uniquely characterize a single concept. Finite characterisations are relevant not only for illustrating a complex concept to a user (e.g., to verify the correctness of a concept expression obtained using machine learning techniques). Their existence is a necessary condition for exact learnability with membership queries [Angluin, 1987]. Furthermore, from a more fundamental point of view, by studying the existence of finite characterisations, we gain insight into the power and limitations of labeled examples as a medium for describing concepts.

Concretely, we systematically study the existence of, and the complexity of computing, finite characterisations for description logic concepts in a wide range of expressive description logics. We look at concept languages L(O) that are generated by a set of connectives O, where {∃, ⊓} ⊆ O ⊆ {∀, ∃,≥,-, ⊓, ⊔,⊤,⊥, ¬}. In other words, we look at fragments of the description logic ALCQI that contain at least the ∃ and ⊓ constructors from EL.

As our first result, within this framework, we obtain an almost complete classification of the concept languages that admit finite characterisations.

1. If O is a subset of {∃,-, ⊓, ⊔,⊤,⊥}, {∀, ∃, ⊔, ⊓} or {∀, ∃,≥, ⊓,⊤} then L(O) admits finite characterisations.
2. Otherwise L(O) does not admit finite characterisations, except possibly if {≥, -, ⊓} ⊆ O ⊆ {∃, ≥, -, ⊓, ⊤}.

The above theorem identifies three maximal fragments of ALCQI that admit finite characterisations. It leaves open the status of essentially only two concept languages, namely L(∃, ≥, -, ⊓) and L(∃, ≥, -, ⊓, ⊤) (note that ∃ is definable in terms of ≥). The proof builds on prior results from [Cate and Dalmau, 2022] and [Cate and Koudijs, 2024]. Our main novel technical contributions are a construction of finite characterisations for L(∀, ∃, ≥, ⊓, ⊤) and complementary negative results for L(≥, ⊥), L(≥, ⊔) and L(∀, ∃, -, ⊓). The construction of finite characterisations for L(∀, ∃, ≥, ⊓, ⊤) is non-elementary. We give an elementary (doubly exponential) construction for L(∃, ≥, ⊓, ⊤), via a novel polynomial-time algorithm for constructing frontiers.

Next, we study which concept languages L(O) admit polynomial-time computable characterisations, i.e., have a polynomial-time algorithm to compute finite characterisations.

1. If O is a subset of {∃,-, ⊓,⊤,⊥}, then L(O) admits polynomial-time computable characterisations.
2. Otherwise, L(O) does not admit polynomial-time computable characterisations, assuming P̸=NP.

The first item follows from known results [Cate and Dalmau, 2022]; we prove the second. Thm. 1.1 and 1.2 are summarized in Figure 1.

Finally, we investigate finite characterisations relative to an ontology O, where we require the examples to be interpretations that satisfy the ontology and we require that every fitting concept is equivalent to the input concept C relative to O.

Theorem1.3. Let {∃, ⊓} ⊆O⊆ {∀, ∃,≥,-, ⊓, ⊔,⊤,⊥, ¬}.

1. If O is a subset of {∃, ⊓,⊤,⊥}, then L(O) admits finite characterisations w.r.t. all DL-Lite ontologies.
2. Otherwise, L(O) does not admit finite characterisations w.r.t. all DL-Lite ontologies, except possibly if {∃, ⊓, ⊔} ⊆ O ⊆ {∃, ⊓, ⊔, ⊤, ⊥}.

In fact, for L(∃, ⊓, ⊤, ⊥)-concepts C and DL-Lite ontologies O such that C is satisfiable w.r.t. O, a finite characterisation can be computed in polynomial time.

This shows in particular that, if we exclude ⊔ from consideration, then L(∃, ⊓,⊤,⊥) is the unique largest fragment admitting finite characterisations under DL-Lite ontologies.

Outline In Section 2, we review relevant definitions and we introduce our framework for finite characterisations. Section 3 studies the existence and polynomial-time computability of finite characterisations without an ontology. Section 4 extends the analysis to the case with DL-Lite ontologies. Section 5 discusses further implications and future directions.

RelatedWork Finite characterisations were first studied in the computational learning theory literature under the name of teaching sets, with a corresponding notion of teaching dimension, measuring the maximal size of minimal teaching sets of some class of concepts [Goldman and Kearns, 1995]. The existence of finite characterisations is a necessary condition for exact learnability with membership queries.

Several recent works study finite characterisations for description logic concepts ([Cate and Dalmau, 2022; Funk et al., 2022] for ELI; [Fortin et al., 2022] for temporal instance queries). We use results from [Cate and Dalmau, 2022; Funk et al., 2022]. Thm. 1.3 appears to contradict a result in [Funk et al., 2022], which states that ELI admits finite characterisations under DL-Lite ontologies. However, this is due to a difference in the way we define examples, which we will discuss in detail in Section 2.

Finite characterisations have also been studied for a while in the data management community (cf. [Mannila and R¨aih¨a, 1985; Staworko and Wieczorek, 2015; Cate and Dalmau, 2022; Cate et al., 2024] for queries; [Alexe et al., 2011] for schema mappings), and, a systematic study of finite characterisations for syntactic fragments of modal logic was carried out in [Cate and Koudijs, 2024]. We make use of several results from [Cate and Koudijs, 2024], and one of our results also implies an answer to an open problem from this paper.

2 Basic Definitions and Framework

In the following, we first define the syntax and semantics of concept and ontology languages considered in this work.

Concept Languages Let NC andNR be infinite andmutually disjoint sets of concept and role names, respectively. We work with finite subsets ΣC ⊆ NC,ΣR ⊆ NR of these. We denote by L(∀, ∃, ≥, -, ⊓, ⊔, ⊤, ⊥, ¬)[ΣC, ΣR] the following concept language:

where k ≥ 1, A ∈ ΣC and S = R or S = R- for some R ∈ ΣR. Note that ∃S.C is equivalent to ≥ 1S.C.

For any set of operators O ⊆ {∀, ∃, ≥, -, ⊓, ⊔, ⊤, ⊥, ¬}, we denote by L(O)[ΣC,ΣR] the fragment of L(∀, ∃,≥ ,-, ⊓, ⊔,⊤,⊥, ¬) that only uses the constructs in O, concept names from ΣC and role names from ΣR. We may omit [ΣC,ΣR] from L(O)[ΣC,ΣR] and simply write L(O) if the role and concepts names are clear from context or irrelevant.

Observe that L(∀, ∃,≥,-, ⊓, ⊔,⊤,⊥, ¬) is a notational variant of ALCQI, while, e.g., L(∃, ⊓,⊤) corresponds to EL and L(∀, ∃, ⊓, ⊤, ⊥) to ALE. This notation thus allows us to state results for a large variety of languages for concepts.

Ontology Language We consider the very popular DL-Lite ontology language [Artale et al., 2009]. DL-Lite concept inclusions (CIs) are expressions of the form B ⊑ C, respectively, where B, C are concept expressions built through the grammar rules (we write below ∃S as a shorthand for ∃S.⊤)

with R ∈ NR and A ∈ NC. We call concepts of the form B above basic concepts. A DL-Lite ontology is a finite set of DL-Lite CIs. Note that every DL-Lite ontology is satisfiable.

Semantics An interpretation I = (∆I , ·I ) w.r.t. a signature (ΣC, ΣR) is a structure, in the traditional model-theoretic sense. It consists of a non-empty set ∆I , called the domain, and a function ·I that assigns a subset AI ⊆ ∆I of the domain to each A ∈ ΣC and a binary relation RI ⊆ ∆I × ∆I over the domain to each R ∈ ΣR. We extend (·)I to concept and role expressions as follows.

We say that an interpretation I satisfies a CI C ⊑ D if C I ⊆ DI . We write I |= α if I satisfies a CI α. Moreover, we say that I satisfies an ontology O, written I |= O, if I |= α for all CIs α in O. A concept C is satisfiable w.r.t. an ontology O (or vice-versa) if there is an interpretation I |= O with C I ̸= ∅; a concept C subsumes D relative to O (denoted O |= C ⊑ D) if C I ⊆ DI for all interpretations I |= O; and two concepts C, D are equivalent relative to O if C I = DI for all interpretations I |= O. We use |= C ⊑ D as a shorthand for ∅ |= C ⊑ D when indicating that a subsumption holds relative to the empty ontology.

We also write C ≡ D as a shorthand for C ≡∅ D.

A pointed interpretation is a pair (I, d) where I is an interpretation and d ∈ ∆I is a domain element. We say that a pointed interpretation (I, d) satisfies a concept C if d ∈ C I . A pointed interpretation (I, d) is finite if ∆I is a finite set.

Theorem 2.1. (Finite Controllability) Let C,D ∈ L(∀, ∃,≥ ,-, ⊓, ⊔,⊤,⊥, ¬) and let O be a DL-Lite ontology. Then C ̸≡O D iff there is a finite pointed interpretation (I, d) with I |= O and d ∈ ((C ⊓ ¬D) ⊔ (¬C ⊓ D))I .

Labeled Examples and Finite characterisations An example is a finite pointed interpretation (I, d), labelled either positively (with a "+") or negatively (with a "-"). We say that an example (I, d) is a positive example for a concept C if d ∈ C I , and otherwise (I, d) is a negative example for C. We may omit "for C" when this is clear from the context. We will use the notation E = (E+, E-) to denote a finite collection of examples labeled as positive and negative. A concept C fits a set of positively and negatively labelled examples if it is satisfied on all the positively labelled examples and not satisfies on any of the negatively labelled examples. 1

A finite characterisation for a concept C w.r.t. concept language L is a finite collection of labeled examples E = (E+, E-) such that C fits E and every concept D ∈ L that fits E is equivalent to C. A concept language L admits finite characterisations if for every pair of finite sets ΣC ⊆ NC, ΣR ⊆ NR, every concept C ∈ L[ΣC, ΣR] has a finite characterisation w.r.t. L[ΣC, ΣR]. We say that L admits polynomial-time computable characterisations if, furthermore, there is an algorithm that, given an input concept C ∈ L[ΣC, ΣR] outputs a finite characterisation E = (E+, E-) of C w.r.t. L[ΣC, ΣR] in time polynomial in the size of the concept |C| and the size of the signature |ΣC| + |ΣR|. This implies that E+ and E- consist of polynomially many, polynomial-size examples. Therefore, if L(O) admits polynomial time computable characterisations it has polynomial teaching size in the sense of [Telle et al., 2019]. Admitting finite or polynomial time computable characterisations is a monotone property of concept classes.

We defined examples as finite pointed interpretations, because they are intended as objects that can be communicated to a user and/or specified by a user. This is justified by Thm. 2.1, which shows that any two non-equivalent concepts can be distinguished by a finite pointed interpretation.

It may not be clear to the reader why the above definition of "admitting finite characterisations" involves a quantification over vocabularies. The following example explains this.

Example 2.1. Consider the concept C = ∃R.A. Let E = (E+, E-) with E+ = {(I, d1)} and E- = {(I, d3)}, where I is the following interpretation.

▷

⊴

glyph[a0]

◁

Clearly, C fits E. In fact, it can be shown that C is the only L(∃, ⊓, ⊔)-concept (up to equivalence) that fits E and that uses only the concept name A and role name R. In other words, E is a finite characterisation of C w.r.t. L(∃, ⊓, ⊔)[ΣC, ΣR] with ΣC = {A} and ΣR = {R}. In contrast, E does not uniquely characterize C with respect to L(∃, ⊓, ⊔)[Σ′C , ΣR] with Σ′C = {A, B} since ∃R.(A⊔B) fits E and is not equivalent to C. Therefore, what qualifies as a finite characterisations depends on the choice of vocabulary.

1 Equivalently, a concept C fits a set of positively and negatively labelled examples if all the positively labelled examples are positive examples for C, and all the negatively labelled examples are negative examples for C.

The notions of an example and of a finite characterisation naturally extend to the case with an ontology O, where we now require that each example satisfies O, and we replace concept equivalence by equivalence relative to O. More precisely, an example for O is a finite pointed interpretation (I, d) with I |= O, labelled either positively or negatively. A finite characterisation for a concept C w.r.t. a concept language L under O is a finite collection E = (E+,E-) of examples for O such that for every D ∈ L that fits E, C ≡O D. A concept language L admits finite characterisations under L′ ontologies if for every O in L′ and every pair of finite sets ΣC ⊆ NC,ΣR ⊆ NR, every concept C ∈ L[ΣC,ΣR] has a finite characterisation w.r.t. L[ΣC, ΣR] under O.

Example 2.2. Consider the concept language L(⊓, ⊔, ¬) and concept names ΣC = {Animal, Cat,Dog, Red}. Note that there are no role constructs in the language. Let O be the DL-Lite ontology that expresses that Cat and Dog are disjoint subconcepts of Animal. Now consider the concept C = Cat ⊓ Red. Let I be the interpretation with

• ∆I = {a, a′ , b, b′ , c, c′ , d, d′ },
• AnimalI = {a, a′ , c, c′ , d, d′ },
• CatI = {c, c′ }, DogI = {d, d′ }, RedI = {a, b, c, d},

which satisfies O. It can be shown that the collection of labeled examples (E+,E-) with E+ = {(I, c)} and E- = {(I, a), (I, a′ ), (I, b), (I, b′ ), (I, c′ ), (I, d), (I, d′ )} is a finite characterisation of C w.r.t. L(⊓, ⊔, ¬) under O. On the other hand, the same set of examples is not a finite characterisation under the empty ontology, because Cat⊓Red⊓¬Dog also fits but is not equivalent to C in the absence of the ontology. Thus, in this case, the ontology helps to reduce the number of examples needed to uniquely characterize C. Moreover, the ontology can rule out unnatural examples, since in this case the characterisation would need to include a negative example satisfying Cat ⊓ Red ⊓ Dog.

Remark 2.2. We have defined an example as a pointed finite interpretation (I, d) and we call such an example a positive example for C if d ∈ C I and a negative example otherwise. In some of the prior literature on learning description logic concepts, examples were instead defined as pointed ABoxes (A, a) [Funk et al., 2022; Konev et al., 2016; Ozaki et al., 2020] 2 , while e.g. [Fortin et al., 2022] also work with finite interpretations (in their case, linear orders) as examples. Such a pointed ABox is then considered a positive example for C under an ontology O if a is a certain answer for C in A under O (i.e., aI ∈ C I for all interpretations with I |= O and I |= A) , and a negative example otherwise. Let us call the latter type of examples "ABox-examples". Consider the concepts C = ∀R.P and C ′ = ∀R.Q. Although they are clearly not equivalent, it is not possible to distinguish them by means of ABox-examples (under, say, an empty ontology), for the simple reason that there does not exist a positive ABox-example for either of these concepts. This motivates our decision to define examples as pointed interpretations. This is tied to the fact that we study concept languages that include universal quantification and/or negation. Hence, for concept languages contained in L(∃, ≥, ⊓, ⊔, ⊤, ⊥), such as EL, there is essentially no difference between finite characterisations using ABox-examples and finite characterisations using interpretation-examples in the absence of an ontology.

2 By a pointed ABox (A, a) we mean a finite set A of assertions of the form A(b) and R(b, c) with A a concept name, R a role name, and b, c individual names (over the given signature), together with an individual name a occurring in some assertion in A.

However, there are some further repercussions for having interpretations instead of ABoxes as examples in the case with ontologies, even for such weaker concept languages. Intuitively, in the presence of a DL-LiteH-ontology O, any ABox consistent with O can be viewed as a succinct representation of a possibly infinite interpretation (i.e. its chase). Conversely, a finite interpretation can always be conceived of as an ABox. The difference shows up as follows: it was shown in [Funk et al., 2022] that L(∃, ⊓,-) admits finite characterisations under DL-LiteH ontologies in the setting where examples are pointed ABoxes. We see in Section 4 below that the same does not hold in our setting.

Size of Concepts and Examples For any concept C ∈ L(∀, ∃, ≥, -, ⊓, ⊔, ⊤, ⊥), we write |C| for the number of symbols in the syntactic expression C. The numbers occurring in C are assumed to be represented using a binary encoding. All our lower bounds also hold when numbers are represented in unary. Let nr(C) be the the largest natural number occurring in C. Further, let dp(C) be the role depth of C, i.e. the longest sequence of nested quantifiers and/or ≥ operators in C. Finally, for interpretations I we set |I| := |∆I |, and the size of an example (I, d) is simply |I|.

3 Finite Characterisations without Ontology

Our aim, in this section, is to prove Thm. 1.1 and 1.2. We start by listing relevant known results.

Theorem 3.1. The following results are known (cf. [Cate and Koudijs, 2024]).

1. L(∃,-, ⊓,⊤,⊥) admits polynomial-time computable characterisations (from [Cate and Dalmau, 2022]).
2. L(∃,-, ⊓, ⊔,⊤,⊥) admits finite characterisations. However, finite characterisation are necessarily of exponential size (from [Alexe et al., 2011]).
3. L(∀, ∃, ⊓, ⊔) admits finite characterisations. However, finite characterisation are necessarily of non-elementary size (from [Cate and Koudijs, 2024]).
4. Neither L(∀, ∃, ⊓, ⊥) nor L(∀, ∃, ⊔, ⊤) admit finite characterisations (from [Cate and Koudijs, 2024]).

To establish Thm. 1.1, it remains to show that L(∀, ∃,≥ , ⊓, ⊤) admits finite characterisations and that L(≥, ⊥), L(≥ , ⊔) and L(∀, ∃, -, ⊓) do not admit finite characterisations.

3.1 Finite Characterisations for L(∀, ∃,≥, ⊓,⊤)

The next results involve a method for constructing examples that forces fitting concepts to have a bounded role depth.

Proposition 3.2. Fix finite sets ΣC ⊆ NC and ΣR ⊆ NR. For all n, k ≥ 0, there is a set of examples E+ n,k , such that for all L(∀, ∃, ≥, ⊓, ⊤)[ΣC, ΣR] concept expressions C, the following are equivalent:

1. C is equivalent to a concept expression of role depth at most n and maximum number restriction k;

2. C fits the positive examples E+ n,k .

We illustrate the result for the special case where n = 3 and k = 2. It suffices to choose as positive examples the examples (I, d1) and (I ′ , d1) based on the following interpretations:

where an arrow d → d′ means that the pair (d, d′ ) belong to the interpretation of every role in ΣR; and every element except e′ belongs to the interpretation of every atomic concept in ΣC. It can be shown that every concept fitting (I, e) and (I ′ , e) as positive is equivalent to a depth 0 concept. It follows by backward induction that an L(∀, ∃, ≥, ⊓, ⊤)[ΣC , ΣR]-concept fits (I, d1) and (I ′ , d1) as positive examples iff it has role depth at most 3 and maximum number restriction 2.

As a consequence, we obtain the following.

Theorem 3.3. L(∀, ∃,≥, ⊓,⊤) admits finite characterisations.

We show this by appending to E+ n,k as many positive and negative examples needed to distinguish a concept from all the finitely many other concepts with depth at most n and number restriction at most k. Hence, we obtain a nonelementary upper bound on the size of finite characterisations for L(∀, ∃, ≥, ⊓, ⊤), since there are already tower(n) (i.e. an iterated power 2...2 of height n) many pairwise non-equivalent L(∃, ⊓, ⊤) concepts of role depth n. We do not have a matching lower bound for the above language, and it remains open whether there are more efficient approaches. In the next subsection, we show that the fragment L(∃, ≥, ⊓, ⊤) does admit an elementary (doubly exponential) construction of finite characterisations.

3.2 An Elementary Construction of Finite Characterisations for L(∃, ≥, ⊓, ⊤)

Since ∃ is expressible as ≥ 1, we restrict our attention to L(≥, ⊓, ⊤) in what follows.

Theorem 3.4. There is a polynomial time algorithm for testing if |= C ⊑ C ′ , where C, C ′ ∈ L(≥, ⊓, ⊤).

The above theorem can be proved by showing that entailments between conjunctions of L(≥, ⊓, ⊤)-concepts can be reduced to entailments between the individual conjuncts.

Next, we will use Theorem 3.4 to show that concepts in L(≥, ⊓, ⊤) can be brought into a certain normal form in polynomial time. Recall that every L(≥, ⊓, ⊤)-concept expression C that is not a concept name is a conjunction C1 ⊓ · · · ⊓ Cn (n ≥ 0) where each Ci is either an concept name or is of the form ≥ kR.C ′ where C ′ is again a L(≥, ⊓,⊤)-concept expression. Here we conveniently view ⊤ as a shorthand for an empty conjunction. We say that such a concept expression C is irredundant if it does not contain a conjunction that includes distinct conjuncts Ci, Cj with |= Ci ⊑ Cj .

Proposition 3.5. Every L(≥, ⊓, ⊤)-concept C is equivalent to an irredundant L(≥, ⊓, ⊤)-concept, which can be computed in polynomial time.

The following two lemmas, intuitively, tell us that, every pointed interpretation satisfying a concept C ∈ L(≥, ⊓, ⊤) contains a small pointed sub-interpretation that already satisfies C and falsifies all L(≥, ⊓, ⊤)-concepts falsified in the original interpretation. We write I ⊆ I ′ to denote that I is a sub-interpretation of I ′ (that is, ∆I ⊆ ∆I ′ and XI ⊆ XI ′ for all X ∈ ΣC ∪ ΣR).

Lemma 3.6. For every concept C ∈ L(≥, ⊓, ⊤), interpretation I, and d ∈ C I , there is an I ′ ⊆ I with d ∈ C I ′ and |I ′ | ≤ |C||C| .

Lem. 3.6 pairs well with the next lemma, showing that L(≥, ⊓, ⊤)-concepts are ⊆-monotone.

Lemma 3.7. For all concepts C ∈ L(≥, ⊓, ⊤) and interpretations I ⊆ I ′ , it holds that C I ⊆ C I ′ .

This can be proved by a straightforward induction argument, or, alternatively, follows from the Łos-Tarski theorem. Together these prove the following theorem.

Theorem 3.8. For every two concepts C,D ∈ L(≥, ⊓,⊤) such that ̸|= C ⊑ D, there is some pointed interpretation (I, d) of size |I| ≤ |C||C| such that d ∈ (C ⊓ ¬D)I .

It follows from this theorem that, in order to construct a finite characterization of an L(≥, ⊓, ⊤)-concept, it suffices to pick as our positive examples all positive examples of size at most |C||C| . It only remains to explain howwe construct the negative examples. This is done through a novel frontier construction construction for L(∃,≥, ⊓,⊤). Intuitively, a frontier for C is finite set of concepts that are strictly weaker than C and that separates C from all concepts strictly weaker than C (cf. Figure 2 for a graphical depiction).

Definition 3.9. (Frontier) Given a concept language L and a concept C ∈ L, a frontier for C w.r.t. L is a finite set of concepts {C1, . . . , Cn} ⊆ L such that:

• (i) |= C ⊑ Ci and ̸|= Ci ⊑ C for all 1 ≤ i ≤ n, and

Frontiers relative to an ontology O are defined similarly, except that each |= or ̸|= is replaced by "O |=", resp. "O ̸|=".

Theorem 3.10. For each C ∈ L(≥, ⊓, ⊤), one can construct a frontier F(C) for C w.r.t. L(≥, ⊓, ⊤) in polynomial time.

By combining Thm. 3.10 and 3.8, we obtain the main result of this section (where Lem. 3.6 is used to bound the size of the positive examples and Thm. 3.10 is used to construct the negative examples).

Theorem 3.11. L(≥, ⊓, ⊤) admits finite characterisations of doubly exponential size.

Thm. 3.15 below implies an exponential lower bound for the same problem, leaving us with a gap of one exponential.

Remark 3.12. The polynomial-time frontier construction from Thm. 3.10 is interesting in its own right, particulary because frontiers are closely related to upward refinement operators, a core component of DL learning systems such as the ELTL variant of DL Learner [B¨uhmann et al., 2016]. We can show that the function ρ mapping each L(≥, ⊓, ⊤)-concept to its frontier is an ideal upward refinement operator as defined in [Lehmann and Hitzler, 2007]. This follows from the fact that, for every L(≥, ⊓,⊤)-concept C there are only finitely many L(≥, ⊓, ⊤)-concepts D, up to equivalence, for which |= C ⊑ D. The latter, in turn, holds because |= C ⊑ D implies that dp(D) ≤ dp(C) and nr(D) ≤ nr(C).

3.3 Negative Results

The following theorem summarizes our negative result pertaining to the existence of finite characterisations.

Theorem 3.13. L(≥, ⊔) and L(≥, ⊥) and L(∀, ∃, -, ⊓) do not admit finite characterisations.

In the remainder of this section, we establish lower bounds on the size and/or the complexity of computing finite characterisations. The following lemma will be helpful for this.

Lemma 3.14. If ⊓ ∈ O and (E+,E-) is a finite characterisation of a concept C ∈ L(O) w.r.t. L(O), then it must be that, for all C ′ ∈ L(O), if ̸|= C ⊑ C ′ then C ′ is falsified on some positive example in E+.

Using this lemma, we show:

Theorem3.15. L(≥, ⊓) does not admit polynomial size characterisations. In fact, there are L(≥, ⊓)-concepts (Ci)i∈N of constant depth and number restriction such that every finite characterisation of Ci has size at least 2|Ci| .

The next lemma establishes a connection between the problem of computing finite characterisations and the problem of checking subsumptions between concepts.

Lemma 3.16. If L(O) admits polynomial characterisations, ⊓ ∈ O and L(O) has a polynomial time model checking problem (in combined complexity), then subsumptions between L(O) concepts can be tested in polynomial time.

This allows us to use hardness results from the literature on subsumption algorithms to establish hardness of computing certain example sets. Note that the converse of Lem. 3.16 fails, since by Theorem 3.4 L(≥, ⊓, ⊤) has a polynomial time subsumption problem but does not admit polynomial-time computable characterisations (Thm. 3.15).

The following subsumption hardness result follows from [Donini et al., 1992].

Proposition 3.17. Subsumption checking for L(∀, ∃, ⊓) is NP-hard.

Using Lem. 3.16 we can the establish our next result, resolving an open question from [Cate and Koudijs, 2024].

Corollary 3.18. L(∀, ∃, ⊓) does not admit polynomial time computable characterisations, unless P = NP.

Theorems 1.1 and 1.2 follow from the results proved in this section and prior results that we recalled in Thm. 3.1.

4 Finite Characterisations With Ontologies

In this section we are concerned with finite characterisations of concepts w.r.t. ontologies.

4.1 L(∃, ⊓,⊤,⊥) Admits Finite Characterisations Under DL-Lite Ontologies

We show that L(∃, ⊓,⊤,⊥) admits finite characterisations under DL-Lite ontologies. The proof uses the following key lemma from [Funk et al., 2022]. Recall the definition of a frontier relative to an ontology (Def. 3.9).

Lemma 4.1. ([Funk et al., 2022]) There is a polynomial-time algorithm that takes as input a L(∃, ⊓, ⊤)-concept C and a DL-Lite ontology O such that C is satisfiable w.r.t. O, and outputs a frontier for C w.r.t. L(∃, ⊓, ⊤) relative to O.

Our second ingredient is a polynomial-time canonical model construction for L(∃, ⊓,⊤)-concepts w.r.t. DL-Lite ontologies. Intuitively, one can think of a canonical model, for a concept C and ontology O, as a minimal positive example, i.e., a positive example for C under O that "makes as few other concepts true as possible". We show that every L(∃, ⊓,⊤) concept that is satisfiable w.r.t. a given DL-Lite ontology O admits a polynomial-time computable canonical model w.r.t. O that satisfies its CIs.

Theorem 4.2. There is a polynomial-time algorithm that takes a L(∃, ⊓, ⊤)-concept C and a DL-Lite ontology O, where C is satisfiable w.r.t. O, and that produces a pointed interpretation (IC,O, dC) (which we will call the canonical model of C under O) with the following properties.

1. for all L(∃, ⊓,⊤)-concepts D, dC ∈ DIC,O iff O |= C ⊑ D. In particular, we have that dC ∈ C IC,O .

2. Moreover, IC,O |= O.

The proof is based on previous constructions of canonical model for query answering [Kontchakov et al., 2010]. Canonical models for query answering usually differ from those for satisfying the ontology. In the case of the EL ontology language (consisting of CIs C ⊑ D where C,D ∈ L(∃, ⊓, ⊤)), it was shown that a polynomial canonical model for EL concepts can be constructed [Baader et al., 2005; Lutz and Wolter, 2010], but it cannot be ensured that this canonical model satisfies the ontology. In fact there are EL ontologies for which there is no finite canonical model satisfying the ontology [Guimar˜aes et al., 2023, Example 33].

Thm. 4.2 does produce models satisfying the DL-Lite ontology, and this is important for our purpose. By combining the frontier construction with the canonical model construction, we can construct finite characterisations in polynomial time for concepts that are satisfiable w.r.t. a given ontology. For inconsistent concepts, we separately prove the following.

Lemma 4.3. Let O be a DL-Lite ontology. Then the unsatisfiable concept ⊥ admits an exponentially sized finite characterisation w.r.t. L(∃, ⊓, ⊤, ⊥) under O.

Given the above, we obtain the main result of this section.

Theorem 4.4. L(∃, ⊓, ⊤, ⊥) admits finite characterisations under DL-Lite ontologies. Moreover, for concepts C ∈ L(∃, ⊓, ⊤, ⊥) that are satisfiable w.r.t. the given ontology O, a finite characterisation can be computed in polynomial time (in |C| and |O|).

Remark 4.5. The restriction to satisfiable concepts in the above theorem is essential given that the ontology is treated as part of the input. Specifically, let O be the ontology O := {A0 ⊑ ¬A0} ∪ {Ai ⊑ ¬Bi | i = 1 . . . n}. It can be shown, for the concept A0 (which is unsatisfiable w.r.t. O), that every finite characterisation must be of size at least 2n (see e.g. [Funk et al., 2021] for a similar style of counterexample). If the ontology is treated as fixed in the complexity analysis, however, a finite characterisation could be computed in polynomial time for all L(∃, ⊓, ⊤, ⊥)-concepts.

4.2 Negative Results

The following two negative results establish that we cannot further enrich the concept language.

Theorem 4.6. Let O be the DL-Lite ontology {A ⊑ ¬A}. Then L(≥) and L(∀, ∃, ⊓) do not admit finite characterisations under O.

Theorem 4.7. Let O be the DL-Lite ontology {A ⊑ ∃R, ∃R- ⊑ A}. Then L(∃, -, ⊓) does not admit finite characterisations under O.

These results, together with Thm. 4.4, imply Thm. 1.3, as they show that no extension of L(∃, ⊓,⊤,⊥) with ≥ or ∀ admits finite characterisations under DL-Lite ontologies. Our positive result in Section 4.1 also cannot be extended to DL-LiteH ontologies (that is, DL-Lite extended with role inclusions [Artale et al., 2009]). This contrasts with a recent positive result for EL with DL-LiteH ontologies using ABoxexamples [Funk et al., 2022].

Theorem 4.8. Let O be the DL-LiteH ontology {A ⊑ ∃R, ∃R- ⊑ A,R- ⊑ S}. Then L(∃, ⊓) does not admit finite characterisations under O.

5 Summary and Discussion

We systematically studied the existence and complexity of computing finite characterisations for concept languages L(O) with {∃, ⊓} ⊆ O ⊆ {∀, ∃, ≥, -, ⊓, ⊔, ⊤, ⊥, ¬}, both in the absence of an ontology and in the presence of a DL-Lite ontology. While we classified most concept languages, there are a few cases left open, detailed below.

In passing, we obtained a polynomial-time algorithm for checking subsumptions between L(∃, ≥, ⊓, ⊤) concepts, and a polynomial time algorithm for computing frontiers of L(∃, ≥ , ⊓, ⊤)-concepts (which gives rise to a polynomial-time ideal upward refinement operator, cf. Remark 3.12).

Repercussions for Exact Learnability As we mentioned in the introduction, the existence of polynomial-time computable characterisations is a necessary precondition for the existence of polynomial-time exact learning algorithms with membership queries. It was shown in [Cate and Dalmau, 2022] that L(∃, -, ⊓, ⊤, ⊥) is indeed polynomial-time exactly learnable with membership queries. Thm. 1.2 therefore implies that L(∃,-, ⊓,⊤,⊥) is a maximal fragment of ALCQI that is efficiently exactly learnable with membership queries, in the absence of an ontology.

Conversely, every algorithm for effectively computing finite characterisations also gives rise to an effective exact learning algorithm with membership queries, although not an efficient one. Thus, Thm. 1.1 also tells us something about the limits of (not-necessarily efficient) exact learnability with membership queries, without an ontology.

Finally, in the same way, Thm. 1.3 tells us something about the limits of exact learnability with membership queries where the membership queries can only be asked for examples satisfying a given DL-Lite ontology. The authors are not aware of prior work on such a notion of learnability.

Open questions Open questions include whether L(∃,≥ , -, ⊓) or L(∃, ≥, -, ⊤) admit finite characterisations (under the empty ontology) and whether concept languages between L(∃, ⊓, ⊔) and L(∃, ⊓, ⊔, ⊤, ⊥) admit finite characterisations under DL-Lite ontologies. Moreover, we do not yet have tight bounds on the complexity of computing finite characterisations for many of the concept languages we study that admit finite characterisations. In particular, for concept languages between L(∀, ∃, ⊓) and L(∀, ∃, ≥ ⊓, ⊤) we have an NP lower bound (from Corollary 3.18) and a non-elementary upper bound (from Thm. 3.3). In Thm. 3.11 we managed to improve this to a doubly exponential upper bound for L(∃,≥, ⊓,⊤), while an exponential lower bound for L(∃, ≥, ⊓) follows from Thm. 3.15. It remains to find tight bounds for these fragments.

Since our setting includes ∀ and ¬, we were forced to work with finite pointed interpretations as examples (cf. Remark 2.2). If one discards these connectives it becomes natural to adopt pointed ABoxes as examples, as in [Funk et al., 2022]. Many of our negative results for the existence of finite characterisations under DL-Lite ontologies rely on examples being finite pointed interpretations satisfying the ontology, except Thm. 4.6 because for the ontology in question, there is essentially no difference between a (consistent) ABox and a finite interpretation. Our study therefore only leaves open the possibility of positive results in the ABox-as-examples setting under DL-Lite ontologies for fragments of L(∃, -, ⊓, ⊔, ⊤, ⊥).

It would be of interest to investigate finite characterisations under ontology languages other than DL-Lite. The recent paper [Cate et al., 2024] implies some positive results for L(∃, ⊓, ⊔, ⊤, ⊥) relative to ontologies defined by certain universal Horn formulas (e.g. symmetry and transitivity).

One of the motivations of our study was to generate examples to illustrate a concept to a user (e.g, for debugging purposes or for educational purposes). Finding practical solutions for this require more research, e.g., on how to generate "natural" examples (cf. [Glavic et al., 2021] for an overview of related problems and techniques in data management).

Acknowledgments

Balder ten Cate is supported by the European Union's Horizon 2020 research and innovation programme under grant MSCA101031081. Raoul Koudijs and Ana Ozaki are supported by the Research Council of Norway, project number 316022, led by Ana Ozaki.