This paper studies the extension of description logics with variables ranging over in nite domains of concept names and role names. As a preliminary work, we consider more speci cally the extension of the logic EL with variables and we investigate in this context two reasoning mechanisms, namely compliance (a kind of matching) and pattern containment. The main technical results are derived by establishing a correspondance between the EL logic and nite variable automata.
We consider description logics augmented with variables ranged over concept names and role names. As an example, consider the following description: B
P erson u 9works-f or:X u 9graduated-f rom:X (1) where the variable X takes its values from an in nite set of possible atomic concept names. B speci es the set of persons that work for the same type of organization they were graduated from. Speci cations of type (1) are called hereafter a pattern de nition and B is called a pattern name (or simply a pattern). An instanciation of a pattern is given by variable valuations. For example, if the variable X is assigned as value the atomic concept name University (respectively, eSchool ), we obtain the following description B1 (respectively, B2) which is compliant with the pattern B:
B1
B2
Variables can also be used in role places as illustrated by the following pattern de nition:
B3
The concept B3 speci es the set of persons that have a relation (i.e., any kind of role) with the same type of organization they are graduated from. Indeed, the concept B1 is compliant with B3 and it is also the case of the concept B4 de ned as follows:
B4
Our framework supports terminological cycles as illustrated below with the pattern B5 which speci es the persons that work for the same type of organization they are graduated from and have a relative who also work for the same type of organization she is graduated from.
B5
For a description logic L, we denote by LV the obtained logic augmented with concept variables and role variables. We study the following reasoning mechanisms in this framework (formal de nitions are given later in the paper): { Compliance which asks whether a description E is compliant with a pattern
C. { Pattern containment which, given two pattern de nitions C1 and C2, asks whether every description E compliant with C1 is also compliant with C2.
Indeed, the notion of a concept pattern (i.e., a concept description containing
variables) is not new and has already been used, in particular, in the context of
two non-standard reasonings, namely matching [
We expect the proposed framework to be useful in various applications. For
example, concept patterns have already been proven to be bene cial in
applications where a given user is interested `to search the knowledge base for concepts
having a certain not completely speci ed form' [
We rst recall the notion of state machines [
M is a nite alphabet, QM is a set of states with Q0M QM the set of initial states and FM QM the set of nal states, M QM M QM is a set of labeled transitions. If QM is nite then M is called a nite state machine. If q 2 Q0M is an initial state of a machine M , we say that M is rooted at q.
Let M =< M ; QM ; FM ; Q0M ; M > and M 0 =< M0 ; QM0 ; FM0 ; Q0M0 ; M0 > be two (eventually, in nite) state machines. A state q1 2 QM is simulated by a state q10 2 QM0 , noted q1 q10, i the following two conditions hold : (i) 8a 2 M and 8q2 2 QM such that (q1; a; q2) 2 M , there exists (q10; a; q20) 2 M0 such that q2 q20, and (ii) if q1 2 FM , then q10 2 FM0 . M is simulated by M 0, noted M M 0, i 8qM 2 Q0M ; 9qM00 2 Q0M0 s.t. qM qM0 .
We brie y introduce now the notion of (Guarded) Variable Automata [
In the sequel, we write (q; t; g; q0) to denote a transition from q to q0, when q0 2 ((q; t; g)). At every point in time, a run of a GVA A is determined by its instantaneous description (or simply, con guration). A con guration of a GVA A is given by a pair id = (q; ) where q 2 Q is a state in A and : X ! is a variable valuation. A valuation is extended to be the identity over the elements of . The satisfaction of a guard g by a valuation , denoted i j= g, is de ned as usual. A run of A starts at an initial con guration id0 = (q0; 0), with q0 2 Q0 an initial control state of A and 0 an arbitrary valuation of the variables of X 3. Then A moves from a con guration idi = (qi; i) to a con guration idj = (qj ; j ) over the letter i(t) if there is a transition (qi; t; g; qj ) 2 s.t. i j= g and i(x) = j (x); 8x 2 X n (qj ) (i.e., i and j coincide on the values of the variables that are not refreshed at the state qj ). Hence, given a GVA A, the runs of a A is captured by an in nite state machine called the extended machine of A and denoted E(A). Roughly speaking, E(A) is made of all the con gurations of A and all the transitions between these con gurations. Simulation between two guarded automata A and B, noted A B, is de ned as simulation between their associated state machines, i.e., A B i E(A) E(B). 3
Let NA and NR be respectively two disjoint and potentially in nite sets of atomic
concept names and role names and let L be a description logic. Let NC be an
in nite set of concept names including the atomic concept names (i.e., NA
NC ). Concept descriptions speci ed in the logic L (or L-descriptions) are built
from concept names NC and role names NR using the constructors of L. The
semantics of L-descriptions is de ned as usual. Let NCT NC and NRT NR be
respectively two nite sets of concept names and role names. An L-terminology
T over the set of concept names NCT and the set of role names NRT is a set of
concept de nitions of the form A D, where A 2 NCT is a concept name and D
is an L-description. Atomic concept names (i.e., elements of NA) are prohibited
from appearing in a left-hand side of a de nition while the the concept names
occurring of NCT n NA, called de ned concepts, must appear at the left-hand
side of a de nition. We assume that a terminology does not contain multiple
de nitions and we allow cyclic de nitions. In this paper, we study reasoning in
the context of a gfp-semantics [
Introducing variables. Let NA, NR and NC de ned as previously. For a
description logic L, we note by LV the corresponding description logic augmented
with variables. To de ne the logic LV , we extend the sets of concept names and
roles names with variables. Let Ncv and Nrv be respectively the sets of concept
and role variables. The sets Ncv, Nrv and NR [ NC are pairwise disjoints. In
the sequel, we use the letters X; Y; : : : to denote variables. An LV -terminology
is de ned over the set of concept terms NCT NC [ Ncv and role terms NRT
NR [ Nrv. Hence, LV -patterns (or simply patterns), are built from concept terms
NCT and role terms NRT using the L-constructors. Therefore, an LV -terminology
is a set of pattern de nitions of the form C D, where C 2 NCT n (NA [ Ncv) is
a concept name and D is an LV -description. We allow indeed cyclic de nitions
in LV -terminologies.
3 Note that we adopt a slight di erent vision of con gurations than [
Pattern valuation. Concept (respectively, role) variables take their values from the in nite set of atomic concept names (respectively, role names). This is captured by the notion of valuation. A variable valuation is a mapping : Ncv [ Nrv ! NA [ NR which maps concept variables into atomic concepts and role variables into role names. We denote by Val the in nite set of all such possible valuations. Valuations are straightforwardly extended to LV -patterns by considering that a valuation is the identity on elements of NC [ NR. Continuing with the example of section 1, and taking a valuation 1 such that 1(X) = U niversity, 1(Y ) = works-f or and 1(Z) = U niversity we obtain 1(B) B1 and 1(B3) B1. If we consider now a valuation 2 such that 2(X) = 2(Z) = eSchool and 2(Y ) = evaluates we obtain 2(B) B2 and 2(B3) B4. Hence, for an LV -pattern C, (C) is an L-description. As a consequence, an LV -pattern C describes a (potentially in nite) set of L-descriptions (corresponding to the potentially in nite number of possible valuations). We extend the notion of valuation to LV -teminologies as follows: given an LV terminology T and a variable valuation , we denote by (T ) the terminology made of the de nitions of the form A (D) such that A D is a pattern de nition in T . Therefore, an LV -terminology T speci es an (in nite) set of L-terminologies (T ); 8 2 Val.
Variants of variable semantics. Several possibilities exist to de ne the
semantics of variables depending on the restrictions imposed on variable valuations.
We borrow the notion of non-deterministic reassignment of variables from
variable automata semantics [
Hence, the valuation of a LV -pattern C is provided by a (potentially in nite) sequence of valuations 0; : : : ; n, where 0 is the initial valuation and where each valuation i+1 coincides with the valuation i on the non refreshed variables (i.e., i(X0) = i+1(X)0 if X0 is not refreshed) while i+1 assigns new values to the refreshed variables.
We use the following notation to distinguish between these two classes of semantics: r-semantics denotes refreshing variables semantics (valuations Valr) while nr-semantics denotes non refreshing variables semantics (valuations Valnr). Let t 2 fr; nrg and C be an LV -pattern. We denote by Dt(C)= f (C) j 8 2 Valt g the in nite set of L-descriptions obtained from the pattern C by the valuations of Valt.
Reasoning in description logics with variables. Let T and T 0 two LV terminologies. We say that T and T 0 are coherent if NCT \ NCT 0 = ;.
Let t 2 fr; nrg. Let C and D be two LV -patterns of an LV -terminology T 0 and let E be an L-description of an L-termonilogy T 00 coherent with T 0. Let T = T 0 [ T 00. In this paper we are interested by the following reasonings. { E is compliant with C w.r.t. a t-semantics, noted E 6tT C, i there exists a valuation 2 Valt such that E v (T ) (C) (i.e., E is subsumed by (C) w.r.t. the terminology (T )). { C is contained in D w.r.t. a t-semantics, noted C tT 0 D, i for every Ldescription E of an L-termonilogy T 00, we have E 6tT C implies E 6tT D (i.e., every description E which is compliant with C w.r.t. a t-semantics is also compiant with D w.r.t. a t-semantics), 4
The case of the logic E LV
In this paper, we study reasoning in the context of a gfp-semantics while we
believe that our framework can be extended to descriptive and lfp-semantics as
well. We are interested by classes of description logics in which reasoning w.r.t. a
gfp-semantics can be characterized using a nite state machine (e.g., automata
or graphs ([
We provide below a characterization of compliance and pattern containment,
w.r.t. a gfp-semantics, in E LV . We explain brie y how to turn any E LV -pattern
t . To achieve this task, we adapt the
de nition C into a variable automata AC
E L-normal form proposed in [
V1 u : : : u Vm u 9W1:D1 u : : : u 9Wn:Dn
for m; n 0 and each Vi is either an atomic concept name or a concept variable
(i.e., Vi 2 NA [ Ncv, for i 2 [1; m]), and Dj is a de ned concept name (i.e.,
Dj 2 NCT n (NA [ Ncv), for j 2 [1; n] and each Wi is a role term (i.e., Ri 2 NRT
(Ri). A pattern terminology T is said normalized if all the pattern de nitions it
contains are in a normal form. W.o.l.g., we assume that two pattern de nitions
in a normalized terminology use disjoint sets of variables. It is worth noting
that, since concept variables do not range over de ned concept names, the
normalization process proposed in [
B B1 B2 B4 B5 D1 D2 D3 D4
X U niversity eSchool X0
Mapping ELV -patterns into variable automata. Let T be a normalized ELV terminology. We explain below how to map de ned concepts and patterns of T into variable automata. Let QT = NCT n (NA [ Ncv) be a set of states made of the de ned concepts of T . Each concept de nition or ELV -pattern C V1 u : : : u Vm u 9W1:D1 u : : : u 9Wn:Dn of T is turned into a variable automaton AtC = ( C ; XC ; QC ; Q0; ; F; ) de ned as follows: { the alphabet C NA [ NR [ fT opg, is made of a subset of atomic concept names, role names and the T op concept, { the set of variables XC Ncv [ Nrv, is made of a subset of concept and role variables, { the set of states QC QT [ fC; Sf g, is made of the states of QT reacheable from the state C, { Q0 = fCg is the set of initial states of the automaton and F = fSf g is its set of nal states, { the transitions are unguarded (i.e., G = ;). The transition function is de ned as follows: (q; T op; true; Sf ) 2 , 8q 2 QC , i.e., there is an edge labeled T op from every node q in QC to the nal state Sf , (C; Vi; true; Sf ) 2 , 8i 2 [1; m], i.e., each term Vi is turned into an edge, labeled Vi, from the node C to the nal state Sf . (C; Wi; true; Di) 2 , 8i 2 [1; n], i.e., each term 9Wi:Di is turned into an edge, labeled Wi, from the node C to the node Di. { the refreshing function is de ned as follows: if t = r then (x) = QC ; 8x 2 X if t = nr then (x) = ;; 8x 2 X The proposed mapping of a pattern C V1 u : : : u Vm u 9W1:D1 u : : : u 9Wn:Dn into an automaton AtC = ( C ; XC ; QC ; Q0; ; F; ) is depicted at gure 1(a) while the gure 1(b) shows the variable automaton AtB5 corresponding to the pattern B5 of section 1. Figure 2(a) shows E(ArB5 ), the extended automaton of ArB5 , for the case of a variable refreshing semantics (i.e. t = r). Note that, this machine includes an in nite set of initial states (i.e., the con gurations (B5; i), 8 i 2 Valr). In the case of a refreshing semantics, the cyclic role hasrelative relates a given state (B5; i) to all the other possible states (B5; j ), 8 j 2 Valr, thereby making each machine rooted at an initial con guration (B5; i) an in nite state machine. In the case of a non-refreshing semantics (i.e. t = nr), E(AnBr5 ) is made of an in nite set of, pairwise disconnected, nite state machines rooted at (B5; i), 8 i 2 Valnr (c.f., gure 2(b)). The following lemma establishes a connection between subsumption in E LV and simulation between instances of variable automata.
Lemma 1. Let t 2 fr; nrg and let C and D be two E L(VA-ptDa)tterns in a E LV
terminology T . Let Valt, then (C) v (T ) (D) i (AtC ).
Let T be an E L-terminology T . This lemma is derived from the observation
that the set of all the automata E(AtC ), of the patterns C of T , corresponds
to a slight modi cation of the notion of E L-description graph [
Therefore reasoning over C can be reduced to reasoning over the corresponding variable automata AtC . However, despite the correspondance established by lemma 1, reduction of compliance and containment to simulation between variable automata is not straightforward and requires additional transformations. Consider for example the following pattern de nitions in a terminology T = fE 9r1:D3; A 9X:D1 u 9Y:D2; Di T op; for i 2 f1; 2; 3gg. The corresponding automata AtE and AtA are depicted at gure 3(a). It is easy to check that E is compliant with A w.r.t. any t-semantics. Indeed, for any valuation which satisfy (X) = (Y ) = r1, we have (AtA) AtE and hence E v (T ) (A) (which implies that E is compliant with A). However, we have clearly AtA 6 AtE . As a witness of non simulation take any valuation 0 which satisfy 0(X) 6= r1 or 0(Y ) 6= r1, and in this case we have At 0(A) 6 At 0(E) (which implies that AtA 6 AtE ). Despite this fact, it is still possible to reduce compliance to simulation after a transformation of the automata AtA and AtE into two new automata, denoted AtA and AtE (c.f., gure 3(b)). The main intuition underlying the proposed transformation is to construct new automata that satisfy the following property: AtA AtE i 9 2 Valt s.t. (AtA) AtE : In the similar way, additional transformations are needed to reduce containment to simulation as stated in the following theorem.
Theorem 1. Let T 0 be an E LV -terminology and C and D two E LV -patterns in T and let E be a de nition in and E L-terminology T 00 coherent with T 0. Let T = T 0 [ T 00. Then there exists guarded variable automata A^tC ; A~tD; AtE and AtC such that: (i) E 6tT C i AtC AtE , and (ii) C tT D i A~tD A^tC .
The proof of this theorem is given in the extended version of this paper
[
Based on the previous theorem, we can provide the following result w.r.t. the considered reasoning in E LV .
Theorem 2. Let t 2 fr; nrg. Then: (i) Compliance in E LV w.r.t. a t-semantics is NP-complete, (ii) Pattern containment in E LV w.r.t.a t-semantics is in 2-Exptime.
Consider rst the case (i). We recall that, E is compliant with C w.r.t. a tE-sevma(Tn)tics(,Cn)o.tWede Ekno6wtT frCo m,ioutrhceorensetrxuiscttsioan vthalautaEtio6ntT C2 isVeaqltuisvuaclehntthtaot: 9 s.t (AtC ) AtE .
The Compliance problem is in NP : given an oracle which guess a valuation , then it is possible to check in polynomial time if (AtC ) AtE .
The NP-hardness is proved by a reduction from graph 3-colorability problem
[
Construction of the terminology T 0. For each color c 2 fb; r; gg, we include in T 0 a concept de nition Ec as follows: { Eb { Er { Eg { ET op 9b:ET op 9r:ET op 9g:ET op
T op
9b:Er u 9g:Er. 9r:Eb u9g:Eb u9r:Eg u9b:Eg u Construction of the E LV -terminology T 00. Given a graph G = (V; E) with V = fn1; : : : ; nmg, we include in T 00 the following set of E LV -patterns: { fNi { NT op 9Xi:NT op j f or i 2 [1; m]g and
T op
d 9Xi:Nj .
(ni;nj)2E
Let T = T 0 [ T 00. It is then easy to check that G is 3-colorable i Ecolor 6tT
Complexity of pattern containment (case (ii)) is obtained from theorem 1
which reduces an E LV -pattern containment test C tT D into a simulation test
A~tD A^tC between two GVA. The automaton A^tC is exponential in the size of
C and D. Hence, knowing from [
This paper addresses the problems of pattern compliance and containment for description logics with variables. It considers a framework that cater for cyclic terminologies and de nes two semantics of variables which di er w.r.t. to the possibility or not to refresh the variables. The paper provides preliminary results regarding the description logic E LV , obtained from an extension of E L with variables. Future research work will be devoted to the extension of the approach to more expressive logics.