Two-Dimensional Description Logics of Context

Abstract

We introduce an extension of Description Logics (DLs) for representing and reasoning about contextualized knowledge. Our formalism is inspired by McCarthy's theory of formalizing contexts and based on two-dimensional semantics, with one dimension representing a usual object domain and the other a domain of contexts. Additionally, it is equipped with a second DL language for describing the context domain. As a result, we obtain a family of two-sorted, two-dimensional combinations of pairs of DLs.

Introduction

Description Logics (DLs) provide a clear and broadly accepted paradigm for reasoning about terminological knowledge. Under the standard Kripkean semantics, a DL ontology forces a unique, global view on the represented world, in which the ontology axioms are interpreted as universally true. This philosophy is wellsuited as long as everyone can share the same conceptual perspective on the domain or there is no need for considering alternative viewpoints. Alas, this is hardly ever the case since a domain can be modeled di erently depending on the intended use of an ontology. Consequently, e ective representation and reasoning about knowledge pertaining to such multiple, heterogenous viewpoints becomes the primary objective for many practical applications [ 1,2 ].

The challenges above resemble clearly those problems that originally inspired J. McCarthy to introduce a theory of formalizing contexts in knowledge representation systems, as a way of granting them more generality [ 3,4 ]. The gist of his proposal is to replace logical formulas ', as the basic knowledge carriers, with assertions ist (c; ') stating that ' is true in c, where c denotes an abstract rstorder entity called a context, which on its own can be described in a rst-order language. For instance:

ist(c; Heart (a)) ^ HumanAnatomy (c) states that the object a is a heart in some context described as HumanAnatomy . Based on this foundation, the theory advocates complex models of knowledge which are able to properly account for the local, context-speci c scope of the represented knowledge, while at the same time provide an expressive apparatus for modeling semantic interoperability of contexts, i.e. generic rules guiding the information ow between di erent contexts.

The importance of contextualized knowledge in DLs has been generally acknowledged, nevertheless the framework is still not supported with a dedicated theory of handling context-dependent information. In this direction, the most commonly considered perspectives are restricted to global integration of local ontologies [ 5,6 ] or modeling levels of abstraction as subsets of models of a DL ontology [ 7,8 ]. The purpose of this paper is to introduce a novel extension of DLs for reasoning with contextualized knowledge. Our proposal is systematically derived from two formal roots. On the one hand, by resorting to McCarthy's theory we ground our approach in a longstanding tradition of formalizing contexts in AI. On the other, we build on top of two-dimensional DLs [ 9 ], which provide us with well-understood formal foundations. In particular, we extend the standard DL semantics with a second modal dimension, representing a possibly in nite domain of contexts. Additionally, our logics are equipped with a second DL language for describing the context domain. This way we obtain a family of two-sorted, two-dimensional combinations of pairs of DLs for reasoning about contextualized knowledge.

This paper is the workshop version of [ 10 ] and [ 11 ]. It extends the work presented there by discussing thoroughly the motivation underlying the formal design of the introduced DLs of contexts. We also review a number of expressive fragments of these logics and report the corresponding complexity results obtained and proven in the two papers. 2

Overview and formal motivation

Since its introduction, McCarthy's theory of formalizing contexts has inspired a signi cant body of work in AI studying implementations of the approach in a variety of formalisms and applications [ 12,13,14,4,1,15 ]. The great appeal of this theory stems from the simplicity of the three major postulates it is based on: 1. Contexts are formal objects. More precisely, a context is anything that can be denoted by a rst-order term and used meaningfully in a statement of the form ist (c; '), saying that formula ' is true (ist ) in context c [ 3,4,12 ]. 2. Contexts have properties and can be described. As rst-order objects, contexts can be in a natural way described in a rst-order language [ 14,4 ]. This allows for addressing them generically through quanti ed formulas such as 8x(C (x) ! ist (x; ')), expressing that ' is true in every context of type C . 3. Contexts are organized in relational structures. In the commonsense reasoning, contextual assumptions are dynamically and directionally altered [ 15,12 ], thus contexts are often accessed from other contexts. Formally, this can be captured by allowing nestings of the form ist (c; ist (d ; ')).

The logics proposed in this paper originate as an attempt of adopting these principles in the framework of DLs. In the following paragraphs we discuss the central design choices we made and the motivation behind them. We start from the basic semantic considerations on contexts and further trace their impact on the selection of speci c logical languages.

The key to importing McCarthy's theory into a knowledge representation framework is a faithful interpretation of his three postulates on the modeltheoretic grounds of the framework. By doing so within the DL paradigm, we e ectively commit ourselves to a speci c sort of semantic structures that must be taken into account in order to express and interpret contextualized knowledge adequately. Figure 1 illustrates one such structure | a formal model of some application domain supporting multiple contexts of representation. As an intuitive example, consider here a formal description of a society of interconnected agents, each one sustaining his own viewpoint and focus on the represented world.

The model has two apparent levels. The context-level consists of context entities (postulate 1), which are possibly interlinked with accessibility relations (postulate 3) and described in a language containing individual names, concepts and relation names (postulate 2). For instance, context c is of type D and is related to d through the relation t . Intuitively, each context in the model can be seen as a box carrying a piece of the object-level representation. Clearly, instead of a unique global model of the object domain, we associate a single local model with every context. Naturally, these models might obviously di er from each other as each of them re ects a speci c viewpoint on the object domain. Moreover, they might not necessarily cover the same fragment and aspects of the application domain and not necessarily use the same fragment of the object language for describing it. For instance, objects a and b occur at the same time in contexts c; d ; e, but in each of them they are described di erently and remain in di erent relations to other objects.

The central insight emerging from this short analysis is that the semantic structures comprising the model theory of a reasonably expressive DL of context are inherently two-dimensional, with one dimension consisting of (domain) objects and the second | contexts.

context language model

object language models c

Once we have identi ed the main characteristics of the intended semantic structures, the next step is to nd convenient languages for speaking about them, and constraining their possible properties. By the assumption taken in this work, DLs are suitable formalisms for representing the object-level knowledge. The key challenge is then to extend them with additional syntactic means that would facilitate accommodating the context-level information. A rst crucial observation in this direction is that contexts and their relations, as pictured above, correspond to Kripke frames, with possible worlds interpreted as context entities. It is commonly known that such frames can be combined in a productlike fashion with the standard DL interpretations, giving rise to two-dimensional semantics for DLs with additional modal operators [ 16 ]. These operators are typically intended for modeling the evolution of the object knowledge across the states of the second dimension, for instance time points, as in temporal DLs [ 17 ]. Although this approach seems in general very encouraging, the caveat is that it does not o er a direct methodology for describing the elements of the second dimension. More precisely, we can easily augment a DL language with modal `contextualization' operators 3; 2 for traversing the context dimension of the models and quantifying over implicit context objects, but it is not clear how to explicitly assert properties of the accessed contexts | an essential point for obtaining a ne-grained contextualization machinery.

As a solution, we employ a second DL language for describing the context dimension. Thus, we obtain a two-sorted language with each sort interpreted over the respective dimension. The two languages are suitably integrated on the syntactic and semantic level, so that their models can be eventually combined as presented in Figure 2. The style of combination remains fully compatible with that underlying two-dimensional DLs described above. In fact, we are able to show that, depending on the choice of the integration mechanism, our logics are proper extensions of the well-known (Kn)L or S5L [ 16 ].

In the following sections, we rst recap the basic DL nomenclature, next we formally de ne the syntax and semantics of the proposed DLs of context and give an overview of their expressiveness{complexity characterization. Finally, we consider intended application scenarios for the framework. 3

Description Logics of Context

A DL language L is speci ed by a vocabulary = (NC ; NR; NI ), where NC is a set of concept names, NR a set of role names and NI a set of individual names, and a number of constructors for composing complex expressions. In this paper, we focus on the well-known DLs E L; ALC and ALCO [ 18,19 ] and assume the reader is familiar with those formalism and the basic notions concerning DLs.

A Description Logic of Context CLLCO consists of a DL context language LC , supporting context descriptions, and an object language LO equipped with context operators for representing object knowledge relative to contexts. We introduce two families of such DLs, characterized by di erent types of context operators.

De nition 1 (CLLCO -context language). The context language of CLC is a DL LO language LC over the vocabulary = (MC ; MR; MI ), with a designated subset MI? MI .

The set MI? contains context names. Following some common-sense intuitions, we consider contexts only as a subset of the domain of the context language. Indeed, certain elements of this domain might carry no object knowledge at all, and instead, serve only as individuals referred to in context descriptions (cf. Figure 1). This is often the case in applications concerned with provenance of knowledge [ 2 ]. For instance, a context c, associated with a single knowledge source, might be there described with an axiom hasAuthor (c; henry ), where henry is an individual related to c, but obviously not a context per se. De nition 2 (CLLCO -object language). Let LO be a DL language over the vocabulary = (NC ; NR; NI ). The object language of CLLCO is the smallest language containing LO and closed under the constructors of LO and one of the two types | F1 resp. F2 | of concept-forming operators: hr:Ci D j [r:C] D hCiD j [C]D (F1) (F2) where C and r are a concept and a role of the context language and D is a concept of the object language.

Intuitively, the concept hr :C iD denotes all objects which are D in some context of type C accessible from the current one through r . Similarly, [r :C ]D denotes all objects which are D in every such context. In the case of the operators in F2, the concept hC iD denotes all objects which are D in some context of type C , whereas [C ]D | all objects which are D in every such context. For example, hneighbor :Country iCitizen, refers to the concept Citizen in some context of type Country accessible through the neighbor relation from the current context. Analogically, hHumanAnatomy iHeart refers to the concept Heart in some context of HumanAnatomy .

De nition 3 (CLLCO -knowledge base). A CLLCO -knowledge base (CKB) is a pair K = (C; O), where C is a set of axioms of the context language in any of the forms (y), and O is a set of formulas of the form:

c : ' j C : ' where ' is an axiom of the object language (a GCI or a concept/role assertion), c 2 MI? and C is a concept of the context language.

A formula c : ' states that the axiom ' holds in the context denoted by the name c. Note that this corresponds directly to McCarthy's ist (c; '). Axioms of the form C : ' assert the truth of ' in all contexts of type C . For example, the formula Country : hneighbor :Country iCitizen v NoVisaRequirement states that in every country, the citizens of its neighbor countries do not require visas.

The semantics is given through CLC -interpretations and CLC -models, which

LO LO combine the interpretations of LC with those of LO. We assume the semantics of E L; ALC and ALCO to be de ned in the standard way[ 18,19 ]. As explained before, the (possibly in nite) domain of contexts C is subsumed by the entire interpretation domain of the context language . For technical reasons, we assume a constant object domain for all contexts. This assumption, though often impractical, grants greater generality to the complexity results and can be easily relaxed to the varying domain case. (De; Cn; iJti;on; 4f I((Ci)LLCO -interpretations). A CLLCO -interpretation is a tuple M = gi2C), where: 1. ( ; J ) is an interpretation of the context language, where is a non-empty domain of individuals and J an interpretation function, where: { C is a non-empty domain of contexts, { cJ 2 C, for every c 2 MI?, 2. ( ; I(i)), for every i 2 C, is an interpretation of the object language, where is a non-empty object domain and I(i) an interpretation function of LO, such that: (F1) for every hr:CiD and [r:C]D: (hr:C i D)I(i) = fx j 9j 2 C : (i; j) 2 rJ ^ j 2 CJ ^ x 2 DI(j)g; ([r:C ] D)I(i) = fx j 8j 2 C : (i; j) 2 rJ ^ j 2 CJ ! x 2 DI(j)g: (F2) for every hCiD and [C]D: (hC iD)I(i) = fx j 9j 2 C : j 2 CJ ^ x 2 DI(j)g; ([C ]D)I(i) = fx j 8j 2 C : j 2 CJ ! x 2 DI(j)g:

Clearly, the di erence between the context operators of type F1 and F2 lies in the choice of the relational structures involved in quantifying over the context domain. F1-operators bind contexts only along the roles of the context language (similarly to K-modalities), while F2-operators ignore these relationships and rest upon the universal relation over C (similarly to S5-modalities). This is reected in the scope and the character of the distribution of the object knowledge over contexts in CLC -models. For instance, in Figure 1, the concept ht :F iB is

LO satis ed by object a only in context c, while hF iB is satis ed by a in all contexts in the model. From the perspective of McCarthy's theory, employing operators F2, rather than F1, is equivalent to scarifying postulate (3). This means that every two contexts in the model become in principle accessible to each other. De nition 5 (CLLCO -models). f I(i)gi2C) is a model of a CKB K = (C; O) i :

A

CLLCO -interpretation

M = ( ; C; J ; ; { for every ' 2 C, ( ; J ) satis es ', { for every c : ' 2 O, ( ; I(cJ )) satis es ', { for every C : ' 2 O and i 2 C, if i 2 CJ then ( ; I(i)) satis es '.

As hinted before, there is a close connection between our DLs of context and the modal DLs (Kn)L and S5L. In particular, the former are proper extensions of (Kn)L resp. S5L. This relationship is formally established in Theorem 1. Theorem 1. If MI = MC = ; then CLLCO with context operators (only) of type F1 resp. F2 is a notational variant of (Kn)LO resp. S5LO with global axioms. Proof sketch. Observe that all formulas are of the form > : '. First, replace every hr :>i with 3r and [r :>] with 2r , resp. every h>i with 3 and [>] with 2. Next, replace every > : ' 2 O with '. It is easy to see that the semantics of CLLCO coincides with that of (Kn)LO resp. S5LO . Note that an axiom is global i it is satis ed in all possible Kn-worlds resp. S5-worlds. q

As our main technical contributions in [ 10 ] and [ 11 ], we obtained a wide panorama of complexity results for reasoning in DLs of context using particular combinations of DLs for LC and LO, and di erent types of context operators. We summarize these results in Table 1, and shortly elaborate on them below. context operators type F1 type F2

E L ALC

ALCO HLOHHHLHC E L ALC; ALCO ALC; ALCO 2ExpTime-complete 2ExpTime-complete

PTime ExpTime-hard ExpTime-complete NExpTime-complete

NExpTime-complete NExpTime-complete

The results reveal that the computational properties of the proposed logics are predominantly a ected by the choice of the context operators. More precisely, reasoning in CLC with F1-operators is harder than with F2-operators. This be

LO havior can be explained by the fact that such di erence in the complexity is essentially present already between the underlying logics (Kn)L and S5L [ 10,20 ].

In the case of DLs of context with F1-operators, we rst established the 2ExpTime lower bound for the satis ability problem for (Kn)ALC w.r.t. to global TBoxes and only local roles. The proof is a reduction of the word problem for an exponentially bounded, alternating Turing machine. This result turned out to be quite surprising since it could be expected that without rigid roles the satis ability problem can be straightforwardly reduced to satis ability in fusion models. This in turn would have to yield an ExpTime upper bound by means of the standard techniques. However, as the following example for (Kn)ALC demonstrates, this strategy fails.

(y) 3iC u 9r:2i?

(z) 9succi:C u 9r:8succi:? Although (y) clearly does not have a model, its reduction (z) to a fusion language, where modal operators are translated to restrictions on fresh ALC roles, is satis able. The reason is that while in the former case the information about the structure of the K-frame is global for all individuals, in the latter it becomes local. The r-successor in (z) is simply not `aware' that it should actually have a succi-successor. The matching 2ExpTime upper bound is proven by using the quasistate elimination technique, similar to the proofs for certain products of modal logics [ 9 ].

Regarding DLs of context with F2-operators, for LO 2 fALC; ALCOg and LC 2 fALC; ALCOg, we encounter a jump from ExpTime to NExpTimecompleteness. The non-determinism involved can be interpreted by the need of guessing the interpretation of the context language rst, before nding the model of the object component of the combination. In particular, the lower bound is obtained by an encoding of the 2n 2n tiling problem, known to be NExpTime-complete [ 9 ]. In the case of LO = ALCO and LC = E L this jump can be explained by the interaction of nominals and the context operators, in fact this enables to encode the 2n 2n tiling problem, as in the previous cases. For the upper bounds for LO 2 fALC; ALCOg we devise a variant of a type elimination algorithm, whereas for LO = E L a completion algorithm in the style of [ 21 ].

Application scenarios

There are two natural application scenarios for the DLs of context. First, they can be used as native representation languages dedicated to modeling and reasoning about knowledge of inherently contextualized nature. Alternatively, the framework can be used to support an external `integration' layer over standard DL ontologies. Observe, that a collection of DL ontologies O1; : : : ; On in some language LO can be seen as a set of formulas O = fci : ' j ' 2 Oi; i 2 (1; n)g in CLC , where every ontology corresponds to a unique context name. Consequently,

LO the extra expressive power of CLLCO can be utilized for imposing interoperability constraints over those ontologies. Arguably, the rst type of use might be of interest for knowledge-intensive/expert applications, while the second one seems appealing from the perspective of integrating information on the Semantic Web. We support the two cases with small examples, based on di erent types of context operators, and explain some possible inferences.

Contextualized knowledge base. Consider a simple representation of knowledge about the legal status of people, contextualized with respect to geographic locations. We de ne a CKB K = (C; O), consisting of the context (geographic) ontology C and the object (people) ontology O, as follows:

C : O :

Country (germany ) (1) neighbor (france ; germany ) (2) germany : 9hasParent :Citizen(john) (3) Country : 9hasParent :Citizen v Citizen (4) france : hneighbor :Country iCitizen v NoVisaRequirement (5) Visibly, france and germany play here the role of contexts, described in the context language by axioms (1) and (2). In the context of germany , it is known that john has a parent who is a citizen (3). Since in every Country context | thus including germany | the concept 9hasParent :Citizen is subsumed by Citizen (4), therefore it must be true that john is an instance of Citizen in germany . Finally, since germany is related to france via the role neighbor , it follows that john (assuming rigid interpretation of this name across contexts) has to be an instance of NoVisaRequirement in the context of france (5). A sample CLLCO -model of K is depicted in Figure 3.

j NoVisaRequirement

NoVisaRequirement france neighbor j Citizen Country hasParent

Citizen germany (*) j = john

Fig. 3. A CLLCO -model of the CKB K.

Interoperability constraints over DL ontologies. Consider an architecture such as the NCBO BioPortal project3, which gathers numerous published biohealth ontologies, and categorizes them via thematic tags, e.g.: Cell , Health , Anatomy , etc., organized in a meta-ontology. The intention of the project is to facilitate the reuse of the collected resources in new applications. Note, that the division between the context and the object language is already present in the architecture of the BioPortal, which can be immediately utilized to state, e.g.: C : O :

HumanAnatomy v Anatomy (1) > : hHumanAnatomy iHeart v [Anatomy ]HumanHeart (2) Anatomy : Heart v Organ (3) where (2) maps the concept Heart from any HumanAnatomy ontology to the concept HumanHeart in every Anatomy ontology; (3) imposes the axiom Heart v Organ of an upper anatomy ontology over all Anatomy ontologies, which due to axiom (1) carries over to all HumanAnatomy ontologies.

In general, CLLCO provides logic-based explications of some interesting notions, relevant to the problem of semantic interoperability of ontologies, such as: concept alignment: > : hAiC v [B ]D every instance of C in any ontology of type A is D in every ontology of type B semantic importing: c : hAiC v D every instance of C in any ontology of type A is D in ontology c upper ontology axiom: A : C v D axiom C v D holds in every ontology of type A 5

Conclusions

The problems of 1) representing inherently contextualized knowledge within the paradigm of DLs and 2) reasoning with multiple heterogenous, but semantically interoperating DL ontologies, are both interesting and important issues, motivated by numerous practical application scenarios. It is our belief that these two challenges are in fact two sides of the same coin and, consequently, they should be approached within the same, unifying formal framework. In this paper, we have proposed two novel families of two-dimensional DLs of context. Arguably, these logics achieve the objective declared above to a great extent, by providing su cient syntactic and semantic means to support both functionalities, seamlessly integrated within one formalism.

As our results show, such two-dimensional extension of the DL framework does not necessarily entail an increase in the computational complexity of reasoning, as for e.g. CEL and CEL

EL ALC with F2-operators, nor does it a ect the generally adopted knowledge representation methodology of DLs. We therefore consider the approach a worthwhile subject to further research. In particular, it is essential to investigate how certain notions and problems central to the practical use and maintenance of multi-context knowledge systems (e.g. handling local inconsistencies) can be meaningfully restated within the presented framework. 3 See http://bioportal.bioontology.org/.

Acknowledgements We want to thank Carsten Lutz and Stefan Schlobach for many helpful discussions and suggestions on the ideas presented in this paper. We are also grateful to the reviewers of this work for their useful feedback.

References

1. Guha , R. , McCool , R. , Fikes , R.: Contexts for the semantic web . In: Proc. of ISWC-04 . ( 2004 ) 32 { 46

2. Bao , J. , Tao , J. , McGuinness , D.L. , Smart , P. : Context representation for the semantic web . Proc. of Web Science Conference ( 2010 )

3. McCarthy , J.: Generality in arti cial intelligence . Communications of the ACM 30 ( 1987 ) 1030 { 1035

4. Guha , R.: Contexts: a formalization and some applications . PhD thesis , Stanford University ( 1991 )

5. Borgida , A. , Sera ni , L.: Distributed description logics: Assimilating information from peer sources . Journal of Data Semantics 1 ( 2003 ) 2003

6. Cuenca Grau , B. , Kutz , O. : Modular ontology languages revisited . In: Proc. of the Workshop on Sem. Web for Collaborative Know. Acquisition . ( 2007 )

7. Goczyla , K. , Waloszek , W. , Waloszek , A. : Contextualization of a DL knowledge base . In: Proc. of DL-07 . ( 2007 )

8. Grossi , D. : Desigining Invisible Handcu s. Formal Investigations in Institutions and Org. for Multi-Agent Systems . PhD thesis , Utrecht University ( 2007 )

9. Kurucz , A. , Wolter , F. , Zakharyaschev , M. , Gabbay , D.M. : Many-Dimensional Modal Logics : Theory and Applications . Elsevier ( 2003 )

10. Klarman , S. , Gutierrez-Basulto , V. : ALCALC: A context description logic . In: Proc. of JELIA-10 . ( 2010 )

11. Klarman , S. , Gutierrez-Basulto , V. : Two-dimensional description logics for context-based semantic interoperability . In: Proc. of AAAI-11 . ( 2011 )

12. Buvac , S. , Mason , I.A. : Propositional logic of context . In: Proc. of AAAI-93 . ( 1993 ) 412 { 419

13. Buvac , S. , Buvac , V. , Mason , I.A. : Metamathematics of contexts . Fundamenta Informaticae 23 412 { 419

14. Buvac , S. : Quanti cational logic of context . In: Proc. of AAAI-96 . ( 1996 ) 412 { 419

15. Nossum , R.: A decidable multi-modal logic of context . Journal of Applied Logic 1 ( 1 -2) ( 2003 ) 119 { 133

16. Wolter , F. , Zakharyaschev , M.: Multi-dimensional description logics . In: Proc. of IJCAI-99 , San Francisco, CA, USA ( 1999 ) 104 { 109

17. Lutz , C. , Wolter , F. , Zakharyaschev , M. : Temporal description logics: A survey . In: Proc. of TIME-08 . ( 2008 )

18. Baader , F. , Brandt , S. , Lutz , C. : Pushing the EL envelope . In: Proc. of IJCAI-05 . ( 2005 )

19. Baader , F. , Calvanese , D. , Mcguinness , D.L. , Nardi , D. , Patel-Schneider , P.F. : The description logic handbook: theory, implementation, and applications . ( 2003 )

20. Artale , A. , Lutz , C. , Toman , D.: A description logic of change . In Veloso, M., ed. : Proc. of IJCAI-07 . ( 2007 ) 218 { 223

21. Lutz , C. , Schroder, L. : Probabilistic description logics for subjective uncertainty . In: Proc. of KR-10 . ( 2010 )