Jérôme Euzenat
email: jerome.euzenat@inrialpes.frjacq@lgpd.univ-mrs.fr

Christophe Chemla

Bernard Jacq

Jérôme Euzenat +,#

A knowledge base for D. melanogaster gene interactions involved in pattern formation

come

L'archive ouverte

We are interested in the biological process of pattern formation in Drosophila and in understanding the basis of specific identity acquisition by the different body parts [START_REF] Fasano | The gene teashirt is required for the development of Drosophila embryonic trunk segments and encodes a protein with widely spaced zinc finger motifs[END_REF][START_REF] Röder | The role of the teashirt gene in trunk segmental identity in Drosophila development[END_REF][START_REF] Alexandre | The Drosophila teashirt homeotic protein is a DNAbinding protein and modulo, a HOM-C regulated modifier of variegation, is a likely candidate for being a direct target gene[END_REF]. In Drosophila, different classes of genes involved in the segmentation processes (maternal, gap, pair-rule and segment polarity genes) divide the embryo along the antero-posterior axis into repeated homologous units [START_REF] Nüsslein-Volhard | Mutations affecting segment number and polarity in Drosophila[END_REF][START_REF] Gaul | Role of gap genes in early development[END_REF] which will develop specific identities and morphogenetic features under the control of homeotic genes [START_REF] Lewis | A gene complex controlling segmentation in Drosophila[END_REF]]. Specific interactions within and between these gene families are essential for the establishment of a correct body pattern. Being able to access, query and manipulate the data on these developmental genes and their functional interactions within specific regulatory networks is now an important requirement for developmental and molecular biologists studying gene regulation. Gene molecular interactions, i.e. direct molecular interactions involving DNA, RNA and proteins, play an essential role in all known biological processes. Although different databases exist for each of these three types of macromolecules, data concerning precise molecular interactions between them are underrepresented in these databases. The majority of these databases can be classified as "mainly structural" because the core of their informational content is based on various aspects of DNA, RNA or protein sequence and/or structure. Relatively few databases have a content and an organisation which are oriented towards the biological function of the genes and the relationships between structure and function. In the field of genetic diseases, OMIM, a catalogue of human genes and genetic disorders [OMIM 1996] provides the user with both structural (e.g. molecular genetics, biochemistry, genetic mapping) and functional data (e.g. clinical features, diagnosis, inheritance) on human genes.

In order to cope with problems of genetic regulation, it is first essential to be able to describe and organise biological facts such as those described above in a standardised way. For this purpose, we recently described [START_REF] Jacq | GIF-DB: a WWW database on gene interactions on gene interactions involved in Drosophila melanogaster development[END_REF]] the concepts, organisation, content and use of GIF-DB (Gene Interactions in the Fly Database), a new WWW repository for data on gene interactions involved in Drosophila embryonic development and the regulatory networks in which they are involved. GIF-DB is a collection of hypertext files, each of them describing an interaction between two molecular partners (Protein/DNA, Protein/RNA, Protein/Protein). All data found in GIF-DB come from the literature. The production of GIF-DB is a first step in the process of managing scientific information concerning genetic interactions. Although quite complete and simple to use, a collection of hypertext files is only imperfectly suited to represent and query the knowledge we already have on such complex biological problems as molecular interactions.

A further step in that direction requires a system providing more structure (e.g. objects and class hierarchies) and manipulation capabilities (e.g. classification, network traversing) than a relational database or a flat WWW server. Such an organisation will provide the opportunity to gather interactions into networks and to compare, check and simulate these networks.

The KNIFE system (Knowledge on Networks of Interactions in the Fly Embryo)1 , which is presented here, is a knowledge base putting together data and methods about interactions gathered in other databases. It has been developed using the TROPES knowledge representation system, is directly accessible from the WWW and provides several specific utilities such as network traversing and analysis. The choice of an object-based knowledge representation system has already been made by several teams working on metabolism [START_REF] Karp | Representing, analyzing, and synthetizing biochemical pathways[END_REF] or genetic regulation [START_REF] Perrière | Object-oriented knowledge bases for the analysis of prokaryotic and eukaryotic genomes[END_REF][START_REF] Hoogland | Drosoposon: a knowledge base on chromosomal localization of transposable element insertions in Drosophila[END_REF]. The more closely related work to this one is the work around the ECOCYC knowledge base on Escherichia coli genes and metabolism [Karp et al. 1996]. It is an example of a knowledge base which integrates functional aspects since one can find both data on gene structure and their function in the regulation of biochemical pathways. Although it focuses on metabolism instead of genetic regulation, there are several features common with the work presented here: use of knowledge base technology; availability through WWW, including for graph drawing; development of specific algorithms for using the networks (pathways). An important difference is that the context in which genetic interactions are valid is not well known yet.

The TROPES object-based knowledge representation system is first described. Then, the objects, modelling KNIFE data, are presented at length. The functions offered by KNIFE are exposed in the remainder: first the general functions available in TROPES (WWW browsing, classification, filtering) are presented; then, specific methods tied to the exploration of genetic interactions (graph traversing and diagnosis of missing interactions) are detailled. The discussion focuses on a long term goal: the simulation of interaction networks.

Short presentation of TROPES

TROPES is an object-based representation system which favours classification. It is here presented through its basic notions, while more specific descriptions will be found in the remaining sections.

Objects and concepts

In TROPES [START_REF] Mariño | Multiple perspectives and classification mechanism in Object-oriented Representation[END_REF]Sherpa 1995] individuals are represented as objects. The objects are partitioned into concepts (an object is an instance of one and only one concept). As an example, the protein concept concerns all the individual proteins. Ontological prerogatives are attached to the concept. They warrant the integrity of an object (i.e. that the object cannot be modified in a way which would lead it to no longer be an instance of the concept) and its identity (i.e. it can always be uniquely identified). These prerogatives play an important role when the object is created and registered. The concept also defines the structure of its instances. The structure of an object is uniquely determined by a set of fields and their basic domains independently of the classes to which the object can be attached. For example, the instances of the protein concept have a name, a size and a sequence field. The basic domain of a field is either a primitive type (string for the name, integer for the size), a concept (protein-sequence for sequence) or a type constructed from primitive types and concepts with the help of set and list constructors. The field values are part of the objects and do not depend upon the classes to which the objects are attached. For instance, the protein BICOID is represented by an object instance of the protein class. Its name field has the string "BICOID" for value, its size field has integer 494 for value and its sequence field has the instance of the protein-sequence concept also named BICOID for value.

Viewpoints

Objects can be seen under several viewpoints. For instance, BICOID is classified as a transcription-factor under the biochemical-function viewpoint and as a nuclei protein under the initial-and final-sub-cellularlocation. The viewpoints allow to restrict the view on instances and to organise the concept into particular taxonomies. A viewpoint determines:

• The set of fields which are relevant under the viewpoint (the sequence is not relevant from the subcellular-location viewpoints as well as the size under the biochemical-function one, and thus the corresponding fields are hidden under the respective viewpoints).

Classes and taxonomy

A class defines constraints that objects must satisfy in order to belong to the class. It is a projection of the structure of the concept retaining only relevant fields and a restriction of the possible values of these fields. This is achieved with the help of:

• Primitive domain restriction provided by domain enumeration, exclusion or bounding (the effect field of an interaction has a string value enumerated by "activation", "repression" and "activationand-repression"; the size of an average protein can be between 300 and 1000 amino-acids). • Attachment restrictions for concepts: the field values must not only be instances of a particular concept but can be constrained to belong to particular classes of that concept (the value of the sequence field of a protein must be member of the protein-sequence class). • Constraints on field values. These constraints are membership constraints or constraints between fields (the size of a RNA cannot exceed that of its DNAsequence).

• Cardinality restriction on sets (resp. lists) by bounding their number of elements. An object is attached to (to be opposed to "is member of") only one more specific sub-class under a viewpoint, but is member of all the classes of which this class is a specialisation. The interpretation of the specialisation relation is twofold: first, the members of a class are members of its super-classes (extension inclusion property); second, the constraints defined in a class apply to all the members of that class (and thus to the objects attached to all of the more specific classes). In the above example, it means that:

• all transcription-factors are DNA-associated, and

• all transcription-factors, as DNA-associated, inherit their constraints (e.g. being located in the nucleus). So the strengthening of the constraints from class to subclasses is parallel to the restriction of the extension. As opposed to instanciation, objects can be attached to a class and can be detached from it at anytime. Classes also allow the expression of hypothetical knowledge in terms of default values or default inference methods.

TROPES has other features which are not relevant here. Some of them will be presented when needed in the remaining sections.

Biological knowledge representation

The core of the system is described hereafter. It is made of a repository (expressed in TROPES) of concepts, classes and instances representing biological entities. The data originates from other standard repositories and GIF-DB. Figures given here are those at the date of December 1st, 1996.

General overview

The knowledge base, while still incomplete, has been carefully designed in order to reflect the complexity of gene interaction. The KNIFE base contains 16 concepts related with many different aspects of interactions. interaction, expression, gene and protein. They will be detailed in depth below. The other concepts, although being useful to the biologist looking for where, how and why an interaction can happen,

are not yet used by the automatic facilities of KNIFE. They can be briefly described in the following manner (numbers in parentheses indicate the number of instances in the actual knowledge base): mutant (0): the mutant concept describes the kind of mutations which can be applied to a gene and the resulting phenotype. It is not presently used. binding-site-feature (43): describes the bindingsites involved in the interaction between biological objects. They refer the actual sequence through their sequence field and the binding protein through the overlaps-with-protein field. RNA. An obvious one is the sequence field referring to the rna-sequence itself, the product field referring to the protein expressed by the RNA strand.

The expression field is meant to describe in which context this particular RNA strand is to be expressed. These rna objects are referred to by the gene concept, allowing them to determine their corresponding expression patterns. dna-sequence (51), rna-sequence (4), proteinsequence (25): the individual sequences of DNA are described by subsequences (called dna-part) and signals detected in the sequences (dna-signal); these fields contain objects known as dna-sequencepart-feature and dna-signal-feature. The same applies with slight variations to rna-sequence and protein-sequence (with no signal/part distinction). They originate from the international sequence databases (EMBL [START_REF] Rice | The EMBL Nucleotide sequence Database[END_REF] and SWISSPROT [START_REF] Bairoch | The SWISS-PROT protein sequence data bank and its new supplement TREMBL[END_REF]). dna-signal-feature (2), rna-signal-feature (4): describes the various signals (binding sites for regulation proteins, splicing sites) that can be found in the regulatory region of a gene or precursor. dna-sequence-part-feature (2), rna-sequencepart-feature (4): describe the functional parts that can be found in a gene. For RNA these are just the parts corresponding to that of DNA. protein-feature (152): the various structural and functional features (zinc-finger, leucine-zipper, homeodomain and helix) of a protein.

Interactions, proteins and genes

The main concept in KNIFE is the interaction concept containing currently interactions between proteins and genes (type I). Each interaction connects an effector (which is a protein, instance of the protein concept) to a target (which is a gene, instance of the gene concept).

In addition, the interaction has a effect field which contains a string qualifying the interaction effect as "activation", "repression" or both. The interactions also mention the following fields: binding-sites: refers to the set of binding sites (concept binding-site-feature) involved in the regulation;

structure-of-target-product, structure-ofeffector: refers by a string to the known structural patterns in the products (e.g. zinc-fingers, homeodomains); dose-dependence: indicates if the interaction depends on the concentration of the effector. This is not currently used by the algorithms but will be useful in the future; protein-partners: contains a set of proteins which are also involved in the regulation; other fields contain information from the literature among which the experimental methods used for pointing out the interaction or the regions of the embryo where there is evidence for the interaction [START_REF] Jacq | GIF-DB: a WWW database on gene interactions on gene interactions involved in Drosophila melanogaster development[END_REF]]. Protein-RNA and protein-protein interactions can also be represented. All these interactions are viewed through viewpoints depending on their types (whether they imply protein, RNA or DNA target), the structure of effectors and target product, the effect of the interaction and the classes of the involved products (classified after [START_REF] Pankratz | Blatoderm segmentation[END_REF] for gap genes). The interactions in the base come from GIF-DB [START_REF] Jacq | GIF-DB: a WWW database on gene interactions on gene interactions involved in Drosophila melanogaster development[END_REF]]. The two main elements involved in interactions are proteins and genes. Figure 1 displays three viewpoints on the protein concept which has been largely described above. This concept introduces views depending on the initial and final locations of a protein involved, for instance, in the signal transduction pathways; the biochemical-function view considers the families of protein biochemical functions.

The gene concept refers to the sequence of the gene, the precursor RNA and the protein it codes for through the corresponding fields. It can be viewed under four viewpoints: its cytological-location, its phenotypic class, its number of precursors and the size of its transcription unit. This is an important issue since the time required by the RNA-polymerase to transcript DNA depends on the size of the unit. This can thus be used in order to impose temporal constraints to the models of embryogenesis (for some homeotic genes, the transcription can last more than one hour). At start up, KNIFE computes the reverse links from genes and proteins. It is then possible to refer to interactions regulating the gene (incoming) and to interactions in which the gene product is regulator (outgoing). Genes and proteins originate mainly from FLYBASE [Flybase 1996] and SWISSPROT [START_REF] Bairoch | The SWISS-PROT protein sequence data bank and its new supplement TREMBL[END_REF] and their representation obey the FLYBASE control vocabulary. At the moment, there are 25 genes, 26 proteins and 62 interactions.

Expression patterns

The expression concept provides, for a particular development stage and a particular mutation (or wild type individual), the localisation of the expression of a gene, a protein or a particular RNA. Expression patterns are thus identifiable through the following fields:

developmental-stage is a string which denotes the stage at which the expression is found; gene-name contains the name of the corresponding gene object; genetic-context is a string denoting the kind of mutation (or "WT" for wild type). It provides a set of segments of the embryo in which the product of the gene is found. These patterns are encoded in various ways. The main one is the egg-length-domain field which contains the bounds of the intervals of the egg (expressed in percentage of the length of the embryo) where the product is found. For instance, the expression of the fushi tarazu gene at the cellular blastoderm stage for a wild individual is made of 7 stripes (shown on Figure 3): 11-16, 20-24, 28-32, 36-40, 44-48, 52-56 and 60-63% of the egg length. The egg-length-domain is not the only field containing this information: it is encoded in other common formats (regions, segments and parasegments).

This information can be found in the two main views which are offered to the user and which decomposes the expression with regard to the expression-regions (the place of expression: thorax, abdomen, terminalanterior, etc.) and the expression-domains (the pattern of expression: stripe, gradient, etc.). To date, there are 46 expression patterns coming from the DEXIFLY database [Horn et al., submitted].

Interaction networks

In the KNIFE sense, a network is nothing more than a set of interactions. Its interactions field contains the set of interaction objects involved in the network. It is identified by a name. Ideally the networks should be bound to a context expressed through a set of fields:

type is the genetic context of the embryo (wild type or mutant for a particular gene); development-stage speaks for itself; beginning and end are the beginning and end of egglength where the network is supposed to occur. The use of the exceptions field, containing a subset of the interactions, is described below. There is no network stored as such in the base: building a meaningful network is the goal of manipulating the data.

KNIFE access

An important benefit from the modelling of the knowledge in TROPES is the possibility to automatically obtain a web server, allowing, without any effort from the developer, to manipulate the base. This is the subject of that section while the next one concentrates on the specific algorithms developed for KNIFE and integrated in the web site.

Web availability

TROPES can be transformed into a HTTP server [START_REF] Euzenat | Knowledge bases as Web page backbones[END_REF]], which means that the knowledge base is automatically turned into a Web site. Each TROPES entity (e.g. object, concept, concept field or class) is provided with an URL and a display function which generates a HTML page (which may contain references to the other entities through their own URL). When such a page is displayed by a HTTP client (or browser), if the user selects a particular hypertext link in the page, this will fetch the page corresponding to the embedded URL and this page will be loaded in the client. Each page is generated on demand from the object in the base. This capability alone has several advantages since it generates a site free of dangling links and allows the remote access to the knowledge base without special training or special computer model. But other, more elaborate, advantages come with some additional work. First, it is possible to provide annotations to TROPES entities. These annotations can be HTML files which will be incorporated in the usual page generated by TROPES in order to document the displayed object. This provides a first level of enrichment of the Web pages. The included page can be arbitrarily complex (containing URL or images). Moreover, if the default display pattern of the pages is not suited to the current task, it is possible to redefine it. Figure 3 and Figure 4 show such redefinition with the call, during the generation of the page, to a specialised applet (a program which is run in the HTTP browser) which draws graphic pictures of the considered entity. An important aspect of this is the possibility to automatically generate a call to an applet with the corresponding data. This function also offers the opportunity to generate automatically forms that will send a specific query to an independent database without the burden for the user to construct the query. This is used in KNIFE for providing access to the remote resources familiar to the user community (FLYBASE for genetics, EMBL and SWISSPROT for gene and protein sequences and GIF-DB for interactions).

Queries

From a knowledge base described according to the presentation above, it is possible to apply operations provided by the knowledge representation system. So far, TROPES provides two main operations: classification and filtering. Classification consists, for a particular object, in identifying the classes to which it can be attached; filtering consists, from a particular class, in identifying the objects which could be attached to it. For their respective purposes, these operations compare the values in the object fields (whatever they are: string, number, objects…) to the constraints attached to the class fields. TROPES allows to use these reasoning mechanisms in order to issue queries against the base through the Web. For example, filters are used for selecting objects which are attached to certain classes and contain particular field values. These filters are accessible through the HTTP server and allow a more sophisticated search than full text search. For instance, it is possible to ask for all the instances of protein, which are classified as average in size and whose biochemical-function is transcription- -|) and inhibiting interaction and others (-->|) a twofold interaction. The graph applet can be manipulated by the users so that the display suits their needs.

factor. The result is provided in Figure 5.

Network manipulation

The manipulation features described so far are provided in a standard way by TROPES. No particular programming is required, but the knowledge base description. In order to go further some algorithms have been developed specially for the needs of KNIFE. They consist in a graph traversal algorithm and an algorithm for diagnosis of missing interactions.

Network creation and traversing

The KNIFE knowledge base page contains a panel with several operations which apply to the whole base and are specific to the application. First several buttons allow the interactive creation of new networks through the direct selection of the involved interactions or the selection of products which must be source or/and target of the interactions. This allows to create and store sub-networks of particular interest (e.g. the gap-gene network). KNIFE also allows the enumeration of the paths in a network between a particular product and a particular gene (selected interactively). For instance, there are 51 possible ways for the BICOID protein to regulate the hunchback gene from the interactions stored in the base (Figure 6). The implemented algorithm is a classical three-passes traversal which proceeds in O(|N|) where N is the set of nodes in the graph (protein objets). It is generally faster than the time required for displaying the result.

Diagnosis of missing interactions

The diagnosis of missing interactions is a new algorithm which could be invaluable for building networks. Its aim is the detection of interactions which should have activated (resp. inhibited) the expression of a gene while this expression is not (resp. is) observed. For that purpose, the user selects the type of fly (e.g. wild type or mutant) and the developmental stage considered (syncitial or cellular blastoderm in the current state of the base). It is also possible to select a particular area (expressed by a segment of the egg) of the fly. The algorithm will then fetch the expression of all the known genes at that stage for that individual and construct a division of the embryo based on all the patterns. For instance, if we consider the genes Deformed, runt, fushi tarazu, Antennapedia and even-skipped, whose expression patterns (for the wild animal at cellular blastoderm stage) are shown in Figure 7, the result is: 0-9-11-16-17-20-24-25-28-32-33-36-40-41-44-45-48-49-52-56-57-60-63-64-65-68-75-100 Then, the system will build a network for each interval obtained and each network will contain the interactions whose source is a product expressed in the concerned region. For instance, and for the interaction contained in the KNIFE base, the interactions involved between 48% and 49% of the egg length are (--> means activation, --| means repression): GF21: even-skipped --> even-skipped GF22: even-skipped --| fushi tarazu GF64: Antennapedia --| Sex combs reduced GF20: even-skipped --> engrailed GF63: Antennapedia --> Sex combs reduced GF59: even-skipped --> Deformed GF40: runt --| even-skipped Afterward, for each network, the system will point out the products which are expressed although they are inhibited by an active interaction (and activated by no active interaction) or those which are not expressed although they are activated by an active interaction (and inhibited by no active interactions). In the former example, the interactions GF20 and GF59 are in such a case. For instance, GF20 tells that if even-skipped is present, it will activate the expression of engrailed, but engrailed is not present and no other product seems to inhibit it. This means that the base is incomplete on that interaction: either engrailed is expressed (and so its expression pattern is wrong) or something represses its expression. On another hand, there are no exception on Sex combs reduced which is activated by Antennapedia because there is another repression interaction (from Antennapedia too in that case). These interactions are put in the exceptions field of the network. This only means that the content of the base does not explain the observations. This is an invitation for the researcher to add new knowledge about interactions in the system or to plan an experiment in order to gather evidence for this lack of knowledge. If there exists a bound to the number of intervals in a the complexity of the algorithm is in O(|N|*|A| 2 ) where A is the set of interactions. There are several ways in which this algorithm could be improved: by targeting the diagnosis on a particular gene or a particular network.

Discussion

The KNIFE knowledge base described above presents several noticeable features:

• the data is type-checked (detection of type-mismatch or misspelling for instance); • it can be browsed and made available in a client-server fashion (and this is due to the use of a formal representation language); • it allows the linking of these data with other knowledge sources (other bases, raw data or bibliographic data) while offering its own perspective on the data; • it provides efficient ways of manipulating the data through filters or classification; • it allows the usage of specialised algorithms which take their input in the base and deliver their output to the base. From a biological point of view, it has to be noted that KNIFE is the first knowledge base which is devoted to the description of gene interactions and their networks. Up to now, the amount of biological data present in the base is not yet sufficient to get completely significant results with the algorithms. This conclusion is in fact the result of the use of the algorithms themselves, since they are able to detect inconsistencies in the data. Another problem is that the missing interactions algorithm is too simplistic at the moment since biological interactions cannot be completely described using simple boolean formulas. However, the above algorithm has been designed as a tool for pointing out possible problems and should not be considered as an interaction simulator. As a matter of fact, the simulation of interactions in the fly embryo is a long-term objective of such a research. No simulation algorithm has been developed so far in the KNIFE knowledge base and this is due to a double requirement: in order to be tractable, the problem should be simplified; in order to be useful, it must not be simplified too much. There are several possible approaches that one could envision in order to tackle the problem.

The first one is boolean simulation which consists, from a network and a set of products (supposed to be present at the beginning), in generating for each possible product the status: present, absent or indeterminate. This type of simulation does not raise any problem but complexity. However, it is not really accurate since it does not account for threshold, efficiency and time, which are important issues in developmental biology. The second one does take into account the fact that the interactions do not act in a uniform way depending on the concentration of the source in the cell. Moreover, the efficiency and result of interactions is not all-or-nothing but can vary depending on that concentration. Simulating the network on that basis would require the introduction in the base of the knowledge about the thresholds and efficiency as well as the initial quantity of product. The simulation could then be produced in a straightforward manner (provided that we are able to combine the threshold and efficiency of two interactions on the same product) or in a more sophisticated way [START_REF] Thomas | Regulatory networks seen as asynchronous automata: a logical description[END_REF]]. However, this solution has the flaw of not considering the time necessary for producing the product and then fails to understand the complete development of interactions. The deeper possible simulation takes the temporal phenomenon into account. It considers not only the threshold effects and interaction efficiency but also the different delays necessary first to transcribe a gene and to obtain a functional protein and, second, for that protein, to regulate a downstream target. A problematic point with this approach is the present scarcity of biological data. It is perhaps also interesting to note that the problem of the simulation of regulatory networks has some similarities, from a formal point of view, with that of metabolism simulation. Since this latter problem is at the moment the object of intense research work [START_REF] Karp | Representing, analyzing, and synthetizing biochemical pathways[END_REF]Karp et al. 1996a;Karp et al. 1996b] it is hoped that future progress in this area will benefit to regulatory network simulation research.

There are three main streams in the future development of the system. The most important one is the feeding of the base with more data. This new data will allow to test the implemented algorithms in context and to evaluate the coverage of the data available. The second direction for improvement is in the user interface: at the moment, a generic interface is proposed by the TROPES system, but it would be better to re-design the actual pages so that they are more adapted to a biologist end-user. This means inclusion of some biological documentation pages and direct links to bibliographic sources for instance. The third important aspect is the development of new algorithms. This covers algorithms for simulating various aspects of genetic regulation and also algorithms for comparing regulation networks between two different development stages or two different organisms.

Figure 1 .

 1 Figure 1. The protein concept is visible under the size, initial-sub-cellular-location and biochemicalfunction viewpoints. Each of them determines a hierarchy of classes whose root class is named protein. For instance, under the biochemical-function viewpoint there is a decomposition of the set of proteins following their functions. The BICOID object is attached to the average class under the size viewpoint, to the nuclear class under the initialsub-cellular-location viewpoint and to the DNA-associated class under the biochemical-function viewpoint.

Figure 2 .

 2 Figure 2. KNIFE concepts and their dependencies. Boxes represent concepts while labelled arrows represent object fields.

Figure 3 .

 3 Figure 3. The expression patterns of the expression concept are displayed by a Java applet. This allows the users to quickly identify the patterns on the fly egg.

Figure 4 .

 4 Figure 4. A network. The list of fields is displayed above a graphic representation of the network. Normal arrows (-->) indicate an activating interaction, T-ending arrows (--|) and inhibiting interaction and others (-->|) a twofold interaction. The graph applet can be manipulated by the users so that the display suits their needs.

Figure 5 .

 5 Figure 5. A filtering: the result of filtering the proteins of average size whose biochemical function is a transcription factor is: DECAPENTAPLEGIC, SEX COMBS REDUCED, WINGLESS, TAILLESS, RUNT, DORSAL and BICOID.

Figure 6 .

 6 Figure6. Graph traversing provides all the paths of length less than or equal to 7 between the BICOID protein and the hunchback gene.

Figure 7 .

 7 Figure 7. Expression patterns and the considered interval between 48 and 49% of the egg length.

  precursor-rna (27): The precursors of a gene are the RNA products which have not been spliced. It was necessary to introduce precursors because the same precursor can be spliced differently or two different precursors can give rise to the same product after splicing. rna (29): rna objects record the information concerning

http://www-biol.univmrs.fr/~lgpd/knife.html

Acknowledgements

This work is supported by the ACC-SV13 of the French ministry of education and research (MENESR), by CNRS and by INRIA. Many thanks to Ulfar Erlingsson and Mukkai Krishnamoorthy (Rensselaer, Troy) for the graphdraw Java applet used in the KNIFE base (http://www.cs.rpi.edu/projects/pb/graphdraw ) and Sylvain Chicois for the adaptation of this applet to the needs of KNIFE and a first implementation of the diagnosis algorithm. We also would like to thank Florence Horn and Laurence Röder for all gene spatial expression data, Laurent Fasano and Michel Page for helpful comments. Finally, the authors would like to thank François Rechenmann for continuous support, fruitful discussions and helpful comments.


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

Sur la sémantique des actes de langage artificiels (remarques préliminaires)

come

INTRODUCTION

La théorie des actes de langage [Searle 69] a été conçue pour rendre compte de la manière qu'ont les locuteurs pour atteindre leurs buts à travers le langage. Ils sont fondés sur une triple distinction entre locution (ce qui est prononcé), illocution (ce que fait le sujet en proférant la locution) et perlocution (ce que fait l'auditeur en recevant la locution émise). Le but peut être atteint par la réalisation de l'un de ces trois aspects. L'un des traits saillants des actes de langage est leur indépendance d'avec le langage d'expression (la forme). Ils ont en particulier été conçu pour rendre compte de ce que les expressions proférées pouvaient être (1) différentes du sens de la locution émise et (2) pouvaient donner un sens à celle-ci.

À l'instar des grammaires qui ont été conçues pour rendre compte du langage naturel et qui ont fait merveille dans la conception de langages artificiels, il semble que la théorie des actes de langages est très bien adaptée pour exprimer des structures de discours artificiels [START_REF] Flores | Computer systems and the design of organisational interaction[END_REF]]. L'avantage des actes de langage par rapport à des messages formels est que l'on doit comprendre ce que veut le locuteur sans comprendre de quoi il s'agit. Ceci est à rapprocher de l'approche fonctionnelle en représentation de connaissance où l'on doit ajouter au langage de représentation de connaissance des "commandes" qui permettent d'agir sur la connaissance représentée [ Levesque 84]. Cette possibilité de typer les messages émis est un trait repris dans les langages multi-agents. Ils sont utilisés pour s'adresser à quelqu'un sans savoir s'il va comprendre ou non le contenu du message (mais il doivent contenir suffisamment d'information pour laisser penser le locuteur qu'il va être compris).

Nous nous intéressons à l'expression des messages pour les systèmes multi-agents. Cette expression peut être considérée indépendamment de la structure des société d'agents et des agents eux-mêmes. Il est largement admis que les actes de langage constituent un bon candidat pour exprimer les messages entre agents. Notre réflexion est plutôt biaisée car elle est dirigée par un domaine de type recherche d'information dont le but est l'échange d'information entre agents et non l'accomplissement d'actions en commun. On peut la replacer dans un contexte où les agents informatique seront amenés à jouer le rôle de représentant d'acteurs socioéconomiques dans la vie publique. Ainsi, beaucoup des exemples figurant ici sont tirés des règles en vigueur dans ces milieux dont il n'y a pas de raisons de penser que l'introduction d'«agents intelligents» doive les changer.

Par ailleurs, notre propos concerne le développement d'un langage général permettant d'exprimer ces actes de langage. Un tel langage devrait permettre d'établir le dialogue entre des agents développés indépendamment. Il doit donc offrir certaines capacités:

• ne pas imposer une réaction particulière à la réception d'un acte de langage particulier;

• être extensible de manière cohérente;

• ne pas imposer sa compréhension complète pour pouvoir être utile.

Il y a cependant une différence importante entre les travaux en linguistique et les travaux en informatique. Au lieu d'analyser la signification des actes de langage naturels, les travaux sur les agents utilisent des systèmes d'actes de langage artificiels et doivent donc leur assigner une définition formelle. Les travaux linguistiques rendent compte d'un comportement observé alors que les travaux informatique tentent de normaliser le comportement que l'on aimerait observer. La théorie des actes de langage développée en linguistique est difficilement implémentable. Mais il ne faut pas oublier que, pour cette raison, leurs spécifications sont plus souples: tous les locuteurs d'une langue naturelle ne sont pas requis d'en comprendre toutes les subtilités et ceci est encore plus vrai pour les actes de langage. À l'opposé, les seconds se posent en normalisateurs de ce que tout le monde doit observer. Ceci induit des différences immédiates entre ces deux approches:

• dans les langages artificiels il est possible de définir une typologie d'actes et de les reconnaître immédiatement alors que dans les langages naturels la difficulté consiste à reconnaître l'acte de langage exprimé au travers de la locution; • dans les langages artificiels les spécifications de ce qui est compréhensible comme un acte de langage particulier sont très rigides alors que dans les langages naturels elles sont beaucoup plus souples. Ainsi, on évitera généralement l'ambiguïté dans un langage artificiel, alors qu'elle apparaît partout dans les langages naturels. Cependant, plus les agents utilisant ces langages seront intelligents, plus ils auront tendance à comprendre les non-dits, plus ils auront tendance à les utiliser et plus l'ambiguïté pourra resurgir. Le parallèle entre langages naturels et artificiels peut ainsi être prolongé: la sémantique des langages, a été développé indépendamment en linguistique et en informatique atteignant dans la seconde discipline des sommets de formalisme. Le résultat étant plus rigide engendre des propriétés plus nombreuses.

Aussi, deux questions se posent légitimement pour les langages d'actes de langage artificiels: quelle est leur syntaxe et leur sémantique?

En ce qui concerne la syntaxe et la typologie des actes de langage disponibles nous considéreront le langage nommé KQML (pour Knowlegde Query and Manipulation Language [Finin& 93]) qui a été conçu à partir de ces idées dans le but de constituer un langage universel et indépendant pour exprimer des actes de langages. Même si KQML est loin d'être universellement apprécié, il reste une bonne base de départ et ne diffère pas dans les principes de sa syntaxe des autres langages fondés sur des actes de langage. Le problème de la sémantique de KQML est actuellement un problème critique [Labrou& 94, Cohen& 95] rejoignant ainsi la seconde question posée. Les travaux actuels concernant la sémantique des actes de langage seront rapidement présentés avant de critiquer leurs développements actuels sur la base de la possibilité d'interaction d'agents hétérogènes. On reviendra ensuite sur quelques propositions pour construire de tels langages.

APPROCHE SÉMANTIQUE DES ACTES DE LANGAGE ARTIFICIELS

Développer la sémantique des actes de langage permettra aux agents de s'exprimer plus sûrement tout en diffusant des contenus dont on ne sait, a priori, si ils seront intelligibles aux autres. Cette flexibilité laisse la porte ouverte à l'implémentation d'agents parlant différents langages et se comportant différemment tout en leur permettant de comprendre l'intention avec laquelle un acte de langage a été proféré.

Présentation de l'idée de ces travaux

Il y a eu de nombreux travaux sur la sémantique des actes de langage. On peut distinguer trois tendances:

1) la sémantique des actes de langage en tant que tels: ces travaux ont principalement été effectué dans le champ de la linguistique à la suite Dans un premier temps on peut s'intéresser à la troisième approche pour deux raisons: (1) elle est générale et n'examine pas le sens des actes de langages au sein d'un protocole particulier -c'est l'un des avantages apporté par l'aspect dénotationel de la logique -et (2) elle ne concerne pas des actes de langages linguistiques (cependant, il faut reconnaître que les approches 1 et 3 ont beaucoup de points communs).

Établir la sémantique d'un acte de langage, consiste à établir à partir de quel moment une action a été accomplie (ou qu'elle a réussit). Elle est donc généralement transposé en logique par la définition des conditions de satisfaction d'un tel acte. Ici, il s'agit généralement de s'assurer que l'interlocuteur a compris le message (ces travaux se sont essentiellement concentrés sur l'illocution). Plus que la modélisation des actes de langages, les travaux cités concernent la modélisation des notions de croyance, de buts et d'intention chez un agent rationnel. Pour cela, les modalités correspondantes sont ajoutées au calcul des prédicats. Ceci permet en outre d'exprimer, à l'aide des théories de l'action, des pré-conditions associées à l'émission d'un acte de langage ainsi que les conditions de son accomplissement. Ces conditions de "satisfaction" d'un acte de langage constituent son sens.

Ces travaux sont généralement applicables à la compréhension d'un dialogue en affectant aux agents des "états mentaux" (sous forme de croyances et de règles pour atteindre leurs buts). Ils sont cependant fondés sur la base d'agents homogènes ayant une compréhension commune de la signification d'un acte de langage particulier. Ils s'appliquent donc parfaitement à l'analyse du comportement d'un système multi-agent et à l'établissement de ses propriétés. Ceci rejoint parfaitement l'approche 2 citée plus haut: les modélisations logico-cognitives permettent de rendre compte des protocoles généralement mis au point. C'est ainsi l'approche utilisée par Munindar Singh [Singh 94] qui permet de faire communiquer des agents utilisant sa logique au travers d'actes de langages dont il donne la sémantique dans ce langage. Le sens d'un acte particulier est alors non ambigu, sujet à aucune interprétation et permet donc de connecter des agents bâtis suivant ce modèle. Il faut noter que cette approche focalisée sur un langage particulier permet d'étudier plus de catégories d'actes de langage (assertive, commissives, directives, permissives, prohibitives et déclaratives) qu'à l'accoutumée.

Cette approche ne permet toujours pas de donner une sémantique à des actes de langages généraux qui pourront être interprétés par des agents quelconques.

Récemment on s'est intéressé à la sémantique des actes de langage utilisés dans KQML [Labrou& 94]. La première remarque que l'on peut se faire est que les auteurs insistent sur l'universalité de KQML. L'approche utilisée consiste alors à assigner à chaque type d'acte de langage un ensemble de pré-conditions et post-conditions exprimées en fonction des croyances, volontés et intentions. Mais l'absence de description plus avancée du formalisme en question ne permet pas de dépasser quelques exemples. Par ailleurs, la sémantique y est donné en fonction de politiques d'interactions qui sont destinées à l'implémenter. Ceci rejoint la seconde approche de la sémantique avec toutefois deux nouveaux problèmes:

• À l'origine, KQML a été présenté comme un standard.

Critique

La critique des formalisations développées ci-dessus s'appuiera sur l'exemple suivant: «Un quidam s'approche d'un distributeur de billets de banque. Il utilise le protocole du distributeur pour retirer 500$. Il y revient quelques jours plus tard et entame le même dialogue mais en demandant 800$. Au moment de valider il annule la transaction. La personne en question n'avait aucune volonté de retirer de l'argent contrairement à ce qu'elle a laissé entendre au distributeur, elle voulait simplement savoir si elle pouvait se faire délivrer 800$ si elle le demandait.» Cet exemple mets en oeuvre un exemple d'agent extrêmement peu intelligent mais particulièrement utile et fiable. Il n'y a rien de particulièrement fautif dans le comportement de l'utilisateur et le distributeur a répondu de manière tout à fait appropriée. Par contre, les travaux présentés ci-dessus sont concernés par la reconnaissance d'un plan (ou des intentions sousjacentes à ce plan) émis par des locuteurs naturels par des êtres intelligents coopératifs. Ce n'est manifestement pas le cas de l'exemple donné plus haut. Or notre position est qu'un langage général de communication entre agents doit, en particulier, permettre à tous les agents de communiquer quelque soit leur degré de complexité. On se rends compte que cet objectif diverge des travaux précédents sur trois points:

• les agents sont soumis à des exigences de sincérité et de coopérativité,

• l'homogénéité des agents est en général supposée, et • la capacité de raisonnement de ces agents est importante.

Sincérité et coopération

Les travaux évoqués ci-dessus postulent très souvent la sincérité (bien que ceci ne soit pas un défaut intrinsèque de l'approche comme le montre [Sadek 93]). Or, dans l'exemple cidessus, l'individu utilisant le distributeur n'est pas sincère puisqu'il laisse entendre à ce dernier qu'il veut réellement retirer de l'argent. Tout est toutefois parfaitement utilisé, l'utilisateur est plus intelligent que le distributeur, il connaît sa façon de réagir, il obtient donc l'information nécessaire. Ceci devrait être possible dans un système multi-agent normalement constitué. Or, si les actes de langages doivent être sincère, l'utilisateur ne peut qu'exprimer ce qu'il veut au distributeur (comment?) qui ne peut répondre qu'en signalant son incompréhension.

Bien que la comparaison avec les comportement sociaux ne soit pas la panacée, il faut bien observer que:

• Nous sommes capables d'interpréter des phrases, et ceci de manière totalement indépendante de l'intention de celui qui les a proféré. • Nous sommes capables de feindre. C'est-à-dire que nous sommes capable de proférer certaines phrases sans qu'elles reflètent nos intentions. En particulier, nous pouvons avoir l'intention de cacher nos intentions.

• Cela ne nous empêche pas d'afficher des règles. Comme la règle suivant laquelle nous sommes toujours sincères. La sincérité dans l'expression des actes de langages et dans l'obéissance aux règles régissant leur compréhension (c'est-à-dire leur sémantique) ne peut être supposée dés l'abord. Il faut donc déconnecter le sens de l'acte de langage de l'intention du locuteur (illocution) ainsi que de l'attitude affichée par l'auditeur (perlocution attendue). Ceci a déjà été soulevé en linguistique [Tutiya 93].

Spécialisation de la sémantique

Les sémantiques évoquées ci-dessus imposent un sens particulier a un acte de langage. Exprimé dans un contexte intentionnel, cet acte de langage implique un comportement particulier de la part du destinataire. Ceci semble contradictoire avec l'universalité attendue d'un langage comme KQML. Pour chaque nouvelle utilisation de KQML, de nouveaux types d'actes sont ainsi nécessaires si l'on veut rester indépendant du langage de représentation de connaissance.

Une définition et une sémantique stricte est très profitable aux aspects de portabilité des langages de programmation mais néfaste à leurs qualités d'ouverture et d'évolution. Dans un monde destiné à être ouvert et évolutif comme celui des systèmes multi-agents, il faut tenter d'être formel (pour que les messages soient interprétables par les agents à qui ils sont adressés) tout en ne fermant pas la porte aux interprétations (de tels sorte que les agents répondent «au mieux» aux messages qu'ils reçoivent). En particulier, il semble néfaste de lier la sémantique des actes de langage artificiels à l'interprétation que devrait en faire leur destinataire.

Hétérogénéité et complexité

Les travaux ci-dessus demandent à chaque agent d'avoir une représentation de ses croyances et de celles de son interlocuteur et de pouvoir raisonner dessus de manière correcte. À partir de croyances et d'intentions, les agents doivent être capable d'inférer les croyances et intentions des autres et, si possible, de les satisfaire sous certaines conditions. Il doivent aussi être capable de se demander si les intentions perçues (au travers d'actes de langages) ont réellement été voulues, etc. C'est beaucoup. Si l'on condamne les distributeurs à couvrir toute la gamme des intentions de leurs utilisateurs, on n'aura plus de distributeurs dans les rues. Supposer que l'on interagit avec des pairs (raisonnant comme nous même) est évidement correct pour des êtres humains adultes. Mais les agents ne sont pas à ce stade. En particulier, il est difficile de dire cela d'un distributeur de billets pourtant très utile.

Si l'on cherche à définir un langage d'actes de langage qui véhicule trop de sens, les petits agents pourtant bien utiles vont être exclus au profit de gros agents (et l'on risque de ne plus être considéré comme des interlocuteurs valables par ces gros agents: déjà certaines personnes ont du mal à utiliser des automates disposés sur la voie publique).

En conclusion, et bien que la logique ne soit qu'un modèle du comportement des agents, imposer une sémantique uniforme oblige à: 1) respecter des règles peu réalistes comme la sincérité, 2) figer le comportement des agents, et 3) figer leur niveau de calcul: il ne peut plus y avoir d'agents dont les capacités cognitives soient inférieures à ce qui est exigé par la sémantique (et elles sont actuellement fort élevées). Ces critiques ne disqualifient pas les approches présentées au paragraphe précédent, en particulier lorsqu'il s'agit de donner un sens au comportement observé par des agents, de donner un sens à un protocole figé, d'interagir avec des interlocuteurs humains ou lorsqu'il s'agit de concevoir des agents très intelligents ayant certaines caractéristiques et agissant dans un milieu connu. Par contre s'il s'agit de donner un sens aux primitives d'un langage destiné à assurer la communication d'agents hétérogènes, elles sont trop réductrices.

SUGGESTIONS

Bien entendu, il est possible de vivre en pensant que les distributeurs de billets sont des être intelligents et coopératifs, qu'ils réfléchissent et ont des intentions. Mais il ne semble pas que ceci doive faire partie de la sémantique des messages utilisés. Cela doit rester une interprétation. Le distributeur n'a pas eu d'intentions, il n'a pas deviné les intentions de son utilisateur, il a simplement réagit de manière à lui donner une explication de pourquoi il ne peut donner 800$ parce qu'il a (été programmé pour) supposé(r) que l'utilisateur voulait 800$.

On ne proposera pas ici de solution miracle permettant de résoudre tous les problèmes mais des pistes principalement fondées sur des approches existantes. En particulier il est clair que les critiques d'ambiguïté et de vague portées à l'encontre de la sémantique de KQML dans [Cohen& 95] est applicable à ces propositions. On est, dans un premier lieu, tenté de repousser toute forme de sémantique dénotationelle au profit d'une sémantique opérationnelle:

• les messages sont émis et non interprétés;

• ils sont traités par les agents suivant des protocoles qui peuvent être accessibles ou cachés. Ceci est proche de la solution 2. Elle conserve une notion d'universalité car elle est fondée sur un ensemble de types de messages. Cette approche permet de répondre à certains des problèmes soulevés:

• Les agents ne sont pas supposés sincères. Ils peuvent afficher leurs règles et les enfreindre. • Ils peuvent interpréter très diversement les messages émis (ils peuvent être plus coopératifs que l'émetteur ne puisse l'imaginer). • On n'impose aucune norme sur le comportement des agents: ils peuvent être très ou très peu intelligent.

Principes

La base de notre argumentation est qu'à une même demande d'information (ask), différents agents ne vont pas réagir de la même manière (par exemple un agent peut disposer de l'information sans être capable de la retrouver si ses mécanismes de raisonnement sont incomplets). Ceci trouve son écho dans les travaux de linguistique mettant en évidence la dépendance entre la signification de l'acte de langage et le contexte (en particulier le déroulement du dialogue) dans lequel celui-ci est émis [Tutiya 93].

Sans parler de sa bonne volonté, on a du mal à imposer la complétude (du moins celle attendue par le locuteur) à un agent. Mais un autre agent plus coopératif pourra répondre quelque chose qui n'est pas demandé (même si celui qui le demande n'est pas capable de comprendre cette manière de faire). Il faut donc déconnecter la sémantique des actes de langage de la manière de fonctionner des agents.

Nous proposons une sémantique à deux niveaux pour les langages d'actes de langage artificiels. Le premier niveau exprime l'intention portée par l'acte de langage (illocution) alors que le second niveau exprime ce qu'une application particulière fera en réception d'une telle expression (perlocution). Ce second niveau pourra être public ou non. Ceci est compatible avec la métaphore sociale: tout le monde ne réagit pas de la même manière à la même demande. La même demande n'a ni la même signification ni le même effet si elle est adressée à son patron, son secrétaire ou son père1 . Cependant, l'intention est la même et le message doit fondamentalement être le même. Ceci est souhaitable dans un contexte multi-agent aussi car cela à l'avantage de permettre l'expression de quelque chose sans se préoccuper de ce que les autres agents vont faire, mais en supposant qu'ils feront quelque chose de raisonnable. Un tel dispositif recouvre les deux aspects suivants:

• Les agents émettent des actes de langage artificiels dans une typologie particulière. On sait dire intuitivement, et non formellement, ce qu'ils signifient, c'est-à-dire ce qu'attend le locuteur. • Les agents publient s'ils le veulent les réactions qu'ils ont aux actes de langage artificiels qu'ils comprennent. Ces réactions peuvent être exposées formellement. Au moins, elles doivent être exposées dans un langage accessible aux locuteurs. Ceci est à rapprocher d'autres travaux: [Sadek 93] en déconnectant la perlocution du sens de l'acte de langage permet, à la fois son interprétation en fonction d'un protocole particulier et la prise en compte de l'insincérité; [Demazeau 95] déconnecte explicitement ce qui est observé de ce qui est attendu et introduit la publication des protocoles.

Mise en oeuvre

Dans le cadre présent, on peut considérer que les messages envoyés le sont en KQML et que les protocoles publiés le sont sous forme d'automates.

Les actes de langage

Ainsi, on peut penser qu'un langage d'actes de langage artificiels doit posséder: • un sens communément accepté;

• la possibilité de porter de l'information indépendamment du formalisme dans lequel celle-ci est exprimée; • la compositionalité (c'est-à-dire la capacité à construire un acte de langage à partir d'un autre). Mais, il ne doit pas définir la manière de déduire les intentions qui lui ont donné naissance. Ainsi, la tâche d'inférer les intentions cachées ou affichées par un acte de langage doit être laissé hors de la sémantique de l'acte de langage dans la conception du raisonnement de l'agent artificiel.

Cette approche fait revenir à l'ancienne définition de KQML [Finin& 93]. Il est en effet difficile de s'entendre beaucoup plus sur ce qui doit être fait sans imposer des comportement. Un pas supplémentaire pourra être atteint, par exemple en typant les différents messages qu'il est possible d'obtenir en réponse. Par exemple, ci-dessous voici quelques primitives KQML (le langage K correspond au langage de représentation de connaissance, S, R et C, N désignent respectivement le locuteur, le récepteur, le contenu et l'identificateur-de-réponse du message). Cependant, même ce petit aménagement contraint a spécifier beaucoup trop les dialogues utiles possibles. La solution proposée ici n'est donc pas très poussée sur l'aspect d'établir une sémantique pour les actes de langage puisqu'ils restent à l'état de jetons. Mais cette approche a plusieurs avantages:

• Elle fourni une sémantique informelle aux actes de langage même si celle-ci n'a aucune relation avec la réalité ou avec les effets que l'"utterance" aura sur le monde; • Elle ne contraint pas les applications à ajouter de nouveaux types d'actes de langage pour des significations légèrement différentes: les différences peuvent être comprises par la publication de la manière dont l'agent comprendra le message.

Les protocoles

Imaginer que les protocoles soient exprimés par des automates d'état finis étiquetés par les types d'actes de langage a plusieurs avantages:

• on sait déjà les interpréter tels-quels (ce n'est pas le cas des démonstrateurs de logique modale); • ils sont relativement synthétiques et naturels; • ils ont un degré d'expressivité qui semble suffisant pour exprimer l'interaction entre les agents (même s'ils ne le font pas forcément de la manière la plus élégante); On peut, bien entendu fournir la sémantique du protocole en logique. Cela a certains avantages comme celui de pouvoir vérifier qu'il possède certaines propriétés (de nombreux travaux sont fait sur ce sujet pour les protocoles de communication classiques). Dans le cadre d'agents, le législateur ou un comptable en certaines circonstances sont capable de comprendre un protocole (contrat de location, règle de remboursement des missions, etc.) par rapport à ses propriétés. Ils sont rapidement capable de dire si un reçu doit être demandé ou si un contrat est équitablement conçu. Sans compréhension du mécanisme complet, ils sont capable de dire que le protocole permet de louer un bien sous les garanties que le législateur a jugées équitables.

La déclaration de protocoles a déjà été expérimentée [Demazeau 95]. Il est envisageable qu'un agent publie plusieurs protocole ou aucun et il est possible qu'il utilise un protocole public (révisable ou non) tel qu'un contrat type de vente ou un protocole qui lui est propre. Un tel protocole est garanti par une autorité à laquelle l'agent émetteur devrait pouvoir faire confiance.

Cette procédure a l'avantage de permettre à un émetteur de préciser sous quel protocole il veut que son message soit interprété (par exemple, en France, les marchés publics ne sont soumis à la procédure d'appel d'offre public que lorsque l'enveloppe budgétaire est supérieure à un certain montant). Ceci nécessite une extension à KQML dans lequel on considère qu'il n'existe pas qu'un protocole universel commun à tous les agents. Si le protocole n'est pas précisé, le choix de celui-ci est laissé au récepteur.

Enfin, tout ceci ne préjuge aucunement du fait que l'on puisse envoyer un message sans que l'interlocuteur ait affiché un protocole particulier. Il est possible de diffuser un message (par exemple, "à l'aide") sans savoir comment chaque individu va réagir face à un tel message. Il faut faire confiance à leur capacité à interpréter correctement le message et à réagir en accord avec le message émis ou à l'ignorer. L'un des avantages de cette méthode est qu'elle permet à des agents d'acquérir et de publier facilement de nouveaux protocoles. Les agents interagissant vont devoir acquérir la connaissance de la façon dont les autres agents réagissent. Ceci peut être acquis par l'expérience ou par la lecture des protocoles publiés par les autres agents. Cela n'empêche pas de raisonner à propos des autres agents, des représentations que l'on se fait d'eux mais doit être déconnecté de la sémantique des actes de langage. Le locuteur potentiel peut alors, s'il dispose de capacités «cognitives» suffisantes déterminer ce que son acte de langage va provoquer. Une fois ceci fait, l'agent initiant une discussion pourra, en fonction de la compréhension connue des différents types d'actes, décider s'il doit ou non envoyer sa demande à un agent particulier. Par ailleurs, l'agent sera capable, en partie, de vérifier si les autres agents mentent ou non; mais il est douteux que l'on puisse d'atteindre la complétude sur ce sujet.

Sincérité

Tout ceci ne préjuge aucunement de la sincérité des intervenants. À partir du clivage illocution/perlocution et exprimé/réel, il est possible de construire une matrice suivant que ce qui est exprimé correspond à ce qui est fait (respectivement désiré). D'habitude, la sémantique des actes de langage considère que la perlocution réalisée doit être en adéquation avec l'illocution exprimée. Cependant, lors d'un dialogue, il n'est pas raisonnable de demander une perlocution précise. Ce que l'on attend est qu'un but soit atteint, c'est ce but qu'il faut exprimer.

À travers les exemples qui suivent nous montrons que les mêmes messages dans différents protocoles peuvent donner lieu à des réactions différentes tout en préservant le sens intuitif des messages. Figure: Dans chacun des quartiers figure une communication entre deux agents; les quartiers sont construits suivant le clivage sincère/non sincère pour chacun des agents. On s'intéresse à la réaction de l'agent de droite à la réception d'un message de l'agent de gauche signifiant qu'il veut connaître l'opinion de celui-ci sur une "formule" (a). L'agent de droite publie son protocole sous la forme d'un automate (K?a retourne le statut de a dans K). Quelques exemples en français d'un tel comportement sont donnés en dessous 2 .

CONCLUSION

Lors de la définition d'un langage d'actes de langage artificiels, le problème de la sémantique des actes est donc posé. Il semble, effectivement utile de le résoudre avant de pouvoir utiliser sur une échelle importante un tel langage. Cependant cette demande se heurte aux problèmes d'inter-opérabilité des agents:

• leur comportement n'est plus libre (sincérité,… dont requis);

• une compréhension standardisée des actes leur est demandée;

• ils doivent disposer de "capacités cognitives" trop étendues a priori.

2 Bien entendu, les exemples donnés sont totalement immaginaires.

Ainsi, si l'on veut arriver à des agents hétérogènes (c'est-à-dire d'origines différentes) capable des communiquer entre eux, il est nécessaire de leur donner la possibilité d'interpréter différemment (dans des contextes différents, sous des protocoles différents, avec des agents différents…) les actes de langage échangés. Si ce n'est pas le cas on verra alors fleurir des panoplies de langages d'actes de langages artificiels, chacun d'eux parfaitement défini, chacun d'eux parfaitement incompatible avec les autres: c'est l'état de l'art des langages de programmation. Cependant, cet état de l'art n'est pas si désastreux que cela:

• il y a des langages plus adaptés à certaines activités que d'autres;

• les langages de programmation permettent l'inter-opérabilité au niveau code-objet. Mais la volonté de communication généralisée entre agents sera envolée.

Il a été suggéré ici de réserver l' approche sémantique logico-cognitive à la compréhension et l'interprétation de systèmes particuliers:

• communication entre agents homogènes et très intelligents;

• modélisation de locuteurs naturels ou analyse d'un dialogue particulier (qui revient simplement à donner un sens à un corpus). Ainsi, l'exemple de l'automate peut parfaitement être interprété en termes logico-cognitifs. De même que des protocoles beaucoup plus complexes sont utilement analysés en ces termes. Par contre, il est proposé de revenir à un approche plus intuitive et plus radicale des langages d'actes de langages artificiels. Une telle formulation laisse les agents libres d'interpréter et d'apprendre la signification des messages et libres de jauger du degré de sophistication de l'agent qu'ils ont en face d'eux.

Nous avons développé un protocole particulier (pour la communication entre bases de connaissance [Euzenat 96]) et la communication entre agents dans le cadre de ce protocole à l'aide de messages KQML. Cependant ce protocole n'est pas inter-opérable (et il ne satisfait pas les sémantiques couramment élaborées pour KQML). Mais il peut être facilement publié et consulté par d'autres agents de manière à ce qu'ils soient capable de comprendre ce qui se passe lorsqu'ils envoient des messages aux bases de connaissance qui sont nos agents (de plus ceuxci sont sincères: ils n'ont même pas à penser à ce qu'ils envoient).

Ces propositions, ne sont à l'évidence qu'un pis-aller. Mais les autres suggestions conduiront sans doute à une nouvelle guerre des langages.

RÉFÉRENCES

  S wants to know if C is believed by RK tell tell S tells R that it believes C K reply S reply to the R's message identified by N kqml/K -

  lequel, pour diverses raisons, le lauréat est désigné d'avance. a (ask-all content: a) (reply content: K?a) x K?x Une OPA destinée uniquement à susciter une contre-OPA. a (ask-all content: a) (reply content: no)Il est clair qu'ici le but du demandeur est simplement de tester la loyauté des réponses du répondeur. Ceci peut aussi s'appliquer à une réponse à un appel d'offre destiné uniquement à atteindre le nombre de concurrents requis.

[

  Chang& 94] Man Kit Chang, Carson Woo, A speech-act-based negociation protocol: design, implementation and test use, ACM transactions on information systems 12(4):360-383, 1994 [Cohen& 79] Philip Cohen, C. Raymond Perrault, Elements of a plan-based theory of speech acts, Cognitive science 3(3):177-212, 1979 [Cohen& 90] Philip Cohen, Hector Levesque, Intention is choice with commitment, Artificial intelligence 42(2-3):213-262, 1990

  Les politiques n'étant que très partiellement fixées, il est difficile de comprendre la sémantique du langage. Ainsi, ces travaux ont prêté le flanc à certaines critiques [Cohen& 95].

Puis, afin qu'il atteigne ce stade, une sémantique a été réclamée et les travaux ont commencé. Maintenant, KQML n'est plus un format de message mais décrit aussi un protocole [Labrou& 94]. On peut se demander s'il s'agit toujours d'un langage universel d'actes de langage au sens présenté plus haut; •

À noter qu'ici les différences de formes qui apparaîssent dans le langages naturel disparaissent au profit de messages banalisés exprimant directement -et linguistiquement en fait -l'acte de langage.


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

An algebraic approach to granularity in qualitative time and space representation

HAL is

. 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 granularity (a) 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 [Hobbs 1985], granularity is expressed in an abstract way (i.e. not connected to time) between two, more or less detailed, logical theories. On the other hand, the physical time-space and its representation have been wellstudied because many applications require them. A very popular way to deal with time [Allen 1983] and space [Egenhofer& 1992;[START_REF] Randell | [END_REF] is the representation of relationships between areas of these spaces. [START_REF] Montanari& | [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 those of [Euzenat 1993].

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 extension of granularity operators towards space representation is then briefly discussed ( §5).

The proofs of all the propositions, but the "only" part of the first one, can be found in [Euzenat 1994].

. 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. Here are reminded 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 . 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) which indeed indicates that =× 3 < gives {<}. The composition operator × 13 is represented by a composition table [Allen 1983], 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.

relation (r): x1 r x2 x1/x2 reciprocal: x2 r -1 x1 before (<) after (>) simultaneously (=) =
× 3 > = < > > > < = > = > = < < < = > < <

Extensions of notations

Let ! be either A 13 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 [Freksa 1992a]. A conceptual neighborhood is a set of relations whose elements constitute a connected sub-graph of the neighborhood graph. A between instants (the only continuous deformation is translation). The graph of Figure 2b represents the conceptual neighborhood N 13 A 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 [Freksa 1992a]). The influence of this choice is acknowledged when it matters. 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).

DEFINITION (conceptual neighborhood

): A conceptual neighbor relationship is a binary relation N ! X on a set ! of relations such that N ! X (r 1 ,r 2 ) iff

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 +
Since any formula representing relationship between four instants x -, x + , y -and y + satisfying 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.

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.

. Requirements for granularity change operators

Operators for transforming the representation of a temporal situation from one granularity to another can be defined so that the resulting representation is 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 under 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. Provided that only the positions of the objects along the horizontal line are considered, 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).

The relationship between two representations of the same reality under two different granularities has to be explicited. 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 (a discretization). 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 cared 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, a downward (resp. upward) operator is needed which, from a relationship observed under 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 [Euzenat 1993]) 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 g3 g' operator will be used for any of them when the property holds for both (then there is no constraint upon g and g'). So, unless stated otherwise, each formula below is universaly quantified on the gs, and constrains g4g' (resp. g5g') whenever g 1 g' (resp. g' 2 g ) is used. As usual, the notation g3 g' 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. Next section shows that they are sufficient for restricting the number of 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 formerly is the order preservation property [Hobbs 1985] 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:

r -1 6 g3g' r (reciprocal avoidance)
Reciprocal avoidance, is over-generalized and causes problems with auto-reciprocal relationships (i.e. such that r=r -1 ). The neighborhood compatibility, while not expressed in [Euzenat 1993] 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) 7r, 7r',r"%g3g'r , 8r 1 ,…r n %g3g'r such that r 1 =r', r n =r" and 7i%[1,n-1] N ! X (r i ,r i+1 )

(neighborhood compatibility)
This property has already been reported by Christian Freksa [1992a] 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 conversion 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.

(4) r % 9 g 2 g 9 r 9 r % g 1 g' r I and r % 9 g 1 g 9 r 9 r % g 2 9 g r

I (inverse compatibility)
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. The cumulated transitivity can be expected: 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 large 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 relationship 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, the requirements are so precise that they leave no place for choice. It is shown 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 : {<=} ; < {<=>} = no info
Table 5. The six possible conversion operators for = and <.

There are still six possible conversion operators left (Id, :, ;, <, = and NI). Since the above table does not consider whether the operators are for downward or upward conversion, this leaves, a priori, 36 upward-downward 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, :-;, <-<, =-= 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 <-< has no general flaw, it seems just odd to have an auto-inverse operator (i.e. which is its own inverse) since upward and downward conversion are perceived as asymmetric; 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, < does not respect vectorial properties such as order-preservation (< is just ; plus the non distinction between < and >). Thus the :-; pair is chosen as downward/upward operators. The main argument in favor of :-; 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 begining of the bumper is before its end), B + <H -(the end of the bumper is before the begining 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 :-; which allows to convert B + <Hinto B + =H -(= % ;<) and B -=B + into B -<B + (< % :=), but not with the use of < 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 (5).

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 (6) 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 (5).

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 Bneighborhood (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.

Extension to spatial relations

Qualitative time representation has inspired several extensions towards qualitative spatial representation [START_REF] Hernández | Qualitative representation of spatial knowledge[END_REF]]. However, there is no universally acknowledged representation. In [Euzenat 1994], two of them, which can be considered as the simplest (those of [Güsgen 1989] and [Egenhofer& 1992;[START_REF] Randell | [END_REF]), have been provided with granularity operators by applying transformations to the temporal operators. These two schemes are either too rigid or too loose. The ideal solution would be to treat independently concepts such as containment (topology) or orientation (vectorial spaces). There are various ways to deal with orientation: global reference frame [Güsgen 1989], global sectorial reference frame [START_REF] Hernández | Qualitative representation of spatial knowledge[END_REF]] and local (to each object) sectorial reference frame [Freksa 1992b]. Granularity has been introduced in the former while the two latter introduce a new problem: the expression of orientation is also subject to granularity. However, the formal treatment presented above does only consider the structure subject to granularity. Such a structure <!, -1 ,×,N> is made of:

• a set of relations !;

• a converse operator (! is closed by -1 );

• a composition operation ×;

• a neighborhood relation N.

It seems that such a structure can be given to orientation representation as introduced in [Freksa 1992b;[START_REF] Hernández | Qualitative representation of spatial knowledge[END_REF]]. The existence and unicity of granularity operators, seem intuitively correct, but remain to be proved.

. Related works

Jerry Hobbs introduced the concept of granularity from the non distinguishability of particular terms with regard to a given set of predicates (these terms can be substituted in the range of any of the predicates without changing their validity). Here, the granularity has been 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& | [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, etc.) which offers upward and downward conversion operators for instants and intervals (instead of their relationships). [Euzenat 1993] 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& | [END_REF][START_REF] Ciapessoni | Embedding time granularity in a logical specification language for sychronous real-time systems[END_REF].

. 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) and other operators for other kind of spaces can be derived for the actual operators for time. These operators can be used for combining information coming from different sources and overcoming their contradictory appearance. [Euzenat 1993] provides more results about the relationship between granularity and inference which can be used for implementing reasoning algorithms.

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.

  the continuous transformation of an entity o 1 in relationship r 1 with another entity o 2 can put them in relation r 2 without transition through another relation. The graph of figure 2a represents the graph of conceptual neighborhood N 3

Figure 4 .

 4 Figure 4. The representation and relationship implied by, respectively, a global cartesian reference frame, a global sectorial reference frame and a local sectorial reference frame.

Table 1 .

 1 The 3 relationships between instants x1 and x2.

Table 2 .

 2 Composition table between instant relationships.

	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 .

Table 3 .

 3 The 13 relationships between two intervals x1 and x2.

Acknowledgements

Many thanks to Hany Tolba who carefully commented a longer version of this paper.