We propose a new mechanism for integration of OWL ontologies using semantic import relations. In contrast to the standard OWL importing, we do not require all axioms of the imported ontologies to be taken into account for reasoning tasks, but only their logical implications over a chosen signature. This property comes natural in many ontology integration scenarios. In this paper, we study the complexity of reasoning over ontologies with semantic import relations and establish a range of tight complexity bounds for various fragments of OWL.
Ontology integration is a research topic which, in particular, aims at organizing information on different domains in a modular way so that information from one ontology can be reused in other ontologies. There is a number of approaches known in the literature [1–5, 8], which address this problem from the point of view of ontology linking and importing, see, e.g., an overview in [6]. Integration of multiple ontologies in OWL is organized via importing: an OWL ontology can refer to one or several other OWL ontologies, whose axioms must be implicitly present in the ontology. The importing mechanism is simple in that reasoning over an ontology with an import declaration is reduced to reasoning over the import closure consisting of the axioms of the ontology plus the axioms of the ontologies that are imported (possibly indirectly). For example, if ontology O1 imports ontologies O2 and O3, each of which, in turn, imports ontology O4, then the import closure of O1 consists of all axioms of O1 O4.
Although the OWL importing mechanism may work well for simple ontology integration scenarios, it may cause some undesirable side effects if used in complex import situations. To illustrate the problem, suppose that in the above example, O4 is an ontology describing a typical university. It may include concepts such as Professor, Course, and axioms stating, e.g., that each professor must teach some course: Professor v 9teaches:Course. Now suppose that O2 and O3 are ontologies describing respectively, Oxford and Cambridge universities that use O4 as a prototype. For example, O2 may include mapping axioms OxfordProfessor Professor, OxfordCourse Course, from which, due to the axiom in O4, it is now possible to conclude that OxfordProfessor v 9teaches:OxfordCourse. Likewise, using similar mapping axioms in O3, it is possible to obtain that CambridgeProfessor v 9teaches:CambridgeCourse. Finally, suppose that O1 is an ontology aggregating information about UK universities, importing, among others, the ontologies O2 and O3 for Oxford and Cambridge universities. Although the described scenario seems plausible, there will be some undesirable consequences in O1 due to the mapping axioms of O2 and O3 occurring in the import closure: OxfordProfessor CambridgeProfessor, OxfordCourse CambridgeCourse. The main reason for these consequences is that the ontologies O2 and O3 happen to reuse the same ontology O4 in two different and incompatible ways. Had they instead used two different ‘copies’ of O4 as prototypes (with concepts renamed apart), no such problem would take place. Arguably, the primary purpose of O2 and O3 is to provide semantic description of the vocabulary for Oxford and Cambridge universities, and the means of how it is achieved—either by writing the axioms directly or reusing third party ontologies such as O4—should be an internal matter of these two ontologies and should not be exposed to the ontologies that import them. Motivated by these observations, in this paper we consider a refined mechanism for importing of OWL ontologies called semantic importing. The main difference with the standard OWL importing is that each import is limited only to a subset of symbols. Intuitively, only logical properties of these symbols entailed by the imported ontology should be imported. These symbols can be regarded as the public (or external) vocabulary of the imported ontologies. For example, ontology O2 may declare the symbols OxfordProfessor, OxfordCourse, and teaches public, leaving the remaining symbols only for the internal use. Importantly, in our approach every ontology has its own view on ontologies it imports and the views are independent between ontologies unless coordinated by the ‘topology’ of import relations.
The main results of this paper are tight complexity bounds for reasoning over ontologies with semantic imports. We consider ontologies formulated in different fragments of OWL starting from the Description Logic (DL) E L and concluding with the DL SROIQ, which corresponds to OWL 2. We also distinguish the case of acyclic imports, when ontologies cannot (possibly indirectly) import themselves. Our completeness results for ranges of DLs are summarized in the following table, where a and c denote the case of acyclic/cyclic imports:
DLs Completeness EL – EL++ ExpTime a containing EL RE (undecidable) c ALC – SHIQ 2ExpTime a
R – SRIQ 3ExpTime a ALCHOIF – SHOIQ coN2ExpTime a
ROIF – SROIQ coN3ExpTime a
Theorems 1, 8 2, 9 3, 8 4, 8 5, 8 6, 8 An extended version of the paper containing all proofs and additional results is available at https://arxiv.org/abs/1705.04719 2
We assume that the reader is familiar with the family of Description Logics from E L to SROIQ, for which the syntax is defined using a recursively enumerable alphabet consisting of infinite disjoint sets NC, NR, Ni of concept names (or primitive concepts), roles, and nominals, respectively. The semantics of DLs is given by means of (first-order) interpretations. An ontology is a set of concept inclusions which are called ontology axioms. A signature is a subset of NC [ NR [ Ni. Interpretations I and J are said to agree on a signature , written as I = J , if the domains of I and J coincide and the interpretation of -symbols in I is the same as in J . We denote the reduct of an interpretation I onto a signature as Ij . The signature of a concept C, denoted as sig (C), is the set of all concept names, roles, and nominals occurring in C. The signature of a concept inclusion or an ontology is defined identically.
Given a signature , suppose one wants to import into an ontology O1 the semantics of -symbols defined by some other ontology O2, while ignoring the rest of the symbols from O2. Intuitively, importing the semantics of -symbols means reducing the class of models of O1 by removing those models that violate the restrictions on interpretation of these symbols, which are imposed by the axioms of O2: Definition 1. A (semantic) import relation is a tuple = hO1; ; O2i, where O1 and
O2. We say that a model I j= O1 satisfies the import relation if there exists a model J j= O2 such that I = J .
Example 1. Consider the import relation = hO1; ; O2i, with O1 = fB v Cg, O2 = fA v 9r:B; 9r:C v Dg, and = fA; B; C; Dg. It can be easily shown using Definition 1 that a model I j= O1 satisfies if and only if I j= A v D.
Note that if contains all symbols in O2 then I j= O1 satisfies = hO1; ; O2i if and only if I j= O1 [ O2. That is, the standard OWL import relation is a special case of the semantic import relation, when the signature contains all the symbols from the imported ontology. If O has several import relations i = hO; i; Oii, (1 i n), one can define the entailment from O by considering only those models of O that satisfy all imports: O j= if I j= for every I j= O which satisfies all 1; : : : ; n. In practice, however, import relations can be nested: imported ontologies can themselves import other ontologies and so on. The following definition generalizes entailment to such situations.
tologies. For a DL L, a L-ontology network is a network, in which every ontology is a set of L-axioms. A model agreement for N (over a domain ) is a mapping that assigns to every ontology O occurring in N a class (O) of models of O with domain such that for every hO1; ; O2i 2 N and every I1 2 (O1) there exists I2 2 (O2) such that I1 = I2. An interpretation I is a model of O in the network N (notation I j=N O) if there exists a model agreement for N such that I 2 (O). An ontology O entails a concept inclusion ' in the network N (notation O j=N ') if I j= ', whenever I j=N O.
An ontology network can be seen as a labeled directed multigraph in which nodes are labeled by ontologies and edges are labeled by sets of signature symbols. Note that Definition 2 also allows for cyclic networks if this graph is cyclic. Note that if O j= ' then O j=N ', for every network N .
In this paper, we are concerned with the complexity of entailment in ontology networks, that is, given a network N , an ontology O and an axiom ', decide whether O j=N '. We study the complexity of this problem wrt the size of an ontology network N , which is defined as the total length of axioms (considered as strings) occurring in ontologies from N . 3
First, we illustrate the expressiveness of ontology networks by showing that acyclic networks allow for succinctly representing axioms with nested concepts and role chains of exponential size, while cyclic ones allow for succinctly representing infinite sets of axioms of a special form. The lemmas given in this Section are used as building blocks in the proofs of our hardness results in Section 4.
For a natural number n > 0, let 9(r; C)n:D be a shortcut for the nested concept 9r:(C u 9r:(C u : : : n times : : : u 9r:(C u D) : : :)), where C, D are DL concepts and r a role (in case n = 0 the above concept is set to be D). For n > 1, let (r)n denote the role chain r : : : n times : : : r. For a given n > 0, let 1exp(n) be the notation for 2n and for k > 1, let (k + 1)exp(n) = 2kexp(n). Then 9(r; C)kexp(n):D (respectively, (r)kexp(n)) stands for a nested concept (role chain) of the form above having size exponential in n. In the following, we use abbreviations 9(r; C)n := 9(r; C)n:> and 9:r9nr::C9rn:=19: :(rC; >a)nnd:Cfo.rFnor>n >2, 18,rt<hne:Cexpwreilslssiotann8drfno:rC w1F6illmb<enu8sremd :aCs.aLsehtoOrtcubte faonr ontology and N an ontology network. O is said to be expressible by N if there is an ontology ON in N such that fIjsig (O) j I j=N ON g = fJ jsig (O) j J j= Og. In case we want to stress the role of ontology ON in the network N , we say that O is (N ; ON )expressible. An axiom ' is expressible by a network N if so is ontology O = f'g. The next two lemmas follow immediately from the definition of expressibility.
of the single import relation hO; ?; ?i. If an ontology Oi is (Ni; Oi0)-expressible, for a network Ni, ontology Oi0, and i = 1; 2, then O1 [ O2 is (N ; ON )-expressible, for ontology ON = ? and a network1 N = N1 [ N2 [ fhON ; sig (Oi); Oi0igi=1;2.
For an axiom ' and a set of concepts fC1; : : : ; Cng, n > 1, let us denote by '[C1 7! D1; : : : ; Cn 7! Dn] the axiom obtained by substituting every concept Ci with a concept Di in '. For an ontology O, let O[C1 7! D1; : : : ; Cn 7! Dn] be a notation for S'2O '[C1 7! D1; : : : ; Cn 7! Dn].
network N . Let C1; : : : ; Cn be L-concepts and fA1; : : : ; Ang a set of concept names such that Ai 2 sig (O), for i = 1; : : : ; n and n > 1. Then ontology O~ = O[A1 7!
Proof Sketch. Denote = fA1; : : : ; Ang and let 0 = fA01; : : : ; A0ng be a set of fresh concept names. Consider ontology O0 = O [ fAi A0igi=1;:::;n. By Lemma 1, O0 is (N 0; ON 0 )-expressible, for an ontology ON 0 and an acyclic L-ontology network N 0 having a linear size (in the size of N ). Consider ontology network N 00 = hON 00 ; (sig (O0) n ) [ 0; ON 0 i, where ON 00 = ?. Then obviously, ontology O00 = O[A1 7! A01; : : : ; An 7! A0n] is (N 00; ON 00 )-expressible. Similarly, by Lemma 1, ontology OC00 = O00 [ fA0i Cigi=1;:::;n is (N~ ; ON~ )-expressible, for an ontology ON~ and an acyclic L-ontology network N~ having a linear size (in the size of N and Ci, for i = 1; : : : ; n). Clearly, it holds ON~ j=N~ O~ and it is easy to show that O~ is (N~ ; ON~ )expressible.
Now we formulate the results on the expressiveness of acyclic E L-, ALC-, and Rontology networks. 1 Note that the size of N is linear in the sizes of N1 and N2.
n > 0, is expressible by an acyclic E L-ontology network of size polynomial in n. Proof Sketch. We show by induction on n that there exists an acyclic E L-ontology network Nn and ontology On such that ' is (Nn; On)-expressible. For n = 0, we define N0 = fhO0; ?; ?ig and O0 = fZ 9r:(A u B)g. In the induction step, let fZ 9(r; A)1exp(n 1):Bg be (Nn 1; On 1)-expressible, for n > 1. Consider ontologies Oc1opy = fB U g, Oc2opy = fU Zg, On = ?. Let Nn be the union i of Nn 1 with the set of the following import relations: hOcopy; fZ; A; B; rg; On 1i, 1 2 for i = 1; 2, hOn; fZ; A; U; rg; Ocopyi, and hOn; fU; A; B; rg; Ocopyi. Let us verify that fIjsig (') j I j=Nn Ong = fIjsig (') j I j= 'g. By the induction assumption we have On 1 j=Nn Z 9(r; A)1exp(n 1):B. Then by the definition of Nn, it holds Oc1opy j=Nn Z 9(r; A)1exp(n 1):U and Oc2opy j=Nn U 9(r; A)1exp(n 1):B and thus, On j=Nn fZ 9(r; A)1exp(n 1):U; U 9(r; A)1exp(n 1):Bg, which yields On j=Nn '. To complete the proof, we show that any model I j= ' can be expanded to a model Jn j=Nn On by setting U Jn = (9(r; A)1exp(n 1):B)I .
The following claim is proved identically to Lemma 3:
v s, where Z; A; B 2 NC, r; s are roles, and n > 0, is expressible by an acyclic E L-,
We continue with results on the expressiveness of acyclic R-ontology networks.
expressible by an acyclic R-ontology network of size polynomial in n. Proof. Consider ontology O = fZ v 8s:A; (r)2exp(n) v sg. Clearly, it holds O j= ' and any model I j= ' can be expanded to a model J j= O by setting sJ = ((r)2exp(n))I . By Lemmas 1, 4, O is expressible by an acyclic R-ontology network of size polynomial in n, from which the claim follows.
Similarly, we demonstrate that an axiom of the form Z v 8r<2exp(n):A, where Z; A 2 NC and n > 0, is expressible by an acyclic R-ontology network of size polynomial in n and show the next statement, which is an analogue of Lemma 4 for the case of double exponent.
n > 0, is expressible by an acyclic R-ontology network of size polynomial in n. Proof. Consider ontology O = fZ v 9s:>; Z v 8s<2exp(n):X; Z v 8s2exp(n):Y; s v rg. By Lemmas 1, 5, and the claim above, we show that O is expressible by an acyclic R-ontology network of size polynomial in n. Then by Lemma 2, so is ontology O = O[X 7! A u 9s:>; Y 7! A u B]. Clearly, we have O j= '. Now let I be an arbitrary model of ' and for m = 2exp(n), let x0; : : : ; xm be arbitrary domain elements such that x0 2 ZI , hx0; x1i 2 rI , and hxi; xi+1i 2 rI , xi 2 AI , for 1 6 i < m, and xm 2 AI uBI . Let J be an expansion of I in which sJ = fhxi; xi+1ig06i<m. Then we have J j= O, from which the claim follows.
expressible by an acyclic R-ontology network of size polynomial in n. Proof. Consider ontology O = fZ v 8r2exp(n):A; Z v 9r2exp(n):Ag. By Lemmas 1, 5, 6, O is expressible by an acyclic R-ontology network of size polynomial in n and by Lemma 2, so is ontology O = O[Z 7! :Z; A 7! :A]. It remains to note that O and f'g are equivalent, so the claim is proved.
We conclude this section with lemmas formulating the expressibility of substitutions by ontology networks.
network N . Let C1; : : : ; Cm be L-concepts and fA1; : : : ; Amg a set of concept names such that Ai 2 sig (O), for i = 1; : : : ; m and m > 1. Then for k = 1; 2 and n > 0, ontology O~ = O[A1 7! 8rkexp(n):C1; : : : ; Am 7! 8rkexp(n):Cm] is expressible by a
N , n, and Ci, for i = 1; : : : ; m, where: L0 = L if L contains ALC and k = 1, or L0 = L if L contains R and k = 2.
Proof. The proof uses Lemmas 4, 7 and is identical to the proof of Lemma 2.
The next statement can be shown similarly by using Lemma 3: Lemma 9. In the conditions of Lemma 8, ontology O~ = O[A1 7! 9r1exp(n):C1; : : : ;
acyclic if so is N and has size polynomial in the size of N , n, and Ci, for i = 1; : : : ; m, where L0 = L if L contains E L.
ontology network N and an ontology ON . Let fA1; : : : ; Ang, n > 1, be concept names such that Ai 2 sig (O), for i = 1; : : : ; n, and let fC1; : : : ; Cng be L-concepts, where every Ci is of the form 9(r; D)p:Ai, for some role r, concept name D, and p > 1. Then ontology O~ = Sm>0 Om, where O0 = O and Om+1 = Om[A1 7! C1; : : : ; An 7!
Proof Sketch. Let = fB1; : : : ; Bkg = Si=1;:::;n(sig (Ci) \ NC) and 0 = fB10; : : : ; Bk0g be a set of fresh concept names disjoint with and sig (O). Let fC10; : : : ; Cn0g be ‘copy’ concepts obtained from C1; : : : ; Cn by replacing every Bi with Bi0, for i = 1; : : : ; k. Consider ontologies O~N 0 = f Bi Bi0 gi=1;:::;k, O0 = f Ai Ci0 gi=1;:::;n, and an ontology network N 0 given by the union of N with the set of import relations hO~N 0 ; sig (O); ON i, hO~N 0 ; 0; O0i, hO0; ; O~N 0 i, where 0 = ( n ) [ 0 and = sig (O) [ Si=1;:::;n sig (Ci). We claim that ontology O~ is (N 0; O~N 0 )-expressible. Denote O~0 = Sm>0 Om0, where Om0 = Om[B1 7! B10; : : : ; Bk 7! Bk0], for all m > 0. First, we show by induction that O~N 0 j=N 0 Om, for all m > 0. The induction base for n = 0 is trivial, since we have O0 = O and O is (N ; ON )-expressible, hON 0 ; sig (O); ON i 2 N 0, and thus, O~N 0 j=N 0 O. Suppose O~N 0 j=N 0 Om, for some ~ m > 0. Since hO0; ; O~N 0 i 2 N 0, we have O0 j=N 0 Om and thus, by the equivalences in O0, it holds O0 j=N 0 Om0+1. Since hO~N 0 ; 0; O0i, we have O~N 0 j=N 0 Om0+1 and hence, by the equivalences in O~N 0 , it holds that O~N 0 j=N 0 Om+1. Finally, in the full proof we show that any model I of O~ can be expanded to a model J j=N 0 O~N 0 , which shows that O~ is (N 0; O~N 0 )-expressible.
We use reductions from the word problem for Turing machines (TMs) and alternating Turing machines (ATMs) to obtain most of the hardness results. We define a Turing Machine (TM) as a tuple M = hQ; A; i, with qh 2 Q being the accepting state, and assume w.l.o.g. that configuration of M is a word in the alphabet Q [ A. An initial configuration is a word of the form b : : : bq0b : : : b, where q0 2 Q and b 2 A is the blank symbol. It is a well-known property of the transition functions of Turing machines that the symbol c0i at position i of a successor configuration c0 is uniquely determined by a 4-tuple of symbols ci 2; ci 1; ci; ci+1 at positions i 2, i 1, i, and i + 1 of a configuration c. We assume that this correspondence is given by the (partial) function 0 and 0 use the notation ci 2ci 1cici+1 7! c0i.
Proof Sketch. We reduce the word problem for TMs making exponentially many steps to entailment in E L-ontology networks. Let M be a TM and n = 1exp(m) an exponential, for m > 0. Consider an ontology O defined for M and n by the following axioms:
A v 9rn (2n+3):(q0 u 9(r; b)2n+2); 9r2n(X u 9r:(Y u 9r:(U u 9r:Z))) v W; 9r:qh v H; 9r:H v H; where A 62 Q [ A
0
for XY U Z 7! W
where H 62 Q [ A
(
Proof Sketch. For a TM M , we define an infinite ontology O, which contains variants
of axioms (
We prove that M halts iff O j= A v H. Suppose that c0 is an accepting
configuration and M halts in n steps; w.l.o.g. we assume that n > 1. Let I be a model of
O and a 2 AI a domain element. Due to axioms (
Proof Sketch. The proof is by reduction of the word problem for 1exp(n)-space bounded ATMs to entailment in ALC-ontology networks. We demonstrate that under a minor modification the construction from Theorem 7 in [7] shows that there exists a ALContology O and a concept name A such that O 6j= A v ? iff a given 1exp(n)-space bounded ATM M accepts the empty word. The ontology contains axioms with concepts of the form 9(r; C)1exp(n):D and 8r1exp(n):D. By using Lemmas 4, 8, we show that every axiom of O containing concepts of size exponential in n is expressible by an acyclic ALC-ontology network N of size polynomial in n. Then by applying Lemma 1 we obtain that there exists an acyclic ALC-ontology network N of size polynomial in n and an ontology ON such that O is (N ; ON )-expressible and thus, it holds ON j=N A v ? iff M accepts the empty word. Since AExpSpace = 2ExpTime, we obtain the required statement.
Proof Sketch. Given a 2exp(n)-space bounded ATM M and a number n > 0, we consider ontology O from the proof of Thm. 3 for M and let O0 be the ontology obtained from O by replacing every concept of the form 9(r; C)1exp(n):D and 8r1exp(n):D with 9(r; C)2exp(n):D and 8r2exp(n):D, respectively. A repetition of the proof of Thm. 3 using Lemmas 1, 6, 8 shows that there is an acyclic R-ontology network N of size polynomial in n and an ontology ON such that O0 is (N ; ON )-expressible and thus, ON j=N A v ? iff M accepts the empty word. Since A2ExpSpace = 3ExpTime, we obtain the required statement.
Proof Sketch. The theorem is proved by reduction of the N2ExpTime-hard problem of domino tiling of size 2exp(n) 2exp(n) to (non-)entailment in ALCHOIF -ontology networks. Under a minor modification the construction from Theorem 5 in [7] shows that there exists a ALCHOIF -ontology O and a concept name A such that O 6j= A v ? iff a given domino system admits a tiling of size 2exp(n) 2exp(n), for n > 0. Ontology O contains axioms with concepts of the form 9r1exp(n):C and 8r1exp(n):C. By using the same arguments as in the proof of Theorem 3 we show that there is a ALCHOIF -ontology network N of size polynomial in n and an ontology ON such that ON j=N A v ? iff the domino system does not admit a tiling.
Proof Sketch. The proof is by reduction of the N3ExpTime-hard problem of domino tiling of size 3exp(n) 3exp(n) to (non-)entailment in ROIF -ontology networks. The proof employs a modification of the ontology O from the proof of Thm. 5 which is obtained like in the proof sketch to Thm. 4. 5
As a tool for proving upper complexity bounds, we demonstrate that entailment in a network N can be reduced to entailment from (a possibly infinite) union of ‘copies’ of ontologies appearing in N . For an ontology network N , let us denote sig (N ) = ShO1; ;O2i2N (sig (O1) [ [ sig (O2)). An import path in N is a sequence p = fO0; 1; O1; : : : ; On 1; n; Ong, n 0, such that hOi 1; i; Oii 2 N for each i, with 1 i n. We denote by len(p) = n and last(p) = On the length of p and the last ontology on the path p. By paths(N ; O) we denote the set of paths that originate in O. For every symbol X 2 sig (N ) and every import path p in N , take a distinct symbol Xp of the same type (concept name, role name, or individual) not occurring in sig (N ). For each import path p in N , define a renaming p of symbols in sig (N ) inductively as follows. If len(p) = 0, we set p(X) = X for every X 2 sig (N ). Otherwise, p = p0 [ fOn 1; n; Ong for some path p0 and we define p(X) = p0 (X) if X 2 n and p(X) = Xp otherwise. A renamed import closure of an ontology O in N is defined by O~ = Sp2paths(N ;O) p(last(p)).
Lemma 11. If I j= O~ then I j=N O and for every I j=N O there exists J j= O~ such that J =sig (N ) I.
that sig ( ) sig (N ). Then O j=N iff O~ j= . an axiom such
Theorem 7 provides a method for reducing the entailment problem in ontology networks to entailment from ontologies. Note that, in general, the renamed closure O~ of an ontology O in a (cyclic) network N can be infinite (even if N and all ontologies in N are finite). There are, however, special cases when O~ is finite. For example, if all import signatures in N include all symbols in sig (N ), then it is easy to see that O~ is equivalent to the union of ontologies appearing in N . O~ is also finite if paths(N ; O) is finite, e.g., if N is acyclic. In this case, the size of O~ is at most exponential in O. If there is at most one import path between every pair of ontologies (i.e., if N is tree-shaped) then the size of O~ is the same as the size of N . This immediately gives the upper complexity bounds on deciding entailment in acyclic networks.
([co] and [N] denote possible co- and N-prefix, respectively). Let N be an acyclic ontology network and O an ontology in N such that O~ is a L-ontology. Then for L-axioms , the entailment O j=N is decidable in [co][N]TIME(f (2n)). If N is tree-shaped then deciding O j=N has the same complexity as entailment in L.
The next theorem is proved by the compactness theorem for First-Order Logic by showing that the renamed import closure of an ontology is recursively enumerable.
and O an ontology in N such that O~ is a L-ontology. Then for L-axioms , the entailment O j=N is semi-decidable. 6
We have introduced a new mechanism for ontology integration based on semantic import relations between ontologies. Reasoning over ontologies with semantic imports can be reduced to reasoning over the union of ontologies obtained as ‘copies’ of ontologies from the import closure under an injective renaming of signature symbols. We have shown that this gives an upper bound on the complexity of reasoning with acyclic semantic imports, which is one exponential harder than entailment in the underlying DLs, from E L to SROIQ. Our hardness results demonstrate that the increased complexity of reasoning is unavoidable. When cyclic imports are allowed, the complexity jumps to undecidability, even if every ontology in a combination is given in the DL E L. These complexity results are shown for situations when the imported symbols include roles. It is natural to ask whether the complexity drops when only concept names are imported. The second parameter which may influence the complexity of reasoning is the semantics which is ‘imported’. In the proposed mechanism, importing the semantics of symbols is implemented via agreement of models of ontologies. One can consider refinements of this mechanism, e.g., by carefully selecting the classes of models of ontologies which must be agreed. The third way to decrease the complexity is to restrict the language in which ontologies are formulated. We conjecture that reasoning with cyclic imports is decidable for ontologies formulated in the family of DL-Lite.
The second author acknowledges support of German Research Foundation within the Transregional Collaborative Research Center SFB/TRR 62 Companion-Technology for Cognitive Technical Systems, while working at the Institute of Artificial Intelligence, University of Ulm, and support of RSF Grant No. 17-11-01176, while working at the Institute of Informatics Systems, Novosibirsk State University.