Description logics (DLs) of context can be employed to represent and reason about contextualized knowledge, which naturally occurs in practice [5,4,7,9,8]. Consider, for instance, the rôles played by a person in different contexts. The person Bob, who works for the company Siemens, plays the rôle of an employee of Siemens in the work context, whereas he might play the rôle of a customer of Siemens in the context of private life. Here, access restrictions to the data of Siemens might critically depend on Bob's rôle. Moreover, DLs capable of representing contexts are vital to integrate distributed knowledge as argued in [5,4]. DLs are well-suited to describe contexts as formal objects with formal properties that are organized in relational structures, which are fundamental requirements for modeling contexts [11,12]. However, classical DLs lack expressive power to formalize that some individuals satisfy certain concepts and relate to other individuals depending on a specific context. Therefore, often two-dimensional DLs are employed [7,9,8]: One DL LM (the meta or outer logic) is used to represent the contexts and their relationships to each other. LM is combined with a DL LO (the object or inner logic) that captures the relational structure within each context. Moreover, while some pieces of information depend on the context, other pieces of information are shared throughout all contexts. For instance, a person's name is typically independent of the actual context. To be able to express that, some concepts and roles a designated to be rigid, i.e. they are required to be interpreted the same in all contexts. Unfortunately, if rigid roles are admitted, reasoning in contextualized DLs is usually undecidable [7]. We propose and investigate a family of two-dimensional DLs LM JLOK that meet the above requirements, but are a restricted form of the one defined in [7] in the sense that we limit the interaction of LM and LO. More precisely, in our family of contextualized DLs the outer DL can refer to the internal structure of each context, but not vice versa. This represents contexts in a top-down perspective. Interestingly, reasoning in LM JLOK stays decidable with such a restriction, even in the presence of rigid roles. In some sense our family of contextualized DLs are similar to temporalized DLs investigated in [2,3,10]. For providing better intuition on how our formalism works, we examine the above mentioned example a bit further. Consider the following axioms: > v J9 worksFor :fSiemensg v 9 hasAccessRights :fSiemensgK Work v JworksFor (Bob; Siemens)K > v J9 isCustomerOf :> v HasMoney K
(
Bob,
worksFor
SSN hasSSN hasAccessRights hasCEO . . .
Private Bob,
:Work v J9 worksFor :> v ?K
(
Our family LM JLOK consists of combinations of two DLs, where we focus on the cases where LM and LO are EL or DLs between ALC and SHOQ. Let OC, OR, and OI be respectively sets of concept, role, and individual names for the object logic LO. Analogously, we define the sets MC, MR, and MI for the meta logic LM . Let O = (OC; OR; OI) and M = (MC; MR; MI). Concepts, GCIs and assertions are defined over the respective signatures O and M as usual [1]. Definition 1. Concepts of the object logic (o-concepts) are LO-concepts over O; o-axioms are LO-axioms over O. Concepts of the meta logic (m-concepts) are defined inductively: each LM -concept over M is an m-concept, and J K is an m-concept for an o-axiom ; and m-axioms are defined analogously. Boolean LM JLOKknowledge bases (LM JLOK-BKBs) are Boolean combinations of m-axioms. Note that the syntax of the object level is precisely the one of LO, whereas the syntax of the meta level also allows to put LO-axioms in place of concept names. The semantics of LM JLOK is defined using nested interpretations, which consist of O-interpretations (usual DL interpretations for the names in O) for the
LO LM EL ALC SHOQ specific contexts and the relational structure between them (M-interpretation), where all contexts have the same domain. Also, let OCrig OC denote the set of rigid concepts, and let ORrig OR denote the set of rigid roles. Moreover, we assume that individuals of LO are always interpreted the same in all contexts. Definition 2. We call a tuple J = (C; J ; ; ( Ic )c2C) a nested interpretation, where C is a non-empty set (called contexts) and (C; J ) is an M-interpretation. Moreover, Ic := ( ; Ic ) is an O-interpretation for every c 2 C, such that it holds for all c; c0 2 C that xIc = xIc0 for all x 2 OI [ OCrig [ ORrig.
Definition 3. Let J = (C; J ; ; ( Ic )c2C) be a nested interpretation. The mapping J is extended as follows: J KJ := fc 2 C j Ic j= g. Moreover, J is a model of the m-axiom if (C; J ) is a model of . This is extended to LM JLOKBKBs inductively as usual. We write J j= B if J is a model of the LM JLOKBKB B. We call B consistent if it has a model.
The complexity of consistency in LM JLOK is listed in Table 1. The lower bounds are obtained using the ideas of [2,3] and hold already for the fragment ELJALCK, even if only conjunctions of m-axioms are considered instead of BKBs. Without rigid names, Exp-hardness follows from the complexity of LO. If rigid concept and role names are allowed, we reduce the word problem for exponentially spacebounded alternating Turing machines to obtain 2Exp-hardness. If only rigid concept names are allowed, a reduction of an exponentially bounded version of the domino problem yields NExp-hardness. For the upper bounds, we proceed similar to what was done for ALC-LTL in [2,3] and reduce the consistency problem to two separate decision problems. First, we abstract our LM JLOK-BKB B by replacing the m-concepts that consist of o-axioms by fresh concept names and test this abstraction B0 for consistency. With this abstraction, we loose, however, the information on the o-axioms. In each model of B0, the fresh concept names have some extensions, and are treated completely independently. The induced o-axioms, however, may not be independent. It could be that some o-axioms are inconsistent together. We check this in a separate step.
To conclude, we have proposed novel combinations of two DLs for representing contextual knowledge and analyzed their complexity. Interestingly, even in the presence of rigid roles the consistency problem is still decidable. For more details, see [6]. As future work apart from others, we envision that our decision procedures can be adapted to deal with temporalized context DLs such as LT LJALCJALCKK.