Context in Categorization

Abstract

We investigate contextual categorizations, i.e., categorizations holding only with respect to a specific context, from a formal semantics perspective. Contexts are modeled as sets of description logic models for different languages, and operations on contexts are defined which provide a new formal characterization of context interplay and especially of a form of context abstraction which we call focus. The framework is compared with relevant related work and discussed from the viewpoint of context theory issues. Finally, a simple scenario is formalized.

Introduction

The motivation of the present research lies in problems concerning the formal specification of normative systems for modeling multi-agent systems ([ 5, 17 ]). In the study of normative systems, it is a widely acknowledged opinion that normative systems of high complexity, for example legal systems or institutional ones, should be viewed not only as regulative systems, but also as systems specifying conceptualizations, or categorizations, of the domain of entities they are supposed to regulate ([ 2, 15 ]). Besides, contexts have been often advocated to play a central role in the specification of complex normative systems ([ 6, 17 ]).

In [ 12, 11 ] we proposed a framework for representing this categorizing feature of normative systems via contextual terminological statements of the form “A counts as B in context C”. In [ 10 ] the framework is put at work and discussed from the point of view of the specification of agent-based electronic institutions. The present work intends to pursue this research line further from the point of view of formal context theory, focusing on the characteristics of the notion of context which our analysis of contextual categorizations delivers, thus relating our approach with work in that area.

The issue of context in categorization has been touched upon in [ 1 ] and the idea of perspectival conceptualizations of a same set of entities has been discussed in context theory literature ([ 4 ]). Here, we analyze contextual categorizations making use of a contextual version of the semantic machinery of description logic ([ 3 ]). In particular, we are interested in providing not only a formal framework able to represent different categorizations of the same set of entities, but also a formal characterizations of how different contexts interact and can be related. With respect to this, particular attention is dedicated to a notion of context abstraction which we call focus.

The key idea of modeling contexts as sets of first-order models is borrowed from the framework developed in [ 7 ], and tailored to the analysis of the categorization phenomenon by imposing some constraints such as: considering only simpler models (description logic ones), and assuming a unique domain of interpretation (since categorizations of a same set of entities are at issue). However, a main difference with respect to that work resides in the characterization of how contexts are related with each other. Context interplay is characterized essentially via operations on sets of models instead of relations (compatibility relations) externally imposed on the set of models in order to validate selected bridge rules. This enables a new perspective in understanding context operations in general, yielding a representation of contexts as “algebraic entities”. Contexts are therefore seen as objects belonging to specific mathematical structures. This suggests the possibility to import to contextual reasoning the standard distinction between inference rules which are domain-specific, and inference rules which are instead logical. Bridge rules are commonly intended as domain-specific intercontextual inference rules: “if α1 holds in c1, then infer that α2 holds in c2”. Here we sketch a new type of bridge rules as logical inter-contextual inference rules based on context operations. For instance, we will see that for the notion of context abstraction (as intended here) the following rule holds: “if α holds in the abstraction of context c, then it holds also in c”.

The paper is organized as follows. In Section 2 we expose some preliminary considerations and we introduce a scenario which is used along the whole paper as an example. In Section 3 the formal framework is introduced, and in Section 4 it is compared with closely related work and some of its theoretical features and insights are discussed. In Section 5 the framework is put at work formalizing the example scenario. Conclusions follow in Section 6. 2

Preliminaries

We depict a simple scenario in order to clarify our domain of interest. Example 1. (The public park scenario) In the regulation governing access to public parks in region R it is stated that: “vehicles are not allowed within public parks”. In this regulation no mention is made of (possible) subconcepts of the concept vehicle, e.g., cars, bicycles, which may help in identifying an instance of vehicle. In municipal regulations subordinated to this regional one, specific subconcepts are instead handled. In municipality M1, the following rule holds: “bicycles are allowed to access public parks”. In M2, it holds that: “bicycles are not allowed to access public parks”. In both M1 and M2 it holds that: “cars are not allowed in public parks”.

There are three relevant contexts: namely R, M1 and M2; and two languages: the language of R (say, L0), which is constituted by the two concepts vehicle and allowed (in public parks), and the language of M1 and M2 (say L1), expanding L0 with the concepts car and bike. The scenario displays interesting issues at at least two different levels. Firstly, at the intra-contextual (within contexts) level, categorizations hold in M1 and M2 which diverge on the interpretation of vehicle and therefore on the classification of bike: different categorizations hold in different contexts. Secondly, at the inter-contextual (between contexts) level, contexts M1 and M2 can be seen as specializations of R. They are expressed on a richer language (they talk also about cars and bicycles), they inherit the constraints holding in R (“vehicles are objects which are not allowed within public parks”) and they specify them further (the concept of “vehicle” happens to be restricted both in M1 and M2). This shows that contexts can be related in precise ways. These aspects raise the two leading questions we address in this work: 1) How to formally represent contextual categorizations of the type depicted in the scenario? 2) How to give formal meaning to context interplay such as the one described in the scenario?

The first question is tackled using the idea grounding the local models semantics of contextual reasoning ([ 7 ]): contexts are viewed as sets of first order models. Since we are interested in simple categorizations though, the underlying formal semantic framework is the one of description logic ([ 3 ]). This allows us to concentrate on simpler models than the ones considered in the general setting of local models semantics. With respect to the second question, our line consists in exploiting further the intuition of contexts as sets of (description logic) models in order to provide straightforward model-theoretical definitions of operations and relations on contexts.

In particular, we will introduce: a contextual disjunction operator and a contextual focus operator1. The first one yields a union of contexts: the contexts “viruses” and “bacteria” can be unified on a language talking about microorganisms generating a more general context like “viral or bacterial microorganisms”. The second one, which plays a central role in our framework, yields the context consisting of some information extracted from the context on which it is focused: the context categorizing “crocodiles”, for instance, can be obtained via focusing the context which categorizes all reptiles on the language talking only about crocodiles and disregarding other reptiles. In other words, the operator prunes the information contained in the context “reptiles” focusing only on what is expressible in the language which talks about crocodiles and abstracting from the rest. Finally, also maximum and minimum contexts will be introduced: these will represent the most general, and respectively the most specific, contexts on a language2.

As it appears from this list of examples, operators will need to be indexed with the language where the operation they denote takes place. The point is 1 In [ 12, 11 ] the focus operation is called abstraction. We decided to modify our terminology in order to avoid confusions with other approaches to notions of abstraction like for instance [ 8 ], with which our work is put in perspective in Section 4.1. 2 In this paper, we limit the number of context operations to disjunction and focus.

More operations are formalized in [ 12 ]. It is worth noticing, in passing, that similar operations and special contexts are discussed in [ 16 ]. that contexts always belong to a language, and so do operations on them. Besides these operations, a generality relation between contexts ([ 14 ]) will also be considered and formalized which expresses that a context is at most as general as another one. An alternative reading of the relation, in terms of the notion of partiality ([ 4 ]), is that a context is at most as partial as another one. These intuitions are clarified and made more rigorous in the following section. 3

A model-theoretic framework

The content of this section is based on [12, 10, 11].

3.1

Language

The language we are defining is a formal metalanguage for talking about sets of subsumption relations, i.e., what in description logic are called terminological boxes (TBoxes). However, we consider only TBoxes specified on very simple languages containing only concepts and boolean operators, i.e., languages of the type ALC ([ 3 ]) but with an empty set of roles. The syntax of these languages is kept simple because the use of boolean concept descriptions alone is enough to model the scenario depicted in Example 1. It serves to illustrate the main ideas of our approach and can be naturally extended with role constructs (like we did in [ 10 ]) in order to model more realistic scenarios.

Language LCT (language for contextual taxonomies) is therefore built on a family of conceptual languages {Li}0≤i≤n. Each Li contains a non-empty finite set Ai of atomic concepts (A), i.e. the alphabet of Li, the zeroary operators ⊥ and > (bottom and top concept), the unary operator ¬ (concept negation), and the binary operator t (concept union). Language LCT contains the alphabets of each Li.

Besides, the alphabet of LCT contains a finite set of context identifiers c, two families of zeroary operators {⊥i}0≤i≤n (minimum contexts) and {>i}0≤i≤n (maximum contexts), a family of unary operators {fcsi}0≤i≤n (context focus operators), a family of binary operators {gi}0≤i≤n (context disjunction operators), one context relation symbol 4 (context c1 “is at most as general as” context c2) and a contextual subsumption relation symbol “ . : . v .” (within context c, concept A1 is a subconcept of concept A2 ), finally, the sentential connectives ∼ (negation) and ∧ (conjunction). Thus, the set Ξ of context constructs (ξ) is defined through the following BNF:

ξ ::= c | ⊥i | >i | fcsi ξ | ξ1 gi ξ2.

Concepts and concept constructors are then defined in the usual way. The set Γ of concept descriptions (γ) is defined through the following BNF: The set A of assertions (α) is then defined through the following BNF: γ ::= A | ⊥ | > | ¬γ | γ1 t γ2.

α ::= ξ : γ1 v γ2 | ξ1 4 ξ2 | ∼ α | α1 ∧ α2.

Technically, a contextual taxonomy in LCT is a set of subsumption relation expressions which are contextualized with respect to the same context, e.g.: {ξ : γ1 v γ2, ξ : γ2 v γ3}. This kind of sets of expressions are what we are interested in to model different categorizations. Assertions of the form ξ1 4 ξ2 provide a formalization of the notion of generality introduced in Section 23. 3.2

Semantics

In order to provide a semantics for LCT languages, we proceed as follows. First we define a class of structures which can be used to provide a formal meaning to those languages. We characterize then the class of operations and relations on contexts that constitute the semantic counterpart of the expressions introduced in Section 3.1.

We recollect the definition of a description logic model for a language Li ([ 3 ]). Definition 1. (Models for Li’s) A model m for a language Li is a structure m = hΔm, Imi where: Δm is the (non empty) domain of the model; Im is a function Im : Ai −→ P(Δm), that is, an interpretation of (atomic concepts expressions of ) Li on Δm. This interpretation is inductively extended to Γ :

Im(>) = Δm Im(⊥) = ∅

Im(¬γ) = Δm\ Im(γ)

Im(γ1 t γ2) = Im(γ1) ∪ Im(γ2).

A model m for a language Li assigns a denotation to each atomic concept (for instance the set of elements of Δm that instantiate the concept bike) and, accordingly, to each complex concept (for instance the set of elements of Δm that instantiate the concept vehicle t bike). – {Mi}0≤i≤n is the family of the sets of models Mi of each language Li. That is, ∀m ∈ Mi, m is a model for Li. – I is a function I : c −→ P(M0) ∪ . . . ∪ P(Mn). In other words, this function associates to each atomic context identifier in c a subset of the set of all models in some language Li: I(c) = M with M ⊆ Mi for some i s.t. 0 ≤ i ≤ n. Function I can be seen as labeling sets of models on some language i via atomic context identifiers. Notice that I fixes, for each atomic 3 In Section 5 the following symbol will be also used “ . : . @ .” (within context c, concept A1 is a proper subconcept of concept A2 ). It can be defined as follows: ξ : γ1 @ γ2 =def ξ : γ1 v γ2 ∧ ∼ ξ : γ2 v γ1.

context identifier, the language on which the context denoted by the identifier is specified. We could say that it is I itself which fixes a specific index for each atomic context identifier c. – ∀m0, m00 ∈ S0≤i≤n Mi, Δm0 = Δm00 . That is, the domain of all models m is unique. As we already noticed, we assume this constraint simply because we are interested in modeling different (taxonomical) conceptualizations of a same set of individuals.

This can be clarified by means of a simple example. Suppose the alphabet of LCT to be the set of atomic concepts {allowed, vehicle, car, bike} and the set of atomic context identifiers {cM1, cM2, cR}. The number of possible languages Li given the four aforementioned concepts is obviously 24 − 1. A ct-model for this LCT language would have as domain the set of the sets of all models for each of the 24 − 1 Li languages, and as interpretation a function I which assigns to each cM1, cM2 and cR a subset of an element of that set, i.e., a set of models for one of the Li languages. We will come back to this specific language in Section 5, where we discuss the formalization of the public park scenario. 3.4

Context focus

We model focus as a specific operation on sets of models which provides the semantic counterpart for the contextual focus operator introduced in LCT . Intuitively, focusing a context ξ on a language Li yields a context consisting in that part of ξ which can be expressed in Li.

Let us first recall a notion of domain restriction (e) of a function f w.r.t. a subset C of the domain of f . Intuitively, a domain restriction of a function f is nothing but the function Cef having C as domain and s.t. for each element of C, f and Cef return the same image: Cef = {hx, f (x)i |x ∈ C}. Definition 3. (Context focus operation: ei) Let M 0 be a set of models, then: eiM 0 = {m | m = hΔm0 , AieIm0 i & m0 ∈ M 0}. In order to clarify our semantics of focus, we provide the following analysis of some relevant properties enabled by Definition 3.

Proposition 1. (Properties of context focus)

Operation ei is: surjective, idempotent (ei(eiM ) =eiM ), normal (ei∅ = ∅), additive (ei(M1 ∪ M2) =eiM1∪eiM2), monotonic (M1 ⊆ M2 ⇒eiM1 ⊆eiM2).

Proof. [Surjectivity] That ei is surjective can be proved per absurdum. First notice that this operation is a function of the following type: ei : P(M0) ∪ . . . ∪ P(Mn) −→ P(Mi) with 1 ≤ i ≤ n. If it is not surjective then exists M 00 ⊆ Mi s.t. for all M 0 in the domain of ei, eiM 0 6= M 00. This means that for all M 0 in the domain of ei, {m | m = hΔm0 , AieIm0 i & m0 ∈ M 0} 6= M 00, which is impossible because we have at least that eiM 00 = M 00. [Idempotency] The proof of the equation for idempotency from Definition 3 is straightforward. [Normality] Normality follows also easily from Definition 3. [Additivity] Additivity is easily proved showing the following: ei(M1 ∪ M2) is equal to {m | m = hΔm0 , AieIm0 i & m0 ∈ M1 ∪ M2}, which is in turn equal to {m | m = hΔm0 , AieIm0 i & m0 ∈ M1 or m0 ∈ M2} and therefore to eiM1∪eiM2. [Monotonicity] It follows from additivity.

The operation of focus allows for shifting from richer to simpler languages and it is, as we would intuitively expect: surjective (every context, even the empty one, can be seen as the result of focusing a different richer context, in the most trivial case, a focus of itself), idempotent (focusing on a focus yields the same first focus), normal (focusing the empty context yields the empty context), additive (the focus of a context obtained via joining of two contexts can be obtained also joining the focuses of the two contexts), monotonic (if a context is less general then another one, the focus of the first is also less general than the focus of the second one). Notice also that operation ei yields the empty set of models when it is applied to a context M 0 the language of which is not an expansion of Li. This is indeed very intuitive: the context obtained via focus of the context “dinosaurs” on the language of, say, “gourmet cuisine” should be empty. 3.5

Operations on contexts

We are now in a position to give a semantics to context constructs as introduced in Section 3.1. In Definition 2 atomic contexts are interpreted as sets of models on some language Li for 0 ≤ i ≤ n: I(c) = M ∈ P(M0) ∪ . . . ∪ P(Mn). The semantics of context constructs Ξ can be defined via inductive extension of that definition.

Definition 4. (Semantics of context constructs)

The semantics of context constructs is defined as follows:

I(fcsi ξ) =eiI(ξ) I(⊥i) = ∅

I(>i) = Mi I(ξ1 gi ξ2) =ei(I(ξ1) ∪ I(ξ2)).

The focus operator fcsi is interpreted on the contextual focus operation introduced in Definition 3, i.e., as the restriction of the interpretation of its argument to language Li. The ⊥i context is interpreted as the empty context (the same on each language); the >i context is interpreted as the greatest, or most general, context on Li; the binary gi-composition of contexts is interpreted as the lowest upper bound of the restriction of the interpretations of the two contexts on Li4. 3.6

Assertions

Semantics for the assertions A is also based on the function I. In what follows we denote with δ(I) the domain of an interpretation function I. 4 It can be proved that the context disjunction is definable in terms of focus and boolean conjunction. We nevertheless chose to keep it explicit in the language because of its intuitively clear meaning and as instructive means for the exposition of the language itself and its characteristics.

Definition 5. (Semantics of assertions: |=) The semantics of assertions is defined as follows:

M |= ξ : γ1 v γ2 iff ∀m ∈ I(ξ) : γ1, γ2 ∈ δ(Im) and Im(γ1) ⊆ Im(γ2)

M |= ξ1 4 ξ2 iff I(ξ1) ⊆ I(ξ2) A contextual concept subsumption relation between γ1 and γ2 holds iff concepts γ1 and γ2 are defined in the models constituting context ξ, i.e., they receive a denotation in those models, and all the basic description logic models constituting that context interpret γ1 as a subconcept of γ2. Note that this is precisely the clause for the validity of a subsumption relation in standard description logics, but together with the fact that the concepts involved are actually meaningful in that context5. The 4 relation between context constructs is interpreted as a standard subset relation: ξ1 4 ξ2 means that context denoted by ξ1 contains at most all the models that ξ2 contains, that is to say, ξ1 is at most as general as ξ2. Note that this relation is obviously reflexive, antisymmetric and transitive. Clauses for boolean connectives are the obvious ones and notions of validity and logical consequence are classically defined. 4 4.1

Discussion

Abstraction and focus: a comparison

In this section we expose some considerations relating our notion of context focus to the model theoretic approach to abstraction proposed in [ 8 ].

In [ 8 ], abstraction is a mapping abs between two languages: the ground language (L0), and the abstract language (L1). The function abs is total (all expressions in L0 are associated to at least one expression in L1) and surjective. Models for abstraction functions are then defined in terms of compatibility relations ([ 7 ])6 on the basis of domain relations ([ 9 ]). Domain relations are mappings describing the relations holding between the interpretation domain of L0 and L1: r : Δ0 −→ Δ1. Intuitively, a domain relation states which entities of the domain of L1 count as which entities of the domain of L0. Given a domain relation r, a model for the abstraction abs is defined as a compatibility relation C, i.e., a set of pairs of models of, respectively, L0 and L1. In other words, given a function abs and a mapping r, a compatibility relation specifies which models of L1 are abstract counterparts of which models of L0.

Let us consider the operation of context focus as a form of abstraction. There are some essential differences between our approach and the work just summarized. First of all, the relation between the ground language and the abstraction 5 The satisfaction clause of contextual subsumption relations would deserve some more remarks. We refer readers to [ 12 ]. What we can underline here, is that this semantics interprets contextual subsumption relations as inherently presupposing the meaningfulness of their terms. 6 Compatibility relations constitute the semantic counterpart of bridge rules. They specify how meaning is preserved in shifting from one context to another. language is, in our work, a superset relation, since focus prunes information away. It is therefore no total mapping as in [ 8 ]. However, it is worth noticing that the totality of the mapping is there guaranteed making use of a specific constant EE (everything else) to which all non relevant expressions of the ground language can be mapped. In our approach, what is not relevant is exactly what is left aside by the language of the focus. Besides, being interested in contextual categorization, we consider just one unique domain of interpretation for both the ground and the abstraction languages. In some sense, we assume trivial domain relations r = Δ × Δ (see Definition 2). Secondly, while in [ 8 ] abstraction is viewed in the first instance as a linguistic phenomenon concerning two languages, the focus operation is instead a function the domain of which is the set of all possible contexts and the co-domain is the set of all contexts on the focus language (ei : P(M0) ∪ . . . ∪ P(Mn) −→ P(Mi)): given a context, the function yields its focus on a selected language.

These characteristics enable in a straightforward way a number of intuitive properties, among which some were studied in Proposition 1. Such properties appear to be intuitive for a notion of abstraction intended as focus, especially in relation with the categorization domain. On the other hand, our approach is clearly of a less general nature, and indeed, many of the aforementioned properties cannot be proved in the approach of [ 8 ]. In fact, despite these differences, it is instructive to notice that our notion of focus can be perfectly framed within the approach exposed in [ 8 ] and can be therefore regarded as a special case of the notion of abstraction as intended in that work. Interestingly, this becomes evident considering Definition 3 from a slightly different perspective. Function ei itself can be viewed as specifying a compatibility relation C defined as follows. Consider a context ξ on L0 and its abstraction fcs1ξ on the sublanguage L1 and let Δ be the domain of the two languages: C = {hm, m0i | m ∈ I(ξ) & m0 = hΔ, A1eImi}. Thus, ei can be viewed as defining a compatibility relation constituted by the pairs of models of the context on the ground language and their restrictions to the abstraction language.

Contexts as algebraic entities: toward a proof-theory for LCT In [ 14 ] the statement about the need for addressing “contexts as abstract mathematical entities” was set forth. Here, moving from an analysis of contextual categorizations, we developed an account of context interplay based on model theoretic operations. In some sense, we propose a view on contexts as “algebraic entities”. In fact, the following proposition can be proved.

Proposition 2. (Algebra of contexts)

Consider a (global) language L and the set M of all models on that language. Consider then a finite set of sublanguages L1, . . . , Ln of Li. The structure hP(M), ∪, ∩, −, M, ∅, e1, . . . , eni is a Boolean Algebra with operators (BAO) ([ 13 ]). That is, hP(M), ∪, ∩, −, M, ∅i is a Boolean Algebra (BA) and e1, . . . , en are normal and additive operators.

Proof. 1) The fact that the set of all models on a language constitutes a Boolean Algebra is obvious. 2) It is proved in Proposition 1.

This proposition distills the type of conception of context we hold here: contexts are sets of models on different taxonomical languages; on each language the set of possible contexts is structured in a BA; adding operations of focus on a finite number of sublanguages yields a BAO.

The fact that context interplay can be algebraically described has interesting consequences also in the understanding of bridge rules. Characterizing context interplay independently allows to import to context reasoning the standard dichotomy between inference rules which are logical, i.e., modus ponens, and inferehnacvee raulwleasywshbiecehn avrieewinesdteaasdadfoomrmainof-sipnetceirfi-cco,nstuecxhtuaasl ``dααo21m. aIinn-fsapcetc,ifibcridingfeerreunlcees rules which “force contexts to agree up to a certain extent” ([ 7 ]). If contexts are structured, it becomes possible to define logical bridge rules based on that structure. For example, we have that ei(eiM ) =eiM (Proposition 1). In other words, eiM and M are equivalent with respect to what can be expressed in language Li. In symbols: eiM ≡i M . This guarantees the soundness of the following logical bridge rule concerning contextual focus: `fcsi(ξ):γ1vγ2 . That is to say, if `ξ:γ1vγ2 the focus of ξ on Li makes γ1 v γ2 valid, then it is sound to infer that ξ makes γ1 v γ2 valid. Completely analogous rules can be devised in relation with other context operations. The development of a proof-theory for LCT systems based on these intuitions constitutes our main target for future research. We deem it worth stressing, finally, that the notion of logical bridge rule is, as such, independent of our approach. In fact, whenever contexts are seen as objects inserted in a precisely defined mathematical structure (which should not necessarily be a BAO), this type of rules become naturally definable. 5

The scenario revisited

The framework is now put at work formalizing Example 1.

Example 2. (The public park scenario formalized) To formalize the public park scenario within our setting a language LCT is needed, which contains the following atomic concepts: allowed, vehicle, car, bike. Three atomic contexts are at issue here: the context of the main regulation R, let us call it cR; the contexts of the municipal regulations M1 and M2, let us call them cM1 and cM2 respectively. These contexts should be interpreted on two relevant languages. A language L0 for cR s.t. A0 = {allowed, vehicle}; and a language L1 for cM1 and cM2 s.t. A1 = A0 ∪ {car, bike} (an abstract language concerning only vehicles and objects allowed to get into the park, and a more concrete one concerning, besides this, also cars and bicycles). A formalization of the scenario by means of LCT formulas is the following one:

cM1 g0 cM2 4 cR (1) cR : vehicle v ¬allowed (2) (4) cM2 : bike v ¬vehicle (5) cM1 g1 cM2 : bike @ vehicle t allowed (6) Formula (1) plays a key role, stating that the two contexts cM1, cM2 are concrete variants of context cR. It tells this by saying that the context obtained by joining the two concrete contexts on language L0 (the language of cR) is at most as general as context cR. As we will see in discussing the logical consequences of this set of formulas, formula (1) makes cM1, cM2 inherit what holds in cR. Formula (2) formalizes the abstract rule to the effect that vehicles belong to the category of objects not allowed to access public parks. Formula (3) states that in both contexts cars count as vehicles. Formulas (4) and (5) state the two different conceptualizations of the concept of bicycle holding in the two concrete contexts at issue. These formulas show where the two contextual taxonomies diverge. Formula (6), finally, tells that bicycles either are vehicles or should be allowed in the park. Indeed, it might be seen as a clause avoiding “cheating” classifications such as: “bicycles count as cars”.

It is worth listing and discussing some straightforward logical consequences of the formalization. (1), (2)

cM1 : vehicle v ¬allowed (1), (2) (1), (2), (3) cM2 : vehicle v ¬allowed (1), (2), (4) cM1 : bike @ ¬allowed (1), (2), (5), (6) cM2 : bike v allowed These are indeed the formulas that we would intuitively expect to hold in our scenario. The list displays two sets of formulas grouped on the basis of the context to which they pertain. They formalize the two categorizations at hands in our scenario.

Let us have a closer look. The first consequence of each group results from the generality relation expressed in (1), by means of which the content of (2) is shown to hold also in the two concrete contexts. Notice that this reasoning involves an instance of the logical bridge rule sketched in Section 4.2. In fact, cM1 g0 cM2 is equal to fcs0(cM1 g1 fcs0cM2) (Definition 4 and Propostion 1) and since fcs0(cM1 g1 cM2) : vehicle v ¬allowed (1) then cM1 g1 cM2 : vehicle v ¬allowed. In simpler words, contexts cM1 and cM2 inherit the general rule stating that vehicles are not allowed to access public parks. Via this inherited rule, and via (3), it is shown that, in all concrete contexts, cars are also not allowed to access the park. As to cars then, all contexts agree. Where differences arise is in relation with how the concept of bicycle is handled. In context cM1, since bicycles count as vehicles (4), bicycles are also not allowed. In context cM2, instead, bicycles constitute an allowed class because they are not considered to be vehicles (5) and there is no bicycle which does not count as a vehicle and which does not belong to that class of allowed objects (6). 6

Conclusions

We proposed a formal semantics framework able to represent contextual categorizations and enabling an algebraic characterization of context interplay. We observed how this formal perspective naturally grounds the possibility of seeing bridge rules also in a logical, besides a domain-specific, way. The development of an appropriate proof-theory for our semantics constitutes a first aim for future work. Additionally, we intend to investigate the complexity of the framework.

Another line we deem worth exploring consists in evaluating whether, and to what extent, the algebraic approach to context interaction can be actually generalized beyond the analysis of contexts in categorization by means of relaxing some of our assumptions like especially the unique domain assumption.

References

1. V. Akman and M. Surav . Steps toward formalizing context . AI Magazine , 17 ( 3 ): 55 - 72 , 1996 .

2. C. E. Alchourr ´on and E. Bulygin . Normative Systems . Springer Verlag, Wien, 1986 .

3. F. Baader , D. Calvanese , D.L. McGuinness , D. Nardi , and P.F. Patel-Schneider . The Description Logic Handbook . Cambridge University Press, Cambridge, 2002 .

4. M. Benerecetti , P. Bouquet , and C. Ghidini . Contextual reasoning distilled . Journal of Experimental and Theoretical Artificial Intelligence (JETAI) , 12 ( 3 ): 279 - 305 , 2000 .

5. F. Dignum . Agents, markets, institutions, and protocols . In Agent Mediated Electronic Commerce, The European AgentLink Perspective ., pages 98 - 114 . SpringerVerlag, 2001 .

6. F. Dignum . Abstract norms and electronic institutions . In Proceedings of RASTA '02) , Bologna, pages 93 - 104 , 2002 .

7. C. Ghidini and F. Giunchiglia . Local models semantics, or contextual reasoning = locality + compatibility . Artificial Intelligence , 127 ( 2 ): 221 - 259 , 2001 .

8. C. Ghidini and F. Giunchiglia . A semantics for abstraction . In R.L´opez de M´ antaras and L. Saitta, editors, Proceedings of ECAI'2004, including PAIS 2004 , pages 343 - 347 , 2004 .

9. C. Ghidini and L. Serafini . Distributed first order logics . In Frontiers of Combining Systems 2, Studies in Logic and Computation , pages 121 - 140 . Research Studies Press, 1998 .

10. D. Grossi , H. Aldewereld , J. V´azquez- Salceda , and F. Dignum . Ontological aspects of the implementation of norms in agent-based electronic institutions . In Proceedings of NorMAS'05 ., Hatfield, England, april 2005 .

11. D. Grossi , F. Dignum , and J-J. Ch . Meyer. Contextual terminologies . In F. Toni and P. Toroni, editors, Proceedings of CLIMA VI , London, June 2005 .

12. D. Grossi , F. Dignum , and J-J. Ch . Meyer. Contextual taxonomies . In J. Leite and P. Toroni, editors, Proceedings of CLIMA V, LNAI 3487 , pages 33 - 51 . Springer, 2005 .

13. B. J´onsson and A. Tarski . Boolean algebras with operators: Part I . American Journal of Mathematics , 73 : 891 - 939 , 1951 .

14. J. McCarthy . Notes on formalizing contexts . In T. Kehler and S. Rosenschein, editors, Proceedings of the Fifth National Conference on Artificial Intelligence , pages 555 - 560 , Los Altos, California, 1986 . Morgan Kaufmann.

15. J. Searle . The Construction of Social Reality . Free Press, 1995 .

16. Y. Shoham . Varieties of context. pages 393 - 407 . Academic Press Professional, Inc., 1991 .

17. J. V´ azquez-Salceda . The role of Norms and Electronic Institutions in Multi-Agent Systems . Birkhuser Verlag AG, 2004 .