Jérôme Euzenat
email: jerome.euzenat@imag.fr

A categorical approach to time representation first study on qualitative aspects

Keywords: Category theory, time representation, temporal granularity, interval algebra

The qualitative time representation formalisms are considered from the viewpoint of category theory. The representation of a temporal situation can be expressed as a graph and the relationship holding between that graph and others (imprecise or coarser) views of the same situation are expressed as morphisms. These categorical structures are expected to be combinable with other aspects of knowledge representation providing a framework for the integration of temporal representation tools and formalisms with other areas of knowledge representation.

Moreover, knowledge representation formalisms are more and more specialized. However, it is expected that they can be combined in order to represent a complex domain (e.g. for adding temporal extension to objects represented as !-terms [START_REF] Hassan | Towards a meaning of LIFE[END_REF]) in such a way that their mathematical properties are preserved. Once this has been achieved, the attention can turn to the interaction between the formalisms in a particular application.

Category theory [BARR90, PIER91, BORC94] deals with objects (characterized by their structure) and morphisms (preserving the structure). This immediately expresses the notion of approximation of one structure by another. Nonetheless, one of the advantages of category theory is its ability to model the interactions between categories through a variety of operations. These operations can be used to combine the independently designed knowledge representation schemes as soon as they are characterized as categories.

The present communication is a first report on the rephrasing, in categorical terms, of the tools for qualitative time and space representation. The theoretical advantage expected from such a characterization is the expression of the relationship between a qualitative representation of a temporal domain and:

1) a less precise qualitative representation of the same domain; 2) a "deductively closed" qualitative representation of the same domain;

3) a coarser qualitative representation of the same domain.

The final aim of this work is the use of category theory for taking into account the relationship between the qualitative representation of time and its quantitative interpretation. As a matter of fact, there is an immediate relationship between quantitative representations at different scales, a far from immediate relationship between discrete quantitative representations and an expected relationship between granular qualitative representation and discrete quantitative representation (see figure 1). Such a characterization would result in a standard notion of temporal representation combinable with any other knowledge representation formalism.

weakening downward granularity change "qualitativizing" discretizing WGq Wq Gq q Q DQ Figure 1. The relationship existing between different models of the same domain. It depends on the nature of the representation (Quantitative/qualitative), its degree of simplification (Discrete -Granular) and the expressiveness of the language used (Weak). Dashed arrows represent operations which can be achieved in many ways and pending arrows those which can be applied to some type of representation providing a new representation of the same type. Note that arrows and nodes are not categorical notation.

The remainder is a first attempt to settle the qualitative temporal (resp. spatial) representation of some situation as an object and the relationship it enjoys with other representations as morphisms. It can also be understood as an introduction by the example to categorical notions and their applicability to artificial intelligence research. This first picture is under construction and by no means complete: some of the concepts will have to be refined and others modified. This short report is not self-contained: it introduces only minimal definitions (noted meta-definitions) for categorical notions and does not introduce notions on qualitative time and space representation. A first section introduces the qualitative interval representation as an object and considers various kind of morphisms (points 1 and 2 above). Section 2 introduces qualitative granularity as a new kind of morphism (point 3 above). For reason of space, section 3 and 4 are reduced and presents some other potential application of category theory to the field.

1.Approximation in symbolic time representations

Qualitative representation of time (e.g. the interval algebra [START_REF] James | Maintaining knowledge about temporal intervals[END_REF]) represents the temporal situation as a complete directed graph whose nodes are temporal entities (e.g. intervals) and edges the relationship between them. The set of temporal relationships considered can vary with the formalism and is noted " here (e.g. A 13 for Allen relationships). These graphs are considered as the objects of a category ( §1.1). The notion of approximation can be modeled through various kind of morphisms which are considered here ( §1.2 and 1.3).

1.1.Time graphs

The representation of a temporal situation can be made of a graph (called "-graph) whose nodes are the temporal entities and whose edges are labeled with a sub-set of a set ". DEFINITION ("-graph): A "-graph A is a complete directed graph made of a set N A of nodes and a set E A of labeled edges <n 1 ,l,n 2 > such that n 1 ,n 2 #N A , n 1 $n 2 , l%" and l$Ø. Moreover, for each n 1 ,n 2 #N A such that n 1 $n 2 there exists exactly one <n 1 ,l,n 2 >#E A . Such graphs are interpreted as a temporal situation in which the nodes are temporal intervals (places in time) and the labels carry the set of possible temporal relations between the two connected intervals. The constraint about non emptiness aims at ensuring that between any two intervals there is always one possible temporal relation (as it is in time).

A less constrained definition of temporal graphs (made of the same set N A of and a set E A of edges such that for some distinct nodes n 1 and n 2 in N A there exist several edges and for others there exists no edge at all) can be straightforwardly normalized by having the only edge between the nodes being labeled by the intersection of the labels of all the initial edges and ". POSTULATE (temporal representation): the modeled domain can be represented by a "-graph.

Any one will admit that this postulate is assumed by anyone using qualitative time representation.

1.2.More precise representation

A more precise representation of the same situation is understood as a representation with more nodes and smaller labels on the edges. This is expressed through the notion of a "-&-morphism.

D EFINITION ("-&-morphism): A "-&-morphism between two "-graphs A=<N A ,E A > and B=<N B ,E B > is an injective map ' such that: • (n#N A , '(n)#N B , and • (<n 1 ,l,n 2 >#E A , '(<n 1 ,l,n 2 >)=<'(n 1 ),l','(n 2 )> with l'%l.
As defined the relationship between "-graphs introduced by "-&-morphisms is reflexive. Note that the definition of graphs and morphisms could have been carried by a fixed set of nodes N thus only the node labels would have changed through morphisms. This is not the case and henceforth, the "operation" carried out by the morphism consist in (1) restricting the existing labels in the domain and

(2) adding new nodes and edges. Below this is simply called restriction. We now prove that "-graphs and "-&-morphisms form a category.

PROPOSITION 2: The structure made of: 1) a collection of "-graphs (called objects); 2) a collection of "-&-morphism between these objects among which are the id A for each object A; 3) an operator "o" corresponding to function composition; is a category (called "-&-category). This proposition only means that:

• the graph A is an empty restriction of itself, so the restriction of A to B is the same restriction as that from A to A composed with that from A to B; • there is only one way to restrict A to D which does not depend on the intermediate steps.

META-DEFINITION (initial object, terminal object): An object 0 is called an initial object if, for every object A, there is exactly one arrow from 0 to A; an object 1 is called a terminal object if, for every object A, there is exactly one arrow from A to 1. PROPOSITION 3: There is an initial object in the "-&-category, the one with no nodes.

proof. for such an object, there is always a "-&-morphism to any other object and since the restriction is unique, this morphism is also unique. * If we consider the graphs carried by a set of nodes N, then there also is an initial object which is the graph with all edges labeled with ".

In temporal representation, the intuition behind the initial object is the representation which tells nothing about the relationship between the objects. At the opposite, we would like to consider the terminal object as the domain to be modeled. So, each "-graph would be an approximation of that domain. However, this has not been considered here (because non correct graph, with regard to that domain, are allowed). A construction meeting that intuition can be found in [START_REF] Hassan | Towards a meaning of LIFE[END_REF]. It consists in restricting the category to these graphs which are an approximation of the modeled domain representation (the category generated by it). Then the graph matching exactly the reality would be terminal.

In addition, we can also define these objects which are not the domain of any morphism (but their identity arrow). Such objects only have singleton labels (if we do not consider any addition of nodes). They represent an instantiated situation which could be the modeled domain (which is such an object from the postulate). As a matter of fact, all such graphs which are approximated by a particular "-graph exactly correspond to the models of (i.e. the possible real situations represented by) this last graph.

1.3.Constraint resolution

Preciseness seems a natural notion for "-graphs. However, qualitative temporal systems are provided with a deductive operation: the application of transitivity through Allen's composition table [START_REF] James | Maintaining knowledge about temporal intervals[END_REF]. They allow the reduction of the edge labels (thus leading to a more precise "-graph). The deduction made is first shown as a morphism and then the intuition that the result of deduction is more precise is established. So, a new kind of morphism: "is deductible through constraint propagation from" is introduced. D EFINITION ("-+-morphism): A "-+-morphism between two "-graphs A=<N A ,E A > and B=<N B ,E B > is an injective map ' such that:

• (n#N A , '(n)#N B , and

• (<n 1 ,l,n 2 >#E A , '(<n 1 ,l,n 2 >)=<'(n 1 ),l','(n 2 )> such that l' is deducible through constraint propagation from A.
As expected, what is deduced is a more precise graph.

CONSEQUENCE 4: A "-+-morphism is a "-&-morphism (since the deduction process only reduces the labels).

CONSEQUENCE 5: For each "-graph A there exists a "-+-endomorphism id A , such that:

• (n#N, id A (n)=n, and

• (e#E, id A (e)=e (since the labels are deducible from themselves).

PROPOSITION 6: The structure made of: 1) a collection of "-graphs (called objects); 2) a collection of "-+-morphism between these objects among which are the id A for each object A; 3) an operator "o" corresponding to function composition; is a category (called "-+-category).

proof.

a) for any arrow f:A)B, id B o f = f and f o id A = f (since no reduction applied before or after a reduction is always this last reduction); b) for any arrows f:A)B, g:B)C and h:C)D, h o (g o f) = (h o g) o f (since, the deductionby successive application of the transitivity table -can be composed and there is only one way to reduce the graph A directly to the graph D). * This is also easily obtained by adapting the proof that deduction systems are categories (in which objects are formulas and arrows are proofs) [START_REF] Michael | Category theory for computing science[END_REF] to the constraint satisfaction case:

• for any graph, there is an empty proof from itself (id A : A)A), and if there is a proof p of A from B, then p o id B and id A o p are the same proof p; • if there is a proof p of A from B, a proof q of B from C and a proof r from C to D, then, the proofs obtained by chaining r o (q o p) and (r o q) o p are the same.

An attempt can be made for normalizing the graphs such that each graph is represented by its more reduced form through constraint propagation. This can be achieved with the help of a functor mapping each graph to its normal form (provided it is unique). The resulting category would be a sub-category of the initial one.

proof. obvious, through an empty "-'-morphism from 0 to any other "-graph and the impossibility of having a morphism from a non empty graph to 0. * Like in the previous section, there is no terminal object for "-'-categories. This is caused by the possibly infinite chain of new nodes that the granularity changes can add to the graphs. However, if the categories are restricted to be generated by a particular domain restriction then the graph representing the modeled domain should be a terminal object.

An important question would be if granularity changes and deduction can be freely interleaved. However, we proved in [START_REF] Jérôme | Représentation granulaire du temps[END_REF]94] that this is not generally the case.

3.Extension to spatial formalisms

The success of qualitative time representation has led to extensions toward spatial qualitative representations. The more simple are those which considers the space as a Cartesian product of linear representation (such as the one used for time [START_REF] Güsgen | Spatial reasoning based on Allen's temporal logic[END_REF]) or those which consider a space topology as a weakening of the time algebra [START_REF] Max | Reasoning about gradual changes of topological relationships[END_REF][START_REF] David | A spatial logic based on regions and connection[END_REF]. These transformations of the formalism has been used in [START_REF] Jérôme | Granularité dans les représentations spatio-temporelles[END_REF]95] for extending in a straightforward fashion the results of temporal granularity to these space representations. These results can also be expressed in categorical terms (respectively as products of categories and functors).

4.Towards quantitative models

All the temporal representations presented above are supported by an idea of a measurable reality. As a matter of fact, a set of the real number intervals is the natural interpretation of these notions. Thus further work should draw the connection between the "-graphs and their possible models. This can be achieved in the context of category theory (more simply than what have been done for --calculus for instance). The general mechanism for doing this is expressed as "A mathematical theorycorresponding roughly to the definition of a class of mathematical objects -can be usefully regarded as a category of a certain kind, and a model of that theory -one of those objects -as a set-valued functor from that category which preserves the structure." [Lawvere quoted in PIER91]. Once this has been done it must be proved (for any kind of "-morphism) that for any A and B "-graphs, there exists a "-morphism ':A)B if and only if the set of models of A is included in that of B. This has been used, for instance, in [START_REF] Renwei | Application of category theory in model-based diagnostic reasoning[END_REF].

A dual way would consist in beginning with the domain to be modeled as the basic category and defining morphisms from that domain (intervals of real numbers) to the "-graphs. The scaling should as well be characterized in this fashion (see figure 1) and be approximated by granularity.

5.Final note

Seeing the many possible representations of a temporal situation as approximations in the same framework is the contribution of category theory to time representation. It allows to conceive these representations in a uniform way.

This short presentation is subject to debate and some problems will have to be solved before to turn to a full account of time representations including the quantitative approach and/as model theory. For instance, as suggested by one of the reviewers, the treatment of graphs with empty labels is not sound. Such graphs have been rejected here under the justification of avoiding inconsistent graphs. However, there can be inconsistent graphs with no empty label. This is very problematic if one thinks that graphs with empty labels can be deduced through constraint propagation from a valid graph. The rejection of graphs with empty labels has been retained here because such graphs are obviously meaningless. The interpretation of morphisms being approximation, it would be peculiar to consider that the description of any real situation (but that with nothing to represent) is an approximation of something meaningless. Ruling out graphs with empty labels allows to preserve an (informal) idea of potential minimality of the most accurate representation. However, the current situation is not satisfactory.

The author would like to warmly thank the anonymous reviewers for their thoughtful remarks which have not been completely taken into account here due to tight schedules.

CONSEQUENCE 1 :

 1 For each "-graph A there exists a "-&-endomorphism id A , such that: • (n#N, id A (n)=n, and • (e#E, id A (e)=e (with systematically l'=l).META-DEFINITION (Category): The structure made of: 1) a collection of objects; 2) a collection of arrows f:A)B (or morphisms) from an object A (domain) to an object B (codomain); 3) a composition operation "o" assigning to each pair of arrows f:A)B and g:B)C a composite arrow g o f:A)C. such that: a) for each object A there exists an identity arrow: id A :A)A satisfying the identity laws: for any arrow f:A)B, id B o f = f and f o id A = f. b) the composition is associative: for any arrows f:A)B, g:B)C and h:C)D, h o (g o f) = (h o g) o f. is called a category.

  any arrow f:A)B, id B o f = f and f o id A = f (property of the identity function); b) for any arrows f:A)B, g:B)C and h:C)D, h o (g o f) = (h o g) o f (since the composition of label restriction/node addition is possible and there is only one way to restrict node labels and add new nodes such that a graph corresponds to another). *

in: proc. IJCAI workshop on «spatial and temporal reasoning», Montreal (CA),pp145-152, 1995

2.Granularity

The granular representation has been introduced in [START_REF] Jérôme | Représentation granulaire du temps[END_REF]94]. It represents a qualitative temporal situation in the same way as any original qualitative language. However, this representation can differ from the "exact" one since it considers that, under a coarser grain, some objects do not exist anymore (thus changing the labels of the remaining edges). These changes between two different granular representations are defined by an operator , on the set of relations between temporal entities [START_REF] Jérôme | Granularité dans les représentations spatio-temporelles[END_REF].

Thus, a granular representation is expressed as a "-graph exactly as the exact representation and the relationship between representations from different granularities is taken into account as a new kind of morphism ("-'-morphisms). These morphisms correspond to downward granularity change, thus going from a coarse view of the situation to a finer one (with more objects). DEFINITION ("-'-morphism): A "-'-morphism between two "-graphs A=<N A ,E A > and B=<N B ,E B > is an injective map ' such that:

• (n#N A , '(n)#N B , and • (<n 1 ,l,n 2 >#E A , '(<n 1 ,l,n 2 >)=<'(n 1 ),l','(n 2 )> such that l'%,l.

"-morphisms do not prevent new nodes from appearing in the image "-graph; this exactly models the possible vanishing of objects through granularity change. It is also possible that two distinct objects in the domain have the same image; this has an interpretation which is not developed here.

CONSEQUENCE 7: A "-&-morphism is a "-'-morphism (since, by [EUZE95, property (1)], l%,l and l' can be chosen in l).

CONSEQUENCE 8: For each "-graph A there exists a "-'-endomorphism id A , such that: • (n#N, id A (n)=n, and • (e#E, id A (e)=e (since, by [EUZE95, property (1)], l%,l.).

PROPOSITION 9: The structure made of: 1) A collection of "-graphs (called objects); 2) A collection of "-'-morphism between these objects (called arrows A , B of domain A and codomain B) among which are the id A for each object A; 3) An operator "o" corresponding to function composition (the symbol "•" used in [START_REF] Jérôme | Représentation granulaire du temps[END_REF]94,95]); is a category (called "-'-category). There exists a particular "-graph which represents the empty world (so coarse that no object in the modeled domain is relevant). This object is initial.

PROPOSITION 10: "-'-categories have an initial object 0 which is the "-graph <Ø,Ø>.


Cécile Capponi
email: cecile.capponi@imag.fr

Jérôme Euzenat
email: jerome.euzenat@imag.fr

Jérôme Gensel
email: jerome.gensel@imag.fr

Objects, types and constraints as classification schemes (abstract)

Keywords:

The notion of classification scheme is a generic model that encompasses the kind of classification performed in many knowledge representation formalisms. Classification schemes abstract from the structure of individuals and consider only a sub-categorization relationship. The product of classification schemes preserves the status of classification scheme and provides various classification algorithms which rely on the classification defined for each member of the product. Object-based representation formalisms often use heterogeneous ways of representing knowledge. In the particular case of the TROPES system, knowledge is expressed by classes, types and constraints. Here is presented the way to express types and constraints in a type description module which provides them with the simple structure of classification schemes. This mapping allows the integration into TROPES of new types and constraints together with their sub-typing relation. Afterwards, taxonomies of classes are themselves considered to be classification schemes which are products of more primitive ones. Then, this information is sufficient for classifying TROPES objects.

Classification has been formalized for specific languages such as terminological logics (as subsumption), types (as sub-typing) or object representation (as classification). However, when used for applications, practical implementation of such systems are confronted with alien formalisms which do not comply their particular rules. We designed a formalism, classification schemes (CS), aimed at comparing the way these many systems classify. For that purpose the specific syntactic features of the above formalisms are hidden focusing only on what is relevant to classification. Here we present how this can also be used for integrating different notions of classification in the same system. Types and constraints are shown to be CS, thus, provided with a set of types and constraints, objects may be constructed through product operations over CS, grounding the classification operation over objects.

First, the classification scheme formalism is briefly outlined ( §1); then the introduction and management of types and constraints into TROPES are presented in order to show that they are classification schemes ( §2).

Classification schemes

The classification scheme formalism [START_REF] Euzenat | Classification schemes: definitions, properties, algorithms[END_REF] is an attempt to represent, in a very abstract way, the classification activity of any knowledge representation system (thus not only terminological systems). Instead of considering the classification activity to be a consequence of the structure of entities, it considers classification to be primitive and builds on it. CS are first defined. Then, the operations of classification are presented and the way CS can be defined through the operations of degeneration, restriction and product of other CS is presented.

. Taxonomies and classification schemes

Hereafter, taxonomies and CS are defined with regard to a language of categories L C and a language of individuals L I . Individuals have an interpretation as individuals in a modeled domain. Categories are interpreted as sets of individuals. DEFINITION (interpretation). There are two interpretations for a category c:

• the abstract interpretation I A (c) is the set of individuals described by the expression c;

• the real interpretation I R (c) is the set of individuals denoted by c in the modeled domain.

The category description must indeed cover its denotation; this is expressed by the constraint of interpretation inclusion: I R (c) I A (c).

The interpretation may depend on the considered knowledge model (for instance, L I = and L C is the set of integer intervals). The categories are interpreted as representing sets of objects. However, the language in which they are expressed could be inadequate for characterizing them exactly. This is the reason for having two interpretations: the real interpretation corresponds to the set of individuals the category is meant to represent, while the abstract interpretation is the set of individuals the description of the category can represent (for instance, in the language of integer intervals, it is not possible to find a class which describes exactly the set {1, 3}, for that purpose the interval [1..3] whose abstract interpretation is {1, 2, 3} can be used for denoting, or be really interpreted as {1, 3}).

DEFINITION (taxonomy):

A taxonomy C with regard to an interpretation I (abstract or real) is made of a set C of categories and of a partial order relation named sub-categorization ( ) over these categories so that the extension inclusion property is satisfied: c c I( c ) I(c).

A taxonomy reflects the organization of categories in an inclusive structure which enables classification systems to draw inferences such as transitivity of non membership along the sub-categorization relation. Note that this definition does not consider sub-categorization and extension inclusion as equivalent (i. The sub-categorization criterion differs from , which only ranges over C. Often, the sub-categorization relation is a "natural" order over L C (sub-typing or set-inclusion for instance) while has to be built. Pursuing the example above, it means that the category c= [2..4] (with I R (c)={2,3,4}) can be added in the taxonomy such that c [1..4] because [2..4] [1..4] (here, << is ). So, constraining the sub-categorization relation to comply with << -which is defined over L C -ensures that, during the construction of , the extension inclusion property is satisfied.

. 2 Classification

CS attempt to formalize the fact that a taxonomy has an interpretation and is carefully framed by a super-structure whose interpretation can be completely -in the formal meaning of completeness -taken into account by the implementation. They are sufficient to describe the classification operation.

DEFINITION (classification): From a set of categories C (such that C L C ), the classification operation determines the set of categories Cl(i,C)={c C; i I A (c)} under which the individual i is classified.

An individual i can be classified under a category c. Classification aims at finding categories whose real extension contains i; however, this is not mechanically accessible. Then, classification returns the set of categories whose abstract interpretation contains i. However, when abstract and real interpretations coincide, i belongs to the real interpretation of each of the categories. A particular taxonomy can be obtained by starting with an empty taxonomy and adding new categories and relationships respecting <<, but also by starting from the largest possible taxonomy L C << and simplifying it. This is achieved through restriction and degeneration. DEFINITION (restriction and degeneration): A partial order relation over a set S can be defined by the graph whose nodes are elements of S and edges E are the subset of S×S containing all the couples of related elements. The restriction of to a set S' subset of S (noted |S') is the graph S' E' with E' the subset of E whose elements are elements of S'×S'. A degeneration of is a graph S E' such that E' E is closed under transitivity and reflexivity. PROPERTIES: 1) L C << is a taxonomy with respect to I A ; 2) Any restriction of a taxonomy w.r.t. I is a taxonomy w.r.t. I; 3) Any degeneration of a taxonomy w.r.t. I is a taxonomy w.r.t. I. Thus, many taxonomies can be constructed within a scheme and their interpretation is not restricted to be I A .

. 3 Products

The definitions given so far do not account for the way classification is deduced from the structure of the terms. Products provide a foundation for such languages with constructors. DEFINITION (product of classification schemes): Let S 1 ,…S n be a set of classification schemes (for j [1,n], S j = C j j << j is defined upon the languages L C j and L I j ), the product of classification schemes S= × j =1 n S j is defined by

× j =1 n C j << on the languages L C = × j =1 n L C j and L I = × j =1 n L I j such that: c = (c 1 ,Kc n ) × j =1 n L C j , c = ( c 1 ,K c n ) × j =1 n L C j , c << c j [1 n], c j << j c j c = (c 1 ,Kc n ) × j =1 n C j , c = ( c 1 ,K c n ) × j =1 n C j , c c j [1 n], c j j c j
The abstract and real interpretations for classes are simply the sets of individuals which are obtained by the product of the corresponding interpretations of each term of the product. The two constraints define and << as the usual product of partial orders. Note that the languages L I and L C are implicitly defined: they are products of the initial languages. There is only one way to obtain a CS from the same set of initial CS.

PROPERTY: A product of classification schemes is a classification scheme.

The assertions above are proved in [START_REF] Euzenat | Classification schemes: definitions, properties, algorithms[END_REF] in which several classification algorithms for products of CS can also be found.

Objects, types and constraints

So far, a notion of CS has been presented with a well-defined notion of classification over CS. Nevertheless, the quality of being a CS is preserved through the operations of product, degeneration and restriction. This must be related to the object-based knowledge representation system TROPES [START_REF]TROPES 1.0 reference manual, internal report[END_REF]. In TROPES, objects are simply product of values and objects, classes are product of type expressions, classes and constraints and concepts are product of abstract data type (ADT) and concepts. So, if ADT and constraints can be organized in classification schemes (with their classification operations) then so are TROPES concepts (with an immediate classification operation). The types and constraints used in TROPES are presented below.

Types

TROPES allows to use values which are not objects, but requires the typing of these values. These values are members of ADT defined into a type system named METEO [START_REF] Capponi | Identification et exploitation des types dans un modèle de représentation des connaissances par objets[END_REF]. Additionally, METEO provides some polymorphic type constructors such as List or Set.

An ADT T necessarily contains an equality predicate between values of this type (x= T y means that x and y denote the same value for type T), and a typing predicate (x T means that x is a value of the ADT T). In addition, an ADT may define other operators on its values: the order predicates on ordered types (x T y means that x is before y for T), the successor operation for countable types, etc. From such information, METEO performs the encoding of the new ADT and makes it available for TROPES, independently from its implementation.

For instance, a user may want to introduce the new ADT Date whose values are triplets of integers: (year, month, day). Date can be explicitly declared as a countable set of values:

• The user has to specify the two required predicates = Date and Date.

• Since Date is ordered, the user can specify the order relation Date between two values of Date, so that METEO can represent domains of Date values as ranges. • In order to express the fact that Date is countable, the user has to specify some elementary operations and properties, such as the successor operation.

So far, ADT provide a set of objects but no taxonomy. However, the TROPES description language allows to restrict a slot type through domain descriptors: domain restrict the possible values to a particular sub-set, range, to a particular set of intervals, card, to a particular cardinality, and so on [START_REF]TROPES 1.0 reference manual, internal report[END_REF]. For dealing with these expressions METEO carries out two main operations:

• normalization (or equality computation) which establishes a unique form from a particular type expression;

• sub-type computation which establishes wether the extension of the first type expression includes that of a second one. The internal representation of type expressions depends on the kind of ADT considered: for instance if Integer is defined as enumerated, the type expressions will be sets, but if it is defined as ordered, they will be list of closedbound intervals. Similarly, normalization and sub-type computation between type expressions of an ADT, depend on the necessary predicates of the ADT ( T and = T ), and eventually from other predicates such as T . For instance, subtype computation is obtained by checking the inclusion between two lists of closed-bound intervals.

Types constructed with the same constructor from the same primitive type are disposed in a lattice whose partial order relation is sub-typing and whose greater element is the referred ADT [START_REF] Capponi | Interactive class classification using types[END_REF]. METEO performs the dynamic management of the type lattice associated to the primitive type (e.g. insertion and deletion of type, computation of the greatest lower bound). Furthermore, it provides algorithms in order to manage links of composition established between different type lattices, thus type modifications are dynamically propagated along these links.

Types introduced in TROPES provide elementary CS from which more complex ones are built. For a primitive type T, L I corresponds to the values of the type and L C corresponds to the set of equivalence classes of type expressions for normalization. The set of categories C is the result of the normalization of the type expressions used in concept expressions augmented in order to be a lattice. The sub-categorization criterion is the sub-typing relation over the whole L C while the sub-categorization relation is its restriction to C. Then types are interpreted as sets (domains) and sub-typing as set inclusion. The real and abstract interpretation are the same and range over the normalized type expressions. Thus, METEO is able to associate with a primitive type T the behavior of a CS, i.e. it provides the computation of the sub-categorization criterion and relation.

For instance, the type Integer determines a CS in which L I is and L C is the set of sets of intervals interpreted as its powerset. The sub-categorization criterion is sub-typing and the normalization operation ensures that the taxonomy is exactly the restriction of 2 to the sets which are necessary to provide it with a lattice structure (i.e. the theoretical lattice over the powerset of integers restricted to sets relevant to the application).

. Constraints

A constraint is interpreted as in Constraint Satisfaction Problems (CSP) [START_REF] Mackworth | Consistency in networks of relations[END_REF]. A CSP considers a set of n variables v j with associated domains d j and a set of relations r i . A relation r i (v i1 , v i2 , …, v im ) is a sub-set of the Cartesian product of the domains D i1 ×…×D im (where D ik is the domain of a variable v ik constrained by r i ). A constraint in a class is a declarative statement which expresses a relation that holds between several fields of this class.

In TROPES, both unary constraints and n-ary (where n > 1) constraints can be defined and set up among the fields of one or several objects. A unary constraint consists of a predicate which extends the field type description. A n-ary constraint corresponds to a relation which must hold between n fields of a class. These two kinds of constraints are necessary conditions that every member of the class must satisfy. Constraints of different kinds are expressed in intension and correspond to basic constraint functions. These basic constraint functions are combined to form more complex constraint expressions. Besides classical constraints, i.e. numerical constraints based on a comparison (=, <, >, , , ) of arithmetic expressions built with the operators (+, -, *, /, ^, log, exp, sin, cos, etc.), more specific ones are available like constraints on sets or lists of values of any types, or like conditional constraints.

A constraint programming module, called MICRO [START_REF] Gensel | Integrating constraints in an object-based knowledge representation system[END_REF], has been designed for TROPES. It handles CSP whose domains are enumerated sets or intervals. Thus, domains may be finite or infinite. MICRO takes advantage of the presence of METEO to propose generic constraints (constraints whose predicate depends on the type of the variables). It includes a constraint propagation algorithm (which achieves arc-consistency [START_REF] Mackworth | Consistency in networks of relations[END_REF] for monotonous operators used in constraint expressions).

In order to guarantee sub-typing of constrained fields between a class and its sub-classes, constraints must be inherited from one class to its sub-classes. Then, the final set of constraints of a class results from the union of the proper set of constraints of this class and of the set of constraints of its super-classes. However, this constraint inheritance should not be systematic, particularly when redundant constraints of class are defined. A constraint to be added to a class is said to be redundant with regard to the current set of constraints when, either it can be obtained after simplification or derivation from the current set of constraints, or its predicate is implied by a conjunction of predicates stemming from the current set of constraints. Indeed, redundancy can be expressed as a set-inclusion between relation extensions. If two n-ary predicates P and Q defined on the same Cartesian product of primitive domains D=D 1 ×…×D n are so that the set of n-uples satisfying P is a sub-set of those satisfying Q, then, a sub-typing relation D between P and Q (such that P D Q) can be considered on D. This sub-typing relation allows to organize the structures representing constraints in a taxonomy.

Since TROPES cannot compare extensions of predicates (simply because they might be infinite) nor their intension, it has to be provided with information concerning sub-categorization of constraints. The user does it by declaring the taxonomy of constraints. TROPES does not automatically maintain the sub-categorization between these constraints. The system is only able to check these constraints for satisfaction. The user is free to organize the constraints with a sub-categorization relation.

This constitutes the classification schemes tied to constraints: a particular constraint r over the variables v 1 ,…v n with domains D 1 ,…D n is easily included in a CS whose L I is the Cartesian product of domains D=D 1 ×…D n and L C is a set of predicate which recognize sub-sets of D (thus sub-sets of L I ). C is simply the set of expressed predicates (thus containing c). As for types, the abstract and real interpretations coincide and range over D. The subcategorization criterion is interpreted as the inclusion of the predicate extension (note that this is not accessible by the program) and the sub-categorization relation its restriction to C expressed by D . Thus, it is possible to use this CS in the classification operation and even if the constraints use classic constraint satisfaction algorithms for deciding if c is satisfied of a tuple of variable (resp. if that individual belongs to the abstract interpretation of the c category), the external behavior of the CS remains.

Conclusion

The extension facilities of the TROPES knowledge representation system have been presented. Type definitions through ADT are very straightforward with regard to the kind of type expressions and inference they allow. So, TROPES can manipulate external expressions in a minimal fashion without having to access the semantics of these expressions. Types and constraints have been characterized as classification schemes. More elaborate CS such as TROPES concepts are justified only because they result from the combination (product, restriction, weakening) of these more simple CS which always produces new CS. Thus, thanks to the CS formalism, TROPES is able to perform classification (but also class classification which has not been presented here).

The problem has been addressed by others in the framework of terminological logics [START_REF] Baader | A scheme for integrating concrete domains into concept languages[END_REF][START_REF] Borgida | PROTODL: a customizable knowledge base management system[END_REF][START_REF] Gaines | A class library implementation of a principled open architecture knowledge representation server with plug-in data types[END_REF]. But, the extendibility mechanisms are not as general as CS. For instance, organizing constraints into a taxonomy as presented here requires the possibility of having non complete relationship between constraints: this is not possible with definitional categories. Implementing the CS principles allow both easy extension and simple classification algorithms. This could affect performances, however the algorithm relies, finally, on the algorithms provided for each type and constraint satisfaction. It is expected that this has better performances than the complete expression of the basic types in the representation formalism.

  e. c c / I( c ) I(c)): this allows non-exclusive categories. DEFINITION (classification scheme): A classification scheme C << over a couple of languages L C and L I is given by a set of category (C), a sub-categorization relation ( ) and a sub-categorization criterion ( <<), such that: • L C << is a taxonomy with regard to the abstract interpretation, • C is a taxonomy with regard to the real interpretation, and • c, c C, c c c << c .


Petko Valtchev
email: petko.valtchev@imag.fr

Jérôme Euzenat
email: jerome.euzenat@imag.fr

Classification of concepts through products of concepts and abstract data types (abstract)

Introduction

Object-based systems offer the opportunity of representing and organizing knowledge into taxonomies of classes. Therefore the application of some data analysis techniques, and precisely the automatic classification algorithms, may be useful for such systems. However, the immediate application of classification algorithms involves a preliminary coding and the reverse decoding stages which may introduce some loss of information [START_REF] Euzenat | Brief overview of T-TREE: the TROPES Taxonomy building Tool[END_REF]. In addition, the data analysis approach, in spite of its undeniable virtues, does not provide a "conceptual" description of the classes [START_REF] Michalski | Learning from observation: conceptual clustering[END_REF][START_REF] Diday | Quelques aspects de l'analyse des données symboliques[END_REF]. A possible way to avoid these flaws is the use of a conceptual clustering algorithm provided with some further abilities to take into account ordered structures. We present here a way to perform a classification of a set of objects on referring to taxonomies of other objects and hierarchies of externally defined types.

We first present the TROPES system and its manner to handle external and primitive types and extend them with a dissimilarity definition. Then, a possible formalization of the taxonomy building process in terms of classification schemes is given. Next, we show the relationship between dissimilarity and class taxonomies. Finally, we give a brief description of a practical classification procedure using concept taxonomies in a bottom-up strategy.

Concepts and ADT in TROPES

TROPES is an object-based knowledge representation model. The individuals are represented as objects. The collection of all objects is partitioned into a set of concepts. A concept describes the fields of the objects it represents. Each field is a map from an object to a "value" where the domain is the concept that object belongs to while the co-domain is either another concept or an abstract data type (see below). Thus, an object can be seen as a collection of field values (either objects or values). A class describes a subset of concept objects through refinements of field types (the field types are either classes or type expressions).

In TROPES, primitive values (which can be constructed but their construction is not accessible to TROPES) are associated with types. Some of them are quite standard (Integers, Booleans...), whereas others are more elaborate (Date, Nucleic acid sequence...). Each of these types is introduced independently from its implementation by an abstract data type (ADT). The ADT for a primitive type T contains an equality predicate between values of this type (= T ), a typing predicate (!T) and, sometimes, an order relationship (" T ).

In order to enable the comparison between values of such types, the ADT are enhanced with a dissimilarity measure. It takes into account the type structure in the ADT, either explicit or unexpressed. For instance, the dissimilarity of two values in a totally ordered discrete type (such as integers) may be defined as the number of intermediate values according to the order (" T ). A more general dissimilarity ranging over type expression instead of single values may be defined.

The structure of ADT can be mapped into that of concepts (see Fig. 1) and what holds for ADT holds for concepts. Thus each concept can be though of as a Cartesian product of ADT and other concepts, more elementary ones. Carrying on with this idea a class may be seen as a product of classes and types while an object becomes a tuple made of objects and values.

This analogy may be enhanced to integrate the dissimilarity. Given a concept K, its extension O K and a set C K of classes defined over O K and organized in a taxonomy (this set is thus structured into a hierarchy " K ), a dissimilarity measure can be introduced. First, a conventional object dissimilarity lying on the field values may be defined. Second, one may also introduce the class dissimilarity # K as an index measured over the hierarchy (# K : C K ×C K $" which is, for instance, some distance inherent to the hierarchy). Analogy between concepts and ADT. How do the above ideas fit in the classification landscape? The compositional vision introduced hereby may be exploited by a classification algorithm. As soon as the sub-structures are provided with their own taxonomies (and the associated dissimilarities) the algorithm should combine them to build a taxonomy in the superstructure. The first attempt to implement similar ideas was an extension of CLUSTER [START_REF] Michalski | Learning from observation: conceptual clustering[END_REF] which uses a dissimilarity between two field values, regardless of their nature -ADT values or objects. This way it is possible to process the structure in the initial data with no extra reformulating efforts.

However, the uniform dissimilarity computation is a rather modest gain compared to the tight analogy between concepts and ADT. To take much more advantage of such an analogy, a common framework to clarify the shared structure has to be designed. For that purpose, we use the classification scheme model.

Classification Schemes

A classification scheme is an abstract model of a class taxonomy. Each classification scheme is defined with regard to a language of individuals L I and a language of categories L C . The elements of the first one are interpreted as the entities of a domain to model. The categories have, in turn, two possible interpretations, both as sets of individuals. The abstract interpretation includes all the individuals the category could represent while the real interpretation contains only those effectively denoted by the category in the modelled domain. In that context, a taxonomy, with respect to an interpretation, is defined by a category set provided with a partial order. The condition to link the category interpretation to the order relation, called extension inclusion property is the following: each time a couple of categories satisfies the partial order predicate a set inclusion between the corresponding interpretations holds. We can now give the definition of a classification scheme which may be roughly compared to a superposition of two taxonomies. More formally, a classification scheme over a couple of languages L C and L I is given by a set of categories (C % L C ) and two partial orders: a subcategorisation relation and a sub-categorisation criterion. The sub-categorisation relation constitutes a taxonomy over C with respect to the real interpretation. So does the subcategorisation criterion over the entire L C and with respect to the abstract interpretation. Furthermore, each time the sub-categorisation relation holds for a couple of categories in C the sub-categorisation criterion must hold too [START_REF] Euzenat | Une définition abstraite de la classification et son application aux taxonomies d'objets, proc. 2ndes journées représentation par objets (RPO)[END_REF].

Classification schemes are constructed from more elementary ones through products. A product is defined over a set of classification schemes in the following way. Both L C and L I of the product are obtained through Cartesian product of the corresponding languages of the basic classification schemes. In a similar way, the partial orders of the product, both the subcategorisation criterion and the sub-categorisation relation, are defined as order products. We proved [START_REF] Euzenat | Une définition abstraite de la classification et son application aux taxonomies d'objets, proc. 2ndes journées représentation par objets (RPO)[END_REF] the following result: a product of classification schemes is a classification scheme. The reverse operation, called projection, is defined too. It singles out one or more classification schemes within a product. This way, the extraction of a field value from a given object is modelled by a unitary projection.

Both operations constitute the theoretical basis for the TROPES bottom-up concept construction. This way, ADT in TROPES are elementary classification schemes where both orders coincide. Concepts are, in turn, products of classification schemes representing ADT or other concepts.

The main advantage the classification scheme model provides is the homogeneous manner the different sub-structures of a concept are accounted for. This homogeneity has a direct impact on usually performed manipulations over taxonomies like the identification of individuals or the classification of a conceptually described class. For instance, the identification of a constructed object is performed within a product of more elementary classification schemes. The object compounds are identified under the corresponding more elementary classification schemes obtained by projection. The results at the lower levels (corresponding to a concept or an ADT) are used to compose (through product) the global result. Notice that the distinction between concepts, ADT for dense infinite types or ADT for finite ordered types is hidden for the identification algorithm which only manipulates categories and predicates. Our idea was to apply the same principles of overall homogeneity to the automatic classification.

Dissimilarity

The complete integration of automatic classification algorithms into the above model requires that model to be extended. We need it, at first, to integrate such a fundamental notion as the dissimilarity between individuals.

In other words we should find a generic dissimilarity measure to hold within a classification scheme. It means that the new measure should be based exclusively upon the taxonomy structure. In addition, we would like it to cover some well-known measures used in particular situations. Those requirements taken into account, we designed what we called the "topological distance". The basic idea is to explore, for a product, the taxonomy structures within the classification schemes-compounds. The dissimilarity between a couple of individuals within the product is the total of their unitary projection dissimilarities. The point is that those projection dissimilarities are computed over the corresponding taxonomy. An exact description of the way the new dissimilarity is computed follows.

First, let us assume that we have to compute the dissimilarity for K, a product of n classification schemes all of them provided with a taxonomy. Let now compare two individuals, say e and e'. Let the corresponding unitary projections be e i and e i ' (i = 1..n) respectively. The dissimilarity between e and e' is given as

d K (e, e') = & i=1..n #(e i , e i ').
The substantial role in the above formula is played by the # function, computed in the same way over each projection. We set it to measure the gap between its parameters over the graph generated by the taxonomy 1 . The value of # is proportional to the shortest paths from both parameter nodes to their most specific common category. Actually the mean of those path lengths is taken. The final value is obtained after a normalisation using the greatest chain length within the graph.

Our definition is valid each time a unique most specific common super-category for arbitrary couple of categories in the taxonomy exists. In other words, we need at least an upper semilattice structure to apply the above measure. Otherwise an extension of the latter to compute the least paths length sum among all possible has to be applied.

Another question one may rise concerns the features of the defined dissimilarity. It is easy to see that the # function is a valid dissimilarity measure. In fact, it is positive, symmetric and it equals 0 each time both parameters are identical. The sum operator preserves those properties, so d K is a valid measure too. Furthermore, when the corresponding taxonomy is a tree, # is a distance function since it respects the triangle inequality.

Classification Algorithm

The previously presented dissimilarity may be integrated in various taxonomy building algorithms. One of the possible applications is described hereafter. In TROPES the set of all concepts and ADT is virtually organised in a (concept) dependency graph. Provided the corresponding classification schemes are considered instead, the vertices of that graph connect the products to their compounds. The dependency graph is clearly an oriented and circuit-free one.

The algorithm is a composition of several functionality levels. The top level explores the dependency graph from a chosen classification scheme downwards. This is made in a depthfirst post-fix manner, testing at each node the availability of a taxonomy within the corresponding classification scheme. The nodes that score positively for that test (these are typically ADT and some elementary concepts) receive no further treatment. They draw the limits of the exploration, providing in the same time the basis for the automatic classification in higher nodes. At each of the remaining nodes reached by the algorithm the exploration carries on with the successors in the graph. Once all of those successors has been thoroughly processed, that is a taxonomy is available (either already existing or built within a previous step) the automatic classification of the current node may start. It constitutes a second level of our algorithm. The underlying procedure combines the taxonomies over the substructures of the concept by the product operation to obtain a prototype of the future taxonomy to validate. The dissimilarity measure between the objects and the proto-categories is used to obtain a simpler and more "plausible" taxonomy. It allows only the high-scored proto-categories to be retained. The resulting taxonomy, in turn, induces a new dissimilarity measure on the set of the concept objects.

As we noted above, we have been working on CLUSTER to make that algorithm stick with an objet-based model like TROPES. Later on, the underlying star algorithm showed to be fairly well adapted to the classification scheme formalism and the product/projection duality. So we came to a extension of CLUSTER based upon the new metrics and the notion of classification scheme product. That modification is what we currently use as a taxonomy building routine in the above algorithm.

What are the advantages of our algorithm from the (conceptual) clustering viewpoint? First, our algorithm deals with compound objects. That kind of treatment is offered at a reduced computational cost. Instead of recursively computing the dissimilarity between each pair of objects referenced, the dissimilarity depends only on their position in the corresponding taxonomy. Another advantage of this approach is the availability of immediate category descriptions through the classification scheme product operation. We thus combine a "conceptual" clustering with an extendible type system. Next, objects are treated with their original structure. Compared with CLUSTER/S, a typical algorithm exploiting the structure in the data, we use no flattering stage.

At that moment we can draw a list of possible extensions our approach would support. One of them concerns the classification with regard to several taxonomies over the same concept. Each taxonomy in this case constitutes what we call a viewpoint. The viewpoints are assigned a classification scheme each and it is often profitable to treat those classification schemes in a single global one. Another extension we think about concerns the type constructors. So far we have considered only single-valued fields. In TROPES, however, the type system supports multi-valued attributes. The latter are realised through constructors like lists and sets. Processing correctly lists and sets attributes is mandatory for any classification algorithm to fully integrate the type system in TROPES.

There are some limitations to our approach, and namely, the possibility of having concepts -indirectly -referring to themselves is not dealt with. Some ideas about the way that kind of data can be processed are given in [START_REF] Bisson | Why and How to Define a Symilarity Meaure for Object-Based Representation Systems[END_REF].

  Fig.1. Analogy between concepts and ADT. How do the above ideas fit in the classification landscape? The compositional vision introduced hereby may be exploited by a classification algorithm. As soon as the sub-structures are provided with their own taxonomies (and the associated dissimilarities) the algorithm should combine them to build a taxonomy in the superstructure. The first attempt to implement similar ideas was an extension of CLUSTER[START_REF] Michalski | Learning from observation: conceptual clustering[END_REF] which uses a dissimilarity between two field values, regardless of their nature -ADT values or objects. This way it is possible to process the structure in the initial data with no extra reformulating efforts.However, the uniform dissimilarity computation is a rather modest gain compared to the tight analogy between concepts and ADT. To take much more advantage of such an analogy, a common framework to clarify the shared structure has to be designed. For that purpose, we use the classification scheme model.Classification SchemesA classification scheme is an abstract model of a class taxonomy. Each classification scheme is defined with regard to a language of individuals L I and a language of categories L C . The elements of the first one are interpreted as the entities of a domain to model. The categories have, in turn, two possible interpretations, both as sets of individuals. The abstract interpretation includes all the individuals the category could represent while the real interpretation contains only those effectively denoted by the category in the modelled domain. In that context, a taxonomy, with respect to an interpretation, is defined by a category set provided with a partial order. The condition to link the category interpretation to the order relation, called extension inclusion property is the following: each time a couple of categories satisfies the partial order predicate a set inclusion between the corresponding interpretations holds. We can now give the definition of a classification scheme which may be roughly compared to a superposition of two taxonomies. More formally, a classification scheme over a couple of languages L C and L I is given by a set of categories (C % L C ) and two partial orders: a subcategorisation relation and a sub-categorisation criterion. The sub-categorisation relation constitutes a taxonomy over C with respect to the real interpretation. So does the subcategorisation criterion over the entire L C and with respect to the abstract interpretation. Furthermore, each time the sub-categorisation relation holds for a couple of categories in C the sub-categorisation criterion must hold too[START_REF] Euzenat | Une définition abstraite de la classification et son application aux taxonomies d'objets, proc. 2ndes journées représentation par objets (RPO)[END_REF].Classification schemes are constructed from more elementary ones through products. A product is defined over a set of classification schemes in the following way. Both L C and L I of the product are obtained through Cartesian product of the corresponding languages of the basic classification schemes. In a similar way, the partial orders of the product, both the subcategorisation criterion and the sub-categorisation relation, are defined as order products. We proved[START_REF] Euzenat | Une définition abstraite de la classification et son application aux taxonomies d'objets, proc. 2ndes journées représentation par objets (RPO)[END_REF] the following result: a product of classification schemes is a classification scheme. The reverse operation, called projection, is defined too. It singles out one or more classification schemes within a product. This way, the extraction of a field value from a given object is modelled by a unitary projection.Both operations constitute the theoretical basis for the TROPES bottom-up concept construction. This way, ADT in TROPES are elementary classification schemes where both orders coincide. Concepts are, in turn, products of classification schemes representing ADT or other concepts.The main advantage the classification scheme model provides is the homogeneous manner the different sub-structures of a concept are accounted for. This homogeneity has a direct impact

To construct that graph we extend the taxonomy by connecting the individuals to their most specific categories. This way we obtain an oriented circuit-free graph.


Jérôme Euzenat
email: jerome.euzenat@imag.fr

An algebraic approach to granularity in time representation

Any phenomenon can be seen under a more or less precise granularity, depending on the kind of details which are perceivable. This can be applied to time. A characteristic of abstract spaces such as the one used for representing time is their granularity independence, i.e. the fact that they have the same structure at different granularities. So, time "places" and their relationship can be seen under different granularities and they still behave like time places and relationship under each granularity. However, they do not remain exactly the same time places and relationship. Here is presented a pair of operators for converting (upward and downward) qualitative time relationship from one granularity to another. These operators are the only ones to satisfy a set of six constraints which characterize granularity changes.

. Introduction

"Imagine, you are biking in a flat countryside. At some distance ahead of you there is something still. You are just able to say (a) that a truck (T) is aside a house (H), it seems that they meet. When you come closer to them (b) you are able to distinguish a bumper (B) between them, and even closer (c), you can perceive the space between the bumper and the house."

This little story shows the description of the same reality perceived at several resolution levels: this is called granularity. Granularity would not be a problem if different individuals, institutions, etc. would use the same granularity. This is not the case and, moreover, these individuals communicate data expressed under different granularities. There could be a problem if, for instance, someone at position (a), asked "how would you call that which is between H and T?" because at that granularity, the description of the scene would assume that there is nothing between H and T. The study of granular knowledge representation thus tries to express how the same phenomenon can, in some sense, be consistently expressed in different manners under different granularities. This is achieved through operators which, for a situation expressed under a particular granularity, can predict how it is perceivable under another granularity. Granularity can be applied to the fusion of knowledge provided by sources of different resolution (for instance, agents -human or computers -communicating about the same situation) and to the structuring of reasoning by drawing inference at the right level of resolution (in the example of figure 1, the first granularity is informative enough for deciding that the truck driving wheel is on the left of the house -from the standpoint of the observer).

On one hand, in [START_REF] Hobbs | Granularity[END_REF], granularity is expressed granularity between two, more or less detailed, logical theories. On the other hand, the physical time-space and its representation have been well-studied because many applications require them. A very popular way to deal with time is the representation of relationships between time intervals [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF]. To our knowledge, qualitative time granularity has never been studied before. Jerry Hobbs [START_REF] Hobbs | Granularity[END_REF] introduced granularity in an abstract way (i.e. not connected to time) and [START_REF] Montanari | Dealing with time and granularity in the event calculus[END_REF][START_REF] Ciapessoni | Embedding time granularity in a logical specification language for sychronous real-time systems[END_REF] introduced operators for quantitative time granularity which share a common ground with ours (see §7).

The paper first recalls some basics about time representation ( §2). This section can be skipped by those who already know the subject. Then, the usual interpretations of time and granularity in this context are introduced. Afterwards, required properties for granularity change operators in the classical time algebra are presented ( §3). This part is very important since, once accepted the remainder is directly deduced. The only set of operators (for instant and interval algebra) satisfying the required properties are thus deduced in §4. The results concerning the relationship between granularity and inference are then briefly presented ( §5).

The proofs of all the propositions, but the "only" part of the first one, can be found in [START_REF] Euzenat | Granularité dans les représentations spatio-temporelles[END_REF]. The main results (but those of §5) are from [START_REF] Euzenat | An algebraic approach to granularity in qualitative time and space representations[END_REF].

. Background

Classical notions about temporal algebras, neighborhood structures and instant-interval conversions are presented here.

Temporal algebra

There has been considerable work carried out on qualitative time representation. We recall here several notions about the algebra of topological and vectorial relationships holding between time entities.

An instant is a durationless temporal entity (also called time point by analogy with a point on a line). It can be numerically represented by a date. Qualitatively representing these instants requires identifying them and putting them in relation. There are three possible mutually exclusive relationships between instants. They are called «before» (<), «after» (>) and «simultaneously» (=). The set {<, =, >} is called A 3 .

relation (r): x1 r x2 x1/x2

reciprocal: x2 r -1 x1 before (<) after (>) simultaneously (=) = The composition operator × 13 is represented by a composition table [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF], similar to the table 2, which allows to deduce, from a set of intervals and constraints between these intervals, the possible relations between any two of these intervals.

× 3 > = < > > > < = > = > = < < < = > < <

Extensions of notations

Let ! be either A 1 3 or A 3 , " be the logical disjunction and × be the composition operator on !, the following notations are used (in a general manner, <2 ! # ×> is an algebra of binary relationships). The lack of knowledge concerning the actual position of some temporal entity x with regard to the temporal entity y is expressed by a sub-set $ of ! which is interpreted as the disjunction of the relations in $:

x$y = r%$ " xry Thus, x{b m}y signifies that the temporal entity x is anterior to or meets the temporal entity y. The following conventions are used below:

• When a result is valid for both algebras, no distinction is made between the temporal entities concerned. The base sets (A 13 , A 3 , and maybe others), as well as the composition × and reciprocity -1 operators are not distinguished;

• The letter $ represents a sub-set of the corresponding base set of relations ($#!); the letter «r» represents a relationship. • $ -1 represents the set of relations reciprocal of those contained in $: {r -1 ; r%$}. • $ 1 ×$ 2 represents the distribution of × on ":

$ 1 × $ 2 = r 1 × r 2 r 1 %$ 1 ,r 2 %$ 2 U 2.

Neighborhood structure

Two qualitative relations between two entities are called conceptual neighbors if they can be transformed into one another through continuous deformation of the entities [START_REF] Freksa | Temporal reasoning based on semi-intervals[END_REF]. A conceptual neighborhood is a set of relations whose elements constitute a connected subgraph of the neighborhood graph. for the deformation corresponding to the move of an extremity of an interval (more generally, the deformation corresponds to moving a limit). Throughout the paper, the only considered transformation A is the continuous move of a limit (called A-neighborhood in [START_REF] Freksa | Temporal reasoning based on semi-intervals[END_REF]). The influence of this choice is acknowledged when it matters.

DEFINITION (conceptual neighborhood

Conversion from interval to instant formalisms

Relationships between intervals can be expressed in function of the relationships between their bounding instants (see table 4): any relationship between x=<x - x + > and y=<y -y + > is expressed by a quadruple (r 1 , r 2 , r 3 , r 4 ) of relationships between the extremities defined as so:

<x -x + > (r 1 , r 2 , r 3 , r 4 ) <y -y + > x -r 1 y -& x -r 2 y + & x + r 3 y -& x + r 4 y +
considering that x -< x + and y -< y + , each possible relationship between the bounding instants are expressible with such a quadruple (see table 4). The symbol ' is used such that 'x is the expression of an interval as a couple of extremities and 'r a relationship between intervals expressed as a quadruple. ' is extended towards sets of relations such that '$ is a set of quadruples. Thus:

< x ( x + > r i1 , r i2 , r i3 , r i 4 ( ) { } i =1 n U ) * + , - . < y ( y + > / i =1 n " x ( r i1 y ( & x ( r i2 y + & x + r i3 y ( & x + r i 4 y + xry x -r 1 y - x -r 2 y + x + r 3 y - x + r 4 y + b < < < < d > < > < o < < > < s = < > < f > < > = m < < = < e = < > = m -1 > = > > f -1 < < > = s -1 = < > > o -1 > < > > d -1 < < > > b -1 > > > >
Table 4. The 13 relationships between intervals expressed through relationships between interval extremities.

Since any formula representing relationship between four instants x -, x + , y -and y + respecting the properties of intervals (x -<x + and y -<y + ) can be expressed under that form, the inverse operation 0 is defined. It converts such an expression between bounding instants of two intervals into a set of relations expressing the disjunction of relations holding between the intervals. Of course, both operators (0 and ') are inverse.

. Requirements for granularity change operators

We aim at defining operators for transforming the representation of a temporal situation from one granularity to another so that the resulting representation should be compatible with what can be observed under that granularity. The requirements for building such operators are considered here. The first section concerns what happens to classical models of time and to temporal entities when they are seen through granularity.

The second one provides a set of properties that any system of granularity conversion operators should enjoy. These properties are expressed in a sufficiently abstract way for being meaningful for instants and periods, time and space.

Granularity change operators

Time is usually represented under a particular granularity. Thus, the time representation system presented so far is an adequate representation for time at any granularity (as far as only qualitative properties are considered). For instance, the three situations of figure 1 can be expressed in the same formalism with objects and qualitative relations between them. If we only consider the position of the objects along the horizontal line, the three elements (T, B and H) are related to each other in the way of figure 1c by T{m}B (the truck meets its bumper) and B{b}H (the bumper is before the house).

We aim at elucidating the relationship between two representations of the same reality under two different granularities. As a matter of fact, the situations of figure 1 cannot be merged into one consistent situation: figures 1b and c together are inconsistent since, in (b), B{m}H and, in (c), B{b}H which, when put together, gives B{}H. First, the reasons for these problems are examined before providing a set of properties that granularity change operators must satisfy.

Time is usually interpreted as a straight line, instants as points and intervals as segments. Under a numerical light, granularity can be defined as scaling plus filtering what is relevant and what is not (discretizing). However, granularity is a special filter since, as the name indicates, it filters on size. For the time concern, the granularity of a system can be defined as the duration of the smallest relevant event (relevance being defined independently beforehand). But what happens to non relevant events? There are two solutions:

• they can vanish; • they can remain with size 0, i.e. as instants. In both cases, these solutions share additional consequences (for symbolic representations): if, under a coarse granularity, one observes that some event is connected to another this can be wrong under a finer granularity since a non relevant laps of time could be relevant here. In another way, when communicating the same observation, it must be taken into account that the short laps of time may be non relevant (and thus that the relationship between the event can be disconnected). This is what happened for the relationship between B and H, which is {b}, in Figure 1c, and becomes {m}, in 1b.

In order to account for this situation, which appears to be regular, we need a downward (resp. upward) operator which, from a relationship observed a some particular granularity, is able to provide a set of relationships at a finer (resp. coarser) granularity which represents what can be perceived under that last granularity. The purpose here, is not to design granularity conversion operators which can make events vanish or turn into instants (see [START_REF] Euzenat | Représentation granulaire du temps[END_REF]) but rather operators which can account for the possibility of having, under a finer granularity, new space between two entities, and, vice-versa, that a space can become non relevant under a coarser granularity. These operators are called upward and downward granularity conversion operators and noted by the infix g 1 g' and g' 2 g operators (where g and g' are granularities such that g is finer -more precise -than g', i.e. that the size of relevant events is smallest in g than in g'). The following g3g' operator will be used for any of them when the property holds for both (then there is no constraint upon g and g'). As usual, the notation g3g' introduced for the conversion of a single relationship is extended towards sets:

g3g' $ = g 3 g' r r%$ U .

Properties for granularity change operators

Anyone can think about a particular set of such operators by imagining the effects of coarseness. But here are provided a set of properties which should be satisfied by any system of granularity conversion operators. In fact, the set of properties is very small. But next section shows that they are sufficient for constraining the possibility for such operators to only one (plus the expected operators corresponding to identity and conversion to everything).

Self-conservation

Self-conservation states that whatever be the conversion, a relationship must belong to its own conversion. It is quite a sensible and minimal property: the knowledge about the relationship can be less precise but it must have a chance to be correct.

(1) r % g3g'r (self-conservation)

Neighborhood compatibility

A property considered earlier is the order preservation property [START_REF] Hobbs | Granularity[END_REF] which states (a part of this):

x > y ' ¬(g3g' x < g3g' y) (order preservation)

However, this property has the shortcoming of being vectorial rather than purely topological. Its topological generalization, is reciprocal avoidance:

x r y ' ¬(g3g' x r -1 g3g' y) (reciprocal avoidance)

Reciprocal avoidance, was over-generalized and caused problems with auto-reciprocal relationship (i.e. such that r=r -1 ). The neighborhood compatibility, while not expressed in [START_REF] Euzenat | Représentation granulaire du temps[END_REF] has been taken into account informally: it constrains the conversion of a relation to form a conceptual neighborhood (and hence the conversion of a conceptual neighborhood to form a conceptual neighborhood).

(2) 4r, 4r',r"%g3g'r , 5r 1 ,…r n %g3g'r such that r 1 =r', r n =r" and 4i%[1,n-1] N ! X (r i ,r i+1 )

(neighborhood compatibility)
This property has already been reported by Christian Freksa [START_REF] Freksa | Temporal reasoning based on semi-intervals[END_REF] who considers that a set of relationships must be a conceptual neighborhood for pretending being a coarse representation of the actual relationship. ( 2) is weaker than the two former proposals because it does not forbid the opposite to be part of the conversion, but, in such a case, it constrains whatever be in between the opposite to be in the conversion too. Neighborhood compatibility seems to be the right property, partly because, instead of the former ones, it does not forbid a very coarse grain under which any relationship is converted in the whole set of relations. It also seems natural because granularity can hardly be imagined as discontinuous (at least in continuous spaces).

Conversion-reciprocity distributivity

An obvious property for such an operator is symmetry. It is clear that the relationships between two temporal occurrences are symmetric and thus granularity conversion must respect this.

(3) (g3g' $ -1 ) = (g3g' $) -1 (distributivity of g3g' on -1 )

Inverse compatibility

Inverse compatibility states that the conversion operators are consistent with each other, i.e. that, if the relationship between two occurrences can be seen as another relationship under some granularity, then the inverse operation from the latter to the former can be achieved through the inverse operator. For instance, if someone in situation (b) of figure 1 is able to imagine that, under a finer granularity (say situation c), there is some space between the bumper and the house, then (s)he must be whiling to accept that if (s)he were in situation (c), (s)he could imagine that there is no space between them under a coarser granularity (as in situation b).

Cumulated transitivity

A property which is usually considered first is the full transitivity: g3g'•g'3g" r = g3g" r This property is too strong; it would for instance imply that: g3g'•g'3g r = r Of course, it cannot be achieved because this would mean that there is no loss of information through granularity change: this is obviously false. If it were true anyway, there would be no need for granularity operators: everything would be the same under each granularity. We can expect to have the cumulated transitivity: g 1 g' • g' 1 g" r = g 1 g" r and g" 2 g' • g' 2 g r = g" 2 g r However, in a purely qualitative calculus, the amounts of granularity (g) are not relevant and this property becomes a property of idempotency of operators:

(5)

1•1 = 1 and 2•2 = 2 (idempotency)
At first sight, it could be clever to have non idempotent operators which are less and less precise with granularity change. However, if this applies very well to quantitative data, it does not apply for qualitative: the qualitative conversion applies equally for a big granularity conversion and for a small one which is ten times less. If there were no idempotency, converting a relationship directly would give a different result than doing it through ten successive conversions.

Representation independence

Representation independence states that the conversion must not be dependent upon the representation of the temporal entity (as an interval or as a set of bounding instants). Again, this property must be required:

(6)g3g' $ = 0 g3g' '$ and g3g' $= ' g3g' 0 $ (representation independence)

Note that since 0 requires that the relationships between bounding instants allows the result to be an interval, there could be some restrictions on the results (however, these restrictions correspond exactly to the vanishing of an interval that which is out of scope here).

. The granular system for time relations

Once these six properties have been defined one can start generating candidate upward and downward conversion operators. However, these requirements are so precise that they leave no place for choice. We are showing below by starting with the instant algebra that there is only one possible couple of operators. Afterwards, this easily transfers to interval algebra.

Conversion operators for the instant algebra

The 64(=2 3 .2 3 ) a priori possible operators for converting < and = can be easily reduced to six: the constraint (1) restricts the conversion of < to be {<}, {<=}, {<>} or {<=>} and that of {=} to be in {=}, {<=}, {=>} or {<=>}. The constraint (2) suppresses the possibility for < to become {<>}. The constraint (3) has been used in a peculiar but correct way for eliminating the {<=} (resp. {=>}) solutions for =. As a matter of fact, this would cause the conversion of = -1 to be {=>} (resp. {<=}), but = -1 is = and thus its conversion should be that of =.

< \ = {=} {<=>} {<} Id 7 {<=} 8 9 {<=>} : no info Table 5
. The six possible conversion operators for = and <.

There are still six possible conversion operators left (Id, 7, 8, 9, : and NI). Since the above table does not consider whether the operators are for downward or upward conversion, this leaves, a priori, 36 upwarddownward couples. But the use of property (4) -the putative operators must be compatible with their inverse operator (and vice-versa) -reduces them to 5: Id-Id, 7-8, 9-9, :-: and NI-NI.

The solution Id-Id cannot be considered as granularity since it does not provide any change in the representation. The solution NI-NI is such that it is useless. The :-: pair has the major flaw of not being idempotent (i.e. : •: ; : ): as a matter of fact, the composition of : with itself is NI, this is not a good qualitative granularity converter (this violates property 5). There are two candidates left: the 9-9 has no general flaw, it seems just odd to have an auto-inverse operator (i.e. which is its own inverse) since we all know the asymmetry between upward and downward conversion: it could be a candidate for upward conversion (it preserves the equality of equals and weakens the assertions of difference) but it does not fit intuition as a downward conversion operator (for the same reasons). Moreover, 9

does not respect vectorial properties such as orderpreservation (9 is just 8 plus the non distinction between < and >). Thus the 7 -8 pair is chosen as downward/upward operators. The main argument in favor of 7-8 is that they fit intuition very well. For instance, if the example of figure 1 is modeled through bounding instants (xfor the beginning and x + for the end) of intervals T + , B -, B + and H -, it is represented in (c) by T + =B -(the truck ends where the bumper begins), B -<B + (the beginning of the bumper is before its end), B + <H -(the end of the bumper is before the beginning of the house) in (b) by B + =H -(the bumper ends where the house begins) and in (a) by B -=B + (the bumper does not exist anymore). This is possible by converting with the couple 7-8 which allows to convert B + <Hinto B + =H -(= % 8<) and B -=B + into B -<B + (< % 7=), but not with the use of 9 as a downward operator. Thus the following result is established: PROPOSITION: The table 6 defines the only possible non auto-inverse upward/downward operators for A 3 .

relation: r g 1 g' r g 2 g' r < < = < = = < = > > > = > Table 6
. Upward and downward granularity conversions between instants.

The operators of table 6 also satisfy the properties of granularity operators.

PROPOSITION: The upward/downward operators for A 3 of table 6 satisfy the properties (1) through [START_REF] Euzenat | Représentation granulaire du temps[END_REF].

Conversion operators for the interval algebra

By constraint (6) the only possible operators for A 13 are now given. They enjoy the same properties as the operators for A 3 .

PROPOSITION: The upward/downward operators for A 13 of table 7 are the only one to satisfy the property [START_REF] Euzenat | Granularité dans les représentations spatio-temporelles[END_REF] with regard to the operators of A 3 of table 6.

PROPOSITION: The upward/downward operators for A 13 of table 7 satisfy the properties (1) through [START_REF] Euzenat | Représentation granulaire du temps[END_REF].

The reader is invited to check on the example of figure 1, that what has been said about instant operators is still valid. The upward operator does not satisfy the condition (2) for B-neighborhood (violated by d, s and f) and C-neighborhood (o, s and f). This result holds since the corresponding neighborhoods are not based upon independent limit translations while this independence has been used for translating the results from A 3 to A 13 . relation: r

g 1 g' r g 2 g' r b b m b d d f s e d o o f -1 s m e o s s e o s d f f e d f o -1 m m b m o e e o f -1 d -1 s e s -1 d f o -1 m -1 m -1 o -1 m -1 b -1 f -1 f -1 e d -1 f -1 o s -1 s -1 e d -1 s -1 o -1 o -1 o -1 s -1 f e m -1 o -1 d -1 d -1 s -1 f -1 e d -1 b -1 b -1 m -1 b -1
Table 7. Upward and downward conversion operators between intervals.

Granularity and inference

The composition of symbolic relationship is a favored inference mean for symbolic representation systems. One of the properties which would be interesting to obtain is the independence of the results of the inferences from the granularity level (property 7). The distributivity of g 3 g ' on × denotes the independence of the inferences from the granularity under which they are worked out. [START_REF] Euzenat | An algebraic approach to granularity in qualitative time and space representations[END_REF] g3g

' ($ 1 × $ 2 ) = (g3g' $ 1 ) × (g3g' $ 2 ) (distributivity of g3g' over ×)
This property is only satisfied for upward conversion in A 3 .

PROPOSITION:

The upward operator for A 3 satisfies property [START_REF] Euzenat | An algebraic approach to granularity in qualitative time and space representations[END_REF].

It does not hold true for A 13 : let consider three intervals x , y and z such that x b y and y d z , the application of composition of relations gives x{b o m d s}z which, once upward converted, gives x{b m e d f s o f -1 }z. By opposition, if the conversion is first applied, it returns x{b m}y and y{d f s e}z which, once composed, gives x{b o m d s}z. The interpretation of this result is the following: by first converting, the information that there exists an interval y forbidding x to finish z is lost: if, however, the relationships linking y to x and z are kept, then the propagation will take this into account and recover the lost precision: {b m e d f s o f -1 }&{b o m d s}={b o m d s}. However, this cannot be enforced since, if the length of y is so small that the conversion makes it vanishing, the correct information at that granularity is the one provided by applying first the composition: x can meet z under such a granularity. However, if [START_REF] Euzenat | An algebraic approach to granularity in qualitative time and space representations[END_REF] cannot be achieved for upward conversion in A 13 , we proved that upward conversion is super-distributive over composition. PROPOSITION: The upward operator for A 13 satisfies the following property: [START_REF] Luis Fiadeiro | Sometimes "tomorrow" is "sometime": action refinement in a temporal logic of objects[END_REF] ( g 1 g' $ 1 ) × ( g 1 g' $ 2 ) # g 1 g' ($ 1 × $ 2 ) (super-distributivity of g 1 g' over ×)

A similar phenomenon appears with the downward conversion operators (it appears both for instants and intervals). So let consider three instants x, y and z such that x>y and y=z, on one hand, the composition of relations gives x>z, which is converted to x>z under the finer granularity. On the other hand, the conversion gives x>y and y{<=>}z because, under a more precise granularity y could be close but not really equal to z. The composition then provides no more information about the relationship between x and z (x{<=>}z). This is the reverse situation as before: it takes into account the fact that the indicernability of two instants cannot be ensured under a finer grain. Of course, if everything is converted first, then the result is as precise as possible: downward conversion is sub-distributive over composition.

PROPOSITION: The downward operators for A 13 and A 3 satisfy the following property: [START_REF] Freksa | Temporal reasoning based on semi-intervals[END_REF] g 2 g' ($ 1 × $ 2 ) # ( g 2 g' $ 1 ) × ( g 2 g' $ 2 )

(sub-distributivity of g 2 g' over ×)

These two latter properties can be useful for propagating constraints in order to get out of them the maximum of information quickly. For instance, in the case of upward conversion, if no interval vanishes, every relationship must be first converted and then composed.

. Further and ongoing works

Category theory which is widely used in programming language semantics has been introduced in knowledge representation [START_REF] Aït-Kaci | Towards a meaning of LIFE[END_REF] in order to account for the relation of approximation between, on the one hand, a knowledge base and the modeled domain, and on the other hand, the many achievements of a knowledge base. Ongoing works tackle the problem of such a categorical semantics for time representation. It meets the intuition: granular representation is approximation. This will provide the advantage of allowing the integration of a specialized time representation into a wider context (e.g. for adding temporal extension to objects represented as <-terms). Category theory allows to do so in a general way.

Figure 1 .

 1 Figure1. The same scene under three different granularities. This is taken as a spatial metaphor for time granularity and is used throughout the paper.

Figure 2 . 3 A

 23 Figure 2. Neighborhood graphs for (a) instant-to-instant relations, (b) interval-to-interval relations. The neighborhood graph is made of relations as nodes and conceptual neighborhood as edges (reciprocal relationships are denoted with an "i" added at the end for the sake of readability). The graph of figure 2a represents the graph of conceptual neighborhood N 3 A between instants (the only continuous deformation is translation). The graph of Figure 2b represents the conceptual neighborhood N 13 A

Table 1 .

 1 The 3 relationships between instants x1 and x2.

Table 2 .

 2 Composition table between instant relationships.It is sometimes possible to deduce the relationship between two instants x and z, even if it has not been provided, by propagating the otherwise known relationships. For instance, if x is simultaneous ({=}) to y which is anterior ({<}) to z, then x is anterior to z; this is called composition of temporal relations. The composition operator × 3 is represented by a composition table(

table 2

 2

	) which indeed indicates that =× 3 < gives
	{<}.
	A (continuous) period is a temporal entity with
	duration. It can be thought of as a segment on a straight
	line. A numerical representation of a period is an
	interval: a couple of bounds (beginning instant, ending
	instant) or a beginning instant and a duration. Intervals
	can be manipulated through a set of 13 mutually
	exclusive temporal relationships between two intervals
	(see table 3); this set is called A 13 .
	relation: x1 r x2	x1/x2	reciprocal: x2 r -1 x1
	before (b)		after
	during (d)		contains
	overlaps (o)		overlapped by
	starts (s) (and		started by
	finishes before)		(and finishes after)
	finishes (f)		finished by
	(and start after)		(and starts before)
	meets (m)		met by
	equals (e)		e

Table 3 .

 3 The 13 relationships between two intervals x1 and x2.

Acknowledgments

Many thanks to Hany Tolba who carefully commented a longer version of this paper and to one of the reviewers who pointed out interesting connections.

. Related works

Jerry Hobbs introduced the concept of granularity from the non discernability of particular terms with regard to a given set of predicates (these terms can be substituted in the range of any of the given predicates without changing their validity). The main difference here is that the granularity is given a priori in the structure of time and the scaling notion while Hobbs defines a granularity with regard to relevant predicates. To our knowledge there is no other proposal for integrating granularity into qualitative time representation.

There has been tremendous work on granularity in metric spaces. One of the more elaborate model is that of [START_REF] Montanari | Dealing with time and granularity in the event calculus[END_REF][START_REF] Ciapessoni | Embedding time granularity in a logical specification language for sychronous real-time systems[END_REF]. It proposes a quantitative temporal granularity based on a hierarchy of granularities strictly constrained (to be convertible, divisible…) which offers upward and downward conversion operators for instants and intervals (instead of their relationships). [START_REF] Euzenat | Représentation granulaire du temps[END_REF] offers a more general (i.e. less constrained) framework for quantitative relationships and thus achieves weaker properties. Hence, the properties obtained here for qualitative representation are compatible with the quantitative representation of [START_REF] Montanari | Dealing with time and granularity in the event calculus[END_REF][START_REF] Ciapessoni | Embedding time granularity in a logical specification language for sychronous real-time systems[END_REF]. Others works [START_REF] Badaloni | Dealing with time granularity in a temporal planning system[END_REF] considered granularity in a hybrid qualitative/quantitative system. The same effect as presented here could certainly been achieved through the computation of qualitative relationships from quantitative ones (using [START_REF] Montanari | Dealing with time and granularity in the event calculus[END_REF][START_REF] Ciapessoni | Embedding time granularity in a logical specification language for sychronous real-time systems[END_REF] but not in a pure qualitative fashion.

[8] presents a systems which shares a great deal with ours: they treat granularity changes between several representations expressed in the same classical temporal logic (just like here, we used the classical A 3 and A 13 ) and they map these representations to natural numbers instead of real numbers [START_REF] Euzenat | Représentation granulaire du temps[END_REF]. However, temporal logics and algebra of relations are not immediately comparable so the results are quite different in nature. It is expected that the categorical framework sketched in §6 allows to compare the two approaches in depth.

. Conclusion

In order to understand the relationships between several granularities, a set of requirements have been established for conversion operators. The only possible operators filling these requirements have been defined. Moreover other properties of the operators have been established (preservation of the relationship between points and interval). These operators can be used for combining information coming from different sources and overcoming their contradictory appearance. Further works have been done for extending qualitative granularity from time to space and are reported in [START_REF] Euzenat | Granularité dans les représentations spatio-temporelles[END_REF][START_REF] Euzenat | An algebraic approach to granularity in qualitative time and space representations[END_REF].