Spatial Semantics for Concepts? Özgür L. Özçep and Ralf Möller Institute for Softwaresystems (STS) Hamburg University of Technology Hamburg, Germany {oezguer.oezcep,moeller}@tu-harburg.de Abstract. Finding concepts that are similar to a given concept can prove useful in constructing user-friendly interfaces for querying DL- ontologies—the concrete use case being a query answering system with an enhanced user interface that suggests semantically relevant keywords (based on concept similarity) during query formulation. Most investiga- tions on the similarity of concepts rely on ad-hoc and non-robust con- structions referring to syntactical relationships in the concept hierarchy. A more promising approach to concept similarity is first to ground the concepts in a topological, geometrical, or more generally a spatial seman- tics and then to use the corresponding proximity or nearness relations provided by the spatial semantics for deciding concept similarity. Such an approach would not only describe a semantical justification for sim- ilarity of concepts but also provide a more cognitive semantics in the style of Gärdenfors conceptual spaces that advance the comprehension by non-professional users of DL-systems. This paper discusses some pos- sible directions for a spatially oriented semantics for DLs, starting off from conceptual spaces and the region connection calculus. Keywords: concept similarity, conceptual space, region connection cal- culus, cognitive semantics 1 Introduction The cognitive hurdles that users who are not experts in logics have to overcome in order to use a DL based system (by e.g. constructing an appropriate ontology and using it for query answering), is quite high compared to those of other software systems. Hence there is a good reason (and there has been some work) to support non-experts with more intuitive means of accessing the services of a DL system within an enhanced user interface. Such an enhanced interface for query answering systems is also one of the aims in the FP7 EU project OPTIQUE (http://www.optique-project.eu/). One well proven concept of supporting users in query construction (e.g., conjunctive queries in an ontology based data access (OBDA) scenario) is to ? This work has been supported by the European Commission as part of the FP7 project Optique. suggest the user who did not get expected results with a new query containing concepts relevant to those in the original query. While in most search engines the relevancy is determined by statistics, a semantical relevancy condition based on concept similarity would be more appropriate for query answering in OBDA. Although concept similarity is a well investigated topic in knowledge repre- sentation and reasoning, most of the proposals have a more syntactic flavor in that they measure the distances within the concept hierarchy. This seems to be a mere ad-hoc and non-robust construction that can lead to changes in the sim- ilarity relation in case the hierarchy is extended with further concepts. In this paper, we try to lay the foundations for a semantically deeper notion of concept similarity by interpreting the extensions of concepts with objects in some spatial theory (be it some geometrical, topological or region oriented theory such as the based on RCC and presented in [22]). The nearness (or proximity) relations of the spatial theory can then be used to define concept similarity. Using a spatial foundation for concepts has not only positive effects for more intuitive query formulations (via concept similarity) but also for a better under- standing of ontologies. In DL Tboxes we may assert subsumption relationships between concept (and role) descriptions and possibly further constraints such as functionality and transitivity assertions for roles. Though this enables the user to model a domain and thereby still keep the reasoning services (such as satisfiabil- ity, subsumption testing etc.) feasible, there are two main problems concerning its application by non-expert users. The first and main point is that the logical notation with concept descriptions and its semantics does not seem to reflect the cognitive mental concepts by the users, as Gärdenfors argues [12]. Gärden- fors’ concepts have geometrical aspects [12,13], which are not reflected within the logical notation. Moreover, the logical notation is not fine-grained enough to distinguish between grammatical categories. Adjectives, verbs and nouns are represented by predicate symbols (in FOL) or concept names and roles (in DL). Complex concept constructions, such as a small elephants, cannot be properly handled by simple concept conjunction due to context dependence. The other point is that the lack of spatial aspects of concepts in standard DL reduces the expressibility of some natural relationships. Rather than just giving general inclusion (GCI) axioms for concepts one should be able to have a more geometrical or topological view with which one can leverage intuitions on concept similarity. Some examples are given by [32]. Having the binary relations of the RCC [25] at our disposal, we can formulate prototype relationships such as: ItalianRestaurant {NTPP}Restaurant. Here, NTPP stands for the non-tangential proper part relation between regions (see Section 3). Intuitively, this says more than the GCI italianReastaurant v Restaurant, namely it does not only say that all italian restaurants are restaurants but that the former are prototypical [29,30] instances of the latter. Here, “(proto)typical” instances means that these are situated closer to the center rather than the boundary of regions. In contrast, saying Bistro {TPP} Restaurant not only expresses that bistros are restaurants but that there are also bistros that are not typical restaurants. For simple concept descriptions as in the examples above, where only atomic concepts are used, we may have pretty strong intuitions on the meanings of the asserted spatial/topological relationships. Furthermore, we may clearly see the constraints in the common use of spatial relationships (e.g. the relations of RCC) and purely logical ones (e.g. subsumption). For example, saying that a concept is subsumed by another can be seen to imply that the former is a part of the latter, i.e., stand in the relation {TPP, NTPP, EQ}. For more complex descriptions, the intuitions may loose their strength. For example, taking the negation constructor, we may formulate that A v ¬B entails that A and B are disjoint, A{DC}B—and vice versa. But for a GCI where the negated concepts occur on the left-hand side, ¬A v B, there is no immediate connection to an RCC relationship between regions in pure RCC8 networks. In particular, if ¬A and B are chosen as convex regions, then A must be empty or a non-convex (unbounded) region with a hole. In this paper we discuss possible spatial interpretations of DL concepts. The kind of transformation of DL concepts and subsumption relations we have in mind has to be such that non-logical users may rely on their spatial intuitions for a better understanding of the mechanisms of the DL axioms which they build. Clearly, we could try to reduce some kind of translation or transformation of DL services to the satisfiability check in RCC8 networks. And in fact, the proof showing NP-hardness of satisfiability testing of RCC8 networks shows a reduction of 3SAT to it [28]. But this is a rather technical transformation that does not enlighten the cognitive semantics of concepts. As a first technical result we show how these ideas can be applied to a member of the DL-Lite family. The resulting proposition states that every consistent DL has a model where all basic concepts are interpreted with convex regions. The structure of the paper is as follows: After this introduction we give overviews of the well known conceptual spaces of Gärdenfors’ cognitive seman- tics (Section 2) and the widely known member of calculi for qualitative spatial reasoning, the region connection calculus (Section 3). Then mainly technical sec- tion (Section 4) shows the existence of models with convex regions for DL-Lite ontologies. The subsequent sections discuss related work, state the conclusion, and give an outlook on future work. 2 Conceptual Spaces Gärdenfors’ conceptual spaces (see the textbook [12] or a summary in [13]) are the main elements of a cognition oriented semantics of language which tries to fill the gap between sub-conceptual semantics on the low level of neuronal networks and the higher symbolic level of logical languages, in particular DLs. The overall aim of such cognitive semantics is to understand the connections between linguistic expressions and their mental representations by users, and as such it may prove beneficial for designing human machine interfaces (in particu- lar interfaces for query answering in DL systems) that is sensitive for the mental representations of the users. Conceptual spaces are geometrical in nature. This may not come as a sur- prise for a cognitively oriented model of semantics because human reasoning is essentially spatial in many cases, as we have argued before. As such, conceptual spaces are not only relevant for spatial (and temporal) reasoning, as argued in [17], but generally for representing and reasoning with concepts. We will give a short introduction to the main notions involved in conceptual spaces. Though our technical result will not directly rely on conceptual spaces (but rather on regions as represented by the region connection calculus), the main constraint of convexity is motivated within this framework. 2.1 Main Definitions for Conceptual Spaces To understand the ingredients of conceptual spaces, we consider the concept of a color. The color of an object is determined by three quality dimensions, chromat- icness (saturation), brightness, and hue. The first two of these are isomorphic to R with the usual ordering while the latter is isomorphic to a circle in the plane. Other examples of quality dimensions are force, height, width. Defining the color of an object calls for assigning it a point in the space induced by the three quality dimensions, which, by the way, has the form of a spinner; one cannot assign the object a value on one dimension without giving it a value on the other dimensions. Gärdenfors says that this set of quality dimensions is integral. The complementary notion is that of separability. The space made up of a set of integral quality dimensions that are separable from all other quality dimensions is called a domain. Note that according to this definition, a domain is identified by its dimension. But the important component of such a domain is the betweenness relation. The betweenness relation B(x, y, z) is a ternary relation read as point y is between points x and z. This notion generalizes that of a metric d which induces a betweenness relation by setting Bd (x, y, z) iff d(x, z) = d(x, y) + d(y, z). The betweenness relation is the basis for defining convex sets X in a domain: X is convex iff for all pairs of points contained in X one has also all points lying in between them in X, formally: for all x, z ∈ X: If B(x, y, z), then also y ∈ X. Convex sets are in a way well-shaped and as such are candidates for the mental pendants of concepts. Gärdenfors defines a (natural) concept to be a set of convex regions in possibly multiple domains. To be more precise, a concept is represented as a set of convex regions in a number of domains, together with information about how the regions in different domains are correlated. The additional constraint in the definition is due to the fact that though the quality dimensions in different domains may be separable they may not be independent in the sense that increasing the value in the one may lead to an increase in the latter. For example, take the concept of an apple. One of the domains in this concept is the color domain, and the (convex) region corresponding is the red- yellow-orange region. Another domain is the taste domain with the region of the sweet and sour dimension. Now, there are connections between the color of an apple and its sweetness, though the quality dimensions are in different domains. In this paper, we will only work with Gärdenfors concepts having exactly one domain. Gärdenfors calls them properties. 2.2 The Benefit of Convexity What are the reasons to define concepts on the basis of convex regions? The main reason is that of “cognitive economy” [12, p. 70], as learning and reasoning with concepts on convex regions seems to demand less cognitive capacities, or, more technically, less resources such as space (memory) and time. Technical underpinnings of this observation can be found in different areas in which convex regions seem to ease the computation; one example from the area of qualitative spatial and temporal reasoning can be found in [16]. The author gives an analytical and spatial characterization of the tractable subclass Ord-Horn [19] of the Allen calculus for reasoning on time intervals [2]; in essence, the tractable classes are (pre-)convex relations in an appropriate lattice of the basis relations. A quite different example stems from DLs with concrete domains, where the convexity on predicates over a domain is part of the admissibility conditions [5], which, if not fulfilled, may lead to undecidability of subsumption testing. And last but not least note that there is a whole subfield of numerical optimization called convex optimization [9], in which algorithms such as the simplex algorithm in linear programming are investigated. 2.3 Conceptual Space Semantics for DLs? Can we give a conceptual space semantics (abbreviated CSS in the following) for DLs such that, e.g., we can show: If a DL ontology has a (DL) model, then it has a CSS model. Or if that is not the case, can we characterize those DLs that have a DL model and not a CSS model? This paper will not give an answer to these questions, but will show the challenges in defining a CSS for DLs. As a result, we will “downgrade” the complexity of the semantics to one based on RCC (see next section) but keep the convexity constraint. The first idea of interpreting concept descriptions with CSS concepts seems natural. But it is not at all clear whether a DL concept expressions has to be interpreted by CSS properties or CSS concepts. Even, if we ignore the prob- lem of defining correlations between different CSS domains (that are needed for defining CSS concepts), it is not clear how to map DL concept constructors to constructors on CSS concepts and vice versa. The only real concept constructor defined in [12] is that of combining con- cepts, which has similarities with concept conjunction, but is quite a bit more complicated [12, p.122], as it tries to explain adjective noun combinations such as small elephant which cannot be handled by intersecting of the components’ extensions (small elephants may be bigger than big mosquitos). Nonetheless, re- stricting the combinations to simple noun-noun combinations with “and” may allow the interpretation by intersection of convex regions. As the intersection of convex regions is again a convex region, the operator would be well-defined. The dual operator of concept-disjunction could be realized by adding a convex- closure operator and defining concept disjunction as the convex closure of the union of the convex regions. But the main problem with cognitive oriented semantics is the handling of negation and quantifiers [12, p.202]. The idea of using the convex hull operator on the complement of a convex region does not work here: If the convex set is bounded, then the complement of it will not be convex. Hence, the convex hull of this set will give the whole domain—resulting in the implausible result that some objects belong to a concept and its negation. But, may be this is a hint on the fact that indeed the negation of a concept (represented by a bounded convex region) should not be seen as a “natural” (convex) concept. The concept of an apple is differently handled than the concept of a non-apple. Nonetheless, for pairs of concepts such as mortal/immortal it may be the case that they both can be represented by (unbounded) convex regions. Even worse is the handling of roles and the quantifiers formed by them. Actually, the only types of roles which Gärdenfors [12, p. 90] handles, are those defined in some domain as a subset over two dimensions. Two examples discussed by him are the representation of the “longer than” and the “is a heir of” relation. The main point is to show that these can be represented as convex regions in some conceptual CSS domain. The longer relation can be reduced to length operators and their comparison on R. Drawing the pairs of lengths in the 2-dim area shows that all pairs of relations standing in this relation form the area above the line y = x, and as such constitute a convex region. But, regarding concepts in this space, CSS roles would have the same “type” as CSS concepts, whilst in DLs roles have higher dimension than concepts. Similar comments are in order for the heirity relation (though this is defined on a completely different structure, namely the genealogy tree). 3 Region Connection Calculus The region connection calculus (RCC)[25] is a well known axiomatic calculus for qualitative spatial reasoning with binary relations on regions. Despite its early invention there is still recent relevant work on RCC in the spatial sessions of AI related conferences (see e.g. [8], [32], [14]). RCC8 is the most expressive members in the family of RCCi calculi each of which is identified by its set of i base relations. Every set of base relations has the JEPD property (jointly exhaustive, pairwise disjoint) meaning that any pair of regions may stand in exactly one of the base relations. As we will rely on the base relations of RCC8—henceforth denoted BRCC8 —we give their intended meanings informally in the following figure. DL relevant work on weaker members of RCC can be found in [23]. The formal definitions of the RCC8 base relations are given in an axiomatic system AxRCC8 which relies on one primitive (reflexive and symmetric) relation, namely the connectedness relation. The base relations induce an algebra of 28 general relations in a relation alge- bra where a general relation is is represented as a set {r1 , . . . , rk } of base relations covers contains TPPi(Y, X) NTPPi(Y, X) X: Y : DC(X, Y ) EC(X, Y ) PO(X, Y ) EQ(X, Y ) TPP(X, Y ) NTPP(X, Y ) disjointness externally partial overlap equal tangential non-tangential connected proper part proper part Fig. 1. Base relations of RCC8 and their intended meanings ri ∈ BRCC8 . The intended meaning of stating a general relation {r1 , . . . , rk } be- tween regions X and Y , denoted by X{r1 , . . . , rk }Y is that X is related to Y in one of the base relations ri (1 ≤ i ≤ k) (but we do not know exactly which). As we will use it in the following, we abbreviate the part-of relations {TPP, NTPP, EQ} by P. Giving relations between pairs of regions results in a network. Such a net- work may be consistent with the axiom system AxRCC8, but may also become inconsistent (as is the case for X{TPP}Y, Y {NTPP}Z, X{TPP}Z. Consistent networks are also called satisfiable. The set of regularly closed sets in R2 with the usual topology forms a model of AxRCC8 that is complete for testing satisfiability of RCC8 networks in the sense that any satisfiable network has a model with the regions interpreted by non-empty regularly closed sets. One can even show that a realization in R for any d ≥ 1 (in particular d = 1) is possible by interpreting regions as (sets) of d- dimensional polytopes [27, Theorem 15]. Regarding the motivation for convexity in the conceptual space approach, we plan to interpret regions as convex sets (in some euclidean space Rd ). And there is a recent result of [32] that sheds a good light on our plan: Every satisfiable RCC8 network is satisfiable by interpreting regions as convex regions in some Rd , d ≥ 1. More concretely, a network with 2d+1 variables can be satisfied in with convex regions in Rd . Note that we cannot fix d, i.e., the domain of convex regions in Rd , for a fixed dimension d is not complete for testing satisfiability of RCC networks (as shown by [11]). Regarding the conceptual space approach this means that we cannot tell in advance how many quality dimensions we need in order to represent concepts. 4 Convex Interpretations for DL-Lite Concepts If we want to introduce a geometrical (or more concrete) a region-based interpre- tation of concepts into DL ontologies, then we have to detail out the interplay between subsumption and the binary relations between regions as well as the interplay of concept constructions and the constructions on regions. Though a universal translation that holds for arbitrary DLs would be preferable, the re- strictions on the spatial target of the translation calls for different translations. We will look here first at a translation for ontologies into a fragment of a mem- ber of the DL-Lite family [4], namely the fragment entitled DL-LiteRp , which allows for role hierarchies and inverses of roles but not for negations of roles. (The superscript ‘p’ should remind the reader that we are working with positive roles only.) Definition 1 (DL-LiteRp ). Let RN be the set of role symbols and P ∈ RN , CN be a set of concept symbols, and A ∈ CN , Const be a set of individual constants and a, b ∈ Const. R −→ P | P − B −→ A | ∃R Cl −→ B Cr −→ B | ¬B Tbox: Cl v Cr , R v R Abox: A(a), P (a, b) Note that we do not allow for GCIs of the form A v ∃R.C; but these can be − modelled equisatisfiably by A v ∃Rnew , ∃Rnew v C, Rnew v R [10, p.286]. Most of the results concerning DL-Lite (in particular those concerning FOL rewritability) are based on a chase construction (originating in database theory). If, e.g., the TBox contains the axiom A1 v A2 and the ABox contains A1 (a) but not A2 (a), then it is enriched by the atom A2 (a). This procedure is applied stepwise to yield a monotonically increasing (with respect to set inclusion) se- quence of Aboxes starting with the original Abox. The resulting union of Aboxes is termed chase(O) and induces a canonical model can(O) for the Abox and the positive axioms of the Tbox, which are used in the chasing process. (For details cf. [10].) All we have know concerning the canonical structure can(O) is that if a DL ontology has a model, then can(O) is a model of O. We seek a translation of DL-LiteRp ontologies into RCC8 networks such that the consistency for DL-Lite can be reduced to the satisfiability test of RCC8 networks. We ignore the computational aspects at this stadium. Actually, in the original RCC8 network, an empty region is not allowed; thus unsatisfiability of the RCC8 network would imply only incoherence of the ontology—where incoherence means that a concept name in the ontology can be proved to be equivalent to ⊥. This can be handled in the following two ways: We can extend RCC such that the empty region is allowed (as done by [15]), thereby considering the realizability of RCC8 networks by regular closed sets and defining the empty region r∅ as a region fulfilling DC(r∅ , r∅ ). We do not follow this solution (because we loose the JEPD property, as the empty region stand in DC and EQ relation to itself.) But we assume that for all concept symbols there is a verifier in the Abox, such that inconsistency testing and incoherence testing give the same results. We call such ontologies verifier complete. The main restriction of the logic DL-LiteRp is that the negation symbols occur only on the right-hand sides of GCIs; hence we do not have to give an interpretation for the negations of concepts but only for basic concepts B. Let Base(RN, CN ) denote the basic concepts over RN and CN . Now, we can define CSS interpretations and the notion of a CSS model of an DL-LiteRp ontology. Definition 2. A CSS interpretation for an (ordinary) DL interpretation I = (∆I , ·I ) is a structure with a domain ∆I and an interpretation function ·I such that – I is a DL interpretation in the usual sense (respecting the semantics of the inverse operation and of existentials) ∆I is Rn for some n ∈ N \ {0}. – Every basic concept B is interpreted by a convex region (B)I in ∆I w.r.t. the euclidean metric. A CSS model of a DL-LiteRp ontology O is an CSS interpretation which is a DL model of O. In order to reduce the consistency test of DL-Lite ontologies to the satisfi- ability test of RCC8 networks we give a translation. With basic concepts and constants B we associate its corresponding region X B and translate the GCIs and the Abox axioms as follows. B1 v B2 X B1 {P}X B2 B1 v ¬B2 X B1 {DC}X B2 A(a) X a {P}X A − P (a, b) X a {P}X ∃P , X b {P}X ∃P − − P 1 v P2 X ∃P1 {P}X ∃P2 , X ∃P1 {P}X ∃P2 − − P1 v P2− X ∃P1 {P}X ∃P2 , X ∃P1 {P}X ∃P2 similarly for P1− v P2 and P1− v P2− Additionally, for every pair of basic concepts B and constant c we add the con- straint X B {DC}X c , and for all c1 , c2 also add X c1 {DC}X c2 (this implements the unique name assumption). For an ontology O let X O denote its corresponding RCC network. The main technical result is given in the following theorem. Theorem 1. A verifier complete DL-LiteRp ontology O is consistent iff it has a CSS model. Proof. If O has an CSS model and all CSS models are DL models, we directly get a DL model for O. The proof of the other direction is more complicated. Assume that O has a DL model. We show that X O must be satisfiable by interpreting concepts by unions of polyeders in R. (This is in accordance with [27].) As O has a model, the canonical structure can(O) built by the chase construction is also a model. This model may be infinite. Let all constants occurring in can(O) be placed in an arbitrary ordering on the integer points of R starting at 0. Now interpret X c by a small interval of width 0.5 with middle point c. For every concept A let X A be the union of all c such that A(c) occurs in the chase. Let X ∃P be the union of all X c such that P (c, c1 ) or P − (c1 , c) occurs − in the chase for some constant c1 . Similarly for X P . Now, this construction respects all constraints in X O . But as [32] show, then X O must be satisfiable with convex regions. From this RCC model we get an CSS model as follows: Interpret all concept symbols A by the convex regions. Interpret every constant with an arbitrary point in the convex region for it and interpret the roles R by − the cartesian product X R × X R . This is possible due to the fact that we do not allow for role negation in DL-LiteRp . This theorem is essential to build more interesting logics that are able to model prototype relationships as those mentioned in the introduction. For ex- ample, adding the RCC8 base relations TPP, NTPP, EC to DL-LiteRp forces us to leave the general DL semantics and constrain it to CSS interpretations. But note that we can still investigate properties (such as FOL rewritability) by consid- ering the narrower set of CSS interpretations. These investigations are planned for future work. 5 Related Work Ideas on specifying spatial semantics for a logical language can be traced back to work of McKinsey and Tarski [18] who develop topological semantics for propositional modal logics and show that that topologically valid formula are just the valid formulas of the modal logic S4. The relevance of these results for the region connection calculus is explicated by [21] and was first pointed out by a modal logical interpretation of RCC8 networks by Bennett [6]. A one-to-one translation of the topological semantics to description logics is prima facie not possible, though there are well known connections between description logics and multi-modal logics [31]. In the motivation for this paper we also stated the observation that spatial semantics ease the understanding of logical systems by non-expert users. This assumption finds its justification also in the area of diagrammatic reasoning [3] which deals with the mechanisms of human reasoning with graphical means (mainly in two dimensions). And indeed, the CSS interpretations for the DL- Lite fragment in this paper have strong connections to Venn diagrams, which can be used for doing syllogistic reasoning (in principle reasoning over the monadic function free universal fragment of predicate logic). Convexity has an important role in conceptual spaces and also the spatial semantics proposed in this paper. We deal with convexity only on the semantic level. Clearly one can also introduce a primitive predicate for convexity in the language level as done for euclidean logics in [24] and [20]. But the high expres- sivity of such logics comes at the prize of bad computational complexity that does not fit into the general DL approach. With respect to the use of conceptual spaces there are already approaches in the recent literature that try to incorporate these cognitive ideas into ontologies as described by [26] on the basis of their formalization in [1]. The conceptual space markup language (CSML) described in [26] is embedded into a hybrid approach using DL ontologies on top of which intended conceptual spaces are constructed with CSML. This is different from our approach as it provides means to directly build the conceptual space within an CSML ontology while our ap- proach uses them on the semantic level (and only in its rougher version of convex regions in euclidean spaces.) The authors of [26] sketch a possible mapping of the CSML ontology into OWL as part of an current research objective. But note that this mapping has the reverse direction to our semantics, and moreover the mapping is mostly a form of reification that hides the semantics in the domain. 6 Conclusion and Outlook A spatial semantics for DLs may prove useful in building intuitive interfaces for use by non-experts, the point in case being the suggestion of similar concept. This paper was intended to discuss possible approaches for defining adequate spatial semantics for DLs that could be the basis for concept similarity. As a first technical result following the survey and discussion we provide spatial semantics on the basis of convex regions for a member of DL-Lite family and show that the spatial interpretations of this logic are complete for satisfiability testing. But still the type of semantics presented here has to prove its benefits. The main question is whether the ideas for interpreting DL-Lite basic concepts with convex regions can be extended to more expressive DLs. In Section 2 we hinted already on the challenges with incorporating negation and quantifiers. In future work we will deal with these challenges in the RCC framework. By allowing boolean constructors on regions we get the more expressive logic BRCC8 [33]. Again, the negations of convex regions are not necessarily convex. Hence, we may get additional constrains (unboundedness) on concepts; as far as known to us, there is (still) no result corresponding to the result of [32] stating the completeness of convex regions for satisfiability testing of RCC networks. Quite more problematic is the incorporation of quantifiers into the RCC framework. Here, we have to find intuitions on what it means to apply the ∃R operator on a region? What kind of region do we expect to get (in contrast e.g. to ∀R)? One idea inspired by mathematical morphology [7] is to find (for each role symbol R) a structuring element B R . Then one could define dilation and erosion operators based on B or more concretely its translation for a concrete element x, Bx as follows. DB (X) = {x ∈ Rn | Bx ∩ X 6= ∅} and EB (X) = {x ∈ Rn | Bx ⊆ X} Here, “B defines a neighborhood that is considered at each point” [7]. Note that the dilation operator amounts to exists operators whilst erosion operators amounts to all quantifiers. If at least the union (or sum) operator is added to RCC8, one can use the framework of [22] to define a notion of concept similarity based on the nearness relations between regions. The general idea is to partition the domain into a tree structured hierarchy of so called level determining (ld) concepts that make up the underlying structure for the similarity comparison of arbitrary concepts. Then one considers a concept C1 to be similar to a concept C2 iff C1 and C2 are contained (RCC relation P) in the same upper ld concept, or at least C1 touches (RCC relation EC) the upper ld concept of C2 . References 1. Adams, B., Raubal, M.: A metric conceptual space algebra. In: Proceedings of the 9th international conference on Spatial information theory. pp. 51–68. COSIT’09, Springer-Verlag, Berlin, Heidelberg (2009) 2. Allen, J.F.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832–843 (Nov 1983) 3. Allwein, G., Barwise, J.: Logical Reasoning with Diagrams. Oxford University Press (1996) 4. Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The dl-lite family and relations. J. Artif. Intell. Res. (JAIR) 36, 1–69 (2009) 5. Baader, F., Brandt, S., Lutz, C.: Pushing the EL envelope. In: IJCAI’05: Pro- ceedings of the 19th international joint conference on Artificial intelligence. pp. 364–369. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2005) 6. Bennett, B.: Modal logics for qualitative spatial reasoning. Logic Journal of the IGPL 4(1), 23–45 (1996) 7. Bloch, I., Lang, J.: Towards mathematical morpho-logics. In: Bouchon-Meunier, B., Gutiérrez-Rı́os, J., Magdalena, L., Yager, R.R., Kacprzyk, J. (eds.) Technologies for constructing intelligent systems, pp. 367–380. Physica-Verlag GmbH, Heidelberg, Germany, Germany (2002) 8. Bodirsky, M., Wölfl, S.: Rcc8 is polynomial on networks of bounded treewidth. In: Proceedings of the Twenty-Second international joint conference on Artificial Intelligence - Volume Volume Two. pp. 756–761. IJCAI’11, AAAI Press (2011) 9. Boyd, S., Vandenberghe, L.: Convex optimization. Cambridge university press (2004) 10. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Poggi, A., Rodrı́guez- Muro, M., Rosati, R.: Ontologies and databases: The DL-Lite approach. In: Tes- saris, S., Franconi, E. (eds.) Semantic Technologies for Informations Systems – 5th Int. Reasoning Web Summer School (RW 2009), Lecture Notes in Computer Science, vol. 5689, pp. 255–356. Springer (2009) 11. Davis, E., Gotts, N.M., Cohn, A.G.: Constraint networks of topological relations and convexity. Constraints 4(3), 241–280 (Sep 1999) 12. Gärdenfors, P.: Conceptual Spaces: The Geometry of Thought. The MIT Press, Cambridge, Massachusetts (2000) 13. Gärdenfors, P.: Semantics based on conceptual spaces. In: Proceedings of the 4th Indian conference on Logic and its applications. pp. 1–11. ICLA’11, Springer- Verlag, Berlin, Heidelberg (2011) 14. Huang, J.: Compactness and its implications for qualitative spatial and temporal reasoning. In: Brewka, G., Eiter, T., McIlraith, S.A. (eds.) KR. AAAI Press (2012) 15. Kontchakov, R., Pratt-Hartmann, I., Wolter, F., Zakharyaschev, M.: Spatial logics with connectedness predicates. Logical Methods in Computer Science 6(3) (2010) 16. Ligozat, G.: A new proof of tractability for ord-horn relations. In: Clancey, W.J., Weld, D.S. (eds.) AAAI/IAAI, Vol. 1. pp. 395–401. AAAI Press / The MIT Press (1996) 17. Ligozat, G., Condotta, J.F.: On the relevance of conceptual spaces for spatial and temporal reasoning. Spatial Cognition & Computation 5(1), 1–27 (2005) 18. McKinsey, J., Tarski, A.: The algebra of topology. Annals of mathematics 45(1), 141–191 (1944) 19. Nebel, B., Bürckert, H.J.: Reasoning about temporal relations: A maximal tractable subclass of allen’s interval algebra. Journal of the ACM 42(1), 43–66 (1995) 20. Nenov, Y., Pratt-Hartmann, I.: On the computability of region-based euclidean logics. In: Proceedings of the 24th international conference/19th annual confer- ence on Computer science logic. pp. 439–453. CSL’10/EACSL’10, Springer-Verlag, Berlin, Heidelberg (2010) 21. Nutt, W.: On the translation of qualitative spatial reasoning problems into modal logics. In: Burgard, W., Cremers, A., Cristaller, T. (eds.) KI-99: Advances in Ar- tificial Intelligence, Lecture Notes in Computer Science, vol. 1701, pp. 699–699. Springer Berlin / Heidelberg (1999) 22. Özçep, O.L., Grütter, R., Möller, R.: Nearness rules and scaled proximity. In: Raedt, L.D., Bessiere, C., Dubois, D. (eds.) Proceedings of ECAI 2012. pp. 636– 641 (2012) 23. Özçep, Ö.L., Möller, R.: Combining DL-Lite with spatial calculi for feasible geo- thematic query answering. In: Kazakov, Y., Lembo, D., Wolter, F. (eds.) Proceed- ings of the 25th Iternational Workshop on Description Logics (DL 2012). vol. 846 (2012), http://ceur-ws.org/Vol-846/ 24. Pratt, I.: First-order qualitative spatial representation languages with convexity. Spatial Cognition and Computation 1(2), 181–204 (Mar 1999) 25. Randell, D.A., Cui, Z., Cohn, A.G.: A spatial logic based on regions and connection. In: Proceedings of the 3rd International Conferecence on Knowledge Representa- tion and Reasoning. pp. 165–176 (1992) 26. Raubal, M., Adams, B.: The semantic web needs more cognition. Semant. web 1(1,2), 69–74 (Apr 2010) 27. Renz, J.: A canonical model of the region connection calculus. Journal of Applied Non-Classical Logics 12(3-4), 469–494 (2002) 28. Renz, J.: Qualitative Spatial Reasoning with Topological Information, Lecture Notes in Computer Science, vol. 2293. Springer (2002) 29. Rosch, E.: Natural categories. Cognitive Psychology 4, 328–350 (1973) 30. Rosch, E.: Cognitive representations of semantic categories. Journal of Experimen- tal Psychology: General 104(3), 192–233 (1975) 31. Schild, K.: A correspondence theory for terminological logics: Preliminary report. In: Proceedings of IJCAI-91. pp. 466–471 (1991) 32. Schockaert, S., Li, S.: Convex solutions of RCC8 networks. In: Raedt, L.D., Bessière, C., Dubois, D., Doherty, P., Frasconi, P., Heintz, F., Lucas, P.J.F. (eds.) ECAI. Frontiers in Artificial Intelligence and Applications, vol. 242, pp. 726–731. IOS Press (2012) 33. Wolter, F., Zakharyaschev, M.: Spatial Reasoning in RCC8 with Boolean Region Terms. In: European Conference on Artificial Intelligence. pp. 244–250 (2000)