Rafael H. Bordini, John A. Campbell and Renata Vieira (1998)

Journal of Artificial Societies and Social Simulation vol. 1, no. 4, <https://www.jasss.org/1/4/3.html>

A version of this article in Portable Document Format (PDF) is also available. The PDF version is recommended if you want to print the article to a laser printer.

Abstract

The paper presents an approach to the description of ontologies used in Multi-Agent Systems as a means to allow interoperability of such systems. It is inspired by a pragmatic theory of intensionality worked out as part of an anthropological approach to agent migration. A new formalisation of how an intensional ontology can be ascribed to a society of agents is presented, together with a first formalisation of the recovery of taxonomical relations from such ontologies. This process of discovering taxonomies is inspired by ethnographic studies in social anthropology. The formalisations are developed using a framework for agent theories, based on the Z specification language. Further, the approach is illustrated by the ascription of an ontology and associated taxonomies for an exotic application: the game of cricket. Finally, several issues related to this approach are discussed.

Keywords:Interoperability of multi-agent systems, pragmatic intensionality, cultural anthropology, inference of taxonomies

Introduction

1.1

We have been dealing for some time with what we have called migration of agents (Bordini 1998, Bordini and Campbell 1995, Bordini 1994, Bordini et al. 1995, da Rocha Costa, Hübner, and Bordini 1994) in the context of Multi-Agent Systems (MAS). The basic idea is that certain individual agents should be able to interact in societies of agents which were designed using paradigms or theories of agents different from their own, or which had different histories of autonomous evolution. We have proposed the use of Cognitive Anthropology (Tyler 1969) as a theoretical foundation and we suggest that fieldwork practice in social anthropology (Bernard 1994) can provide useful techniques for an agent's adaptation to a strange society.

1.2

One consequence of this view is that it is desirable to develop agents that can produce anthropologically-based formal descriptions of the cultures present in arbitrary MAS, in order to help migrating agents in their processes of cultural adaptation. Such formal descriptions must include various aspects of a society (see Bordini and Campbell 1995). In Bordini, Campbell, and Vieira (1997) we have explained how an agent can ascribe ontological descriptions for the terms used in the communication language to a society being observed; this idea was first mentioned in Bordini, Campbell, and Vieira (1996). For this particular problem, we have proposed the use of a pragmatic theory of intensionality, which is based on the work of Martin (1959), and has been revived and adapted to the MAS context by Vieira and da Rocha Costa (1993). Further, we have presented our approach using Luck and d'Inverno's (1995) formal framework for specification of agent theories.

1.3

One possible use of these ideas is interoperation of systems (Genesereth and Ketchpel 1994, Wiederhold 1994). The ideas are particularly relevant if the systems do not employ similar definitions for the terms used to communicate and represent knowledge. Our approach can be seen as a step towards a solution to the problem of ontological mismatch among disparate MAS.

1.4

In this paper, we extend our work on ascription of intensional ontologies to show how an agent can work out the taxonomical relations existing among the terms in the intensional ontology it has ascribed to a society of agents. We have noted that some initial taxonomical relations can be recovered directly from an ascribed intensional ontology. This process too was inspired by the methods used by cultural anthropologists, as we shall discuss later. A taxonomy is clearly important from an agent's reasoning point of view; this has been a recurrent observation in Artificial Intelligence research since the early days. Furthermore, from experience in anthropology, it is known that a taxonomy can be quite revealing about the traits of a particular culture. The extension we present in this paper is, thus, related to a fundamental aspect of the procedures of an anthropologist studying a particular society. We suggest that the same approach is of value for an "anthropologist agent" studying a MAS.

1.5

The next section summarises the main concepts and definitions we have used or created in previous work. These are needed for an understanding of our ideas and the formalisations presented in this paper. Section 3 discusses the elaboration of taxonomies in the context of social anthropology, which has been the main influence on the present extension of our work. We then present the formal specifications in Section 4, while Section 5 shows a case study of those specifications in the context of a game of cricket. The sections that follow contain discussions and an overview of our anthropological approach.

Review of Ascription of Intensional Ontologies

2.1

In this section we review the most important concepts and definitions that we have presented in more detail in Bordini, Campbell, and Vieira (1997). They are essential for an understanding of the specifications we shall present in Section 4. This section is organised according to whether the definitions are from our work on agent migration based on social anthropology, from the underlying pragmatical theory of intensionality (Vieira and da Rocha Costa 1993), or whether they are specific to our work on ascription of intensional ontologies.

Anthropologically-Based Migration of Agents

2.2

We have proposed in Bordini and Campbell (1995) the use of Cognitive Anthropology (Tyler 1969) as a theoretical foundation for the search for inspirations to the treatment of the problems associated with cultural adaptation of agents. In brief, the intention of the cognitive approach to social anthropology is to discover the "organizing principles underlying behaviour" in unexplored societies--i.e., "how different peoples organize and use their cultures" (Tyler 1969)--and to rely on fairly formal methods for specifying theories for each particular culture. That is why cognitive anthropologists have been very concerned with describing arrangements (of which taxonomy is one particular type) for the cultures they study.

2.3

The general idea of providing formal models of each culture is particularly interesting for our counterpart work on computational societies. Not only should an anthropologist agent (AA), ideally, be able to generate a formal description of an artificial culture, but also a migrant agent (MA) could use it in its process of adaptation to that particular target society (TS), which is our label for societies studied by anthropologists agents to which migrant agents might migrate. Ascribing an intensional ontology is part of the work of creating cultural descriptions of agent communities. Taxonomies expressing relations among the terms used in particular societies of agents should also be present in their formal cultural descriptions. The way anthropologists elaborate their taxonomical descriptions (see Section 3) has led us to realise that we can (as we show in Section 4) recover taxonomical relations in intensional ontologies that our anthropologist agents have ascribed, using the approach in Bordini, Campbell, and Vieira (1997), to particular societies of agents.

2.4

We have also shown that research methods in anthropology (Bernard 1994) can provide useful techniques for an agent's adaptation to a strange society. One of them, which is based on the idea that choosing key informants is of fundamental importance in ethnographic work, is to incorporate in societies of agents the idea of informant agent (IA). For this particular work, the informant agents for each target society should be able to give accurate information about the terms whose definitions are being ascribed by the anthropologist agent to that target society.

Subjective Intensionality

2.5

This section covers only the main concepts related to subjective intensionality which we shall use next. We have given a larger account of these concepts and some discussion of its advantages in Bordini, Campbell, and Vieira (1997); for further details it is necessary to refer to (Vieira and da Rocha Costa 1993). These concepts will be made clearer when we use them in the formalisation presented in Section 4.

2.6

The intension of an expression is what is known about it in order to identify the object/entity to which it refers. We can say that intension is related to notions of mental entities, properties, relations, and concepts, while extension is related to objective entities (i.e., objects, structures). Further, we have the concept of subjective intensions. These are associated with the intuitive notion of connotation of a term or name; that is, related to the properties that are associated with a term in an individual's mind in such a way that they are normally borne in mind when the individual uses that term at a certain time^[1]. Further, quasi-intensions are linguistic reductions of the mental entities relative to intensions. Therefore, the terminology subjective quasi-intensions emphasises that the theory deals with virtual classes of expressions related to particular users of the language; in other words, it is a linguistic reduction of the cognitive notion of connotation.

2.7

In order to define subjective quasi-intensions and related notions, the acceptance relation between agents and expressions is introduced. The definition, originally described in (Martin 1959), follows.

Definition 1 (Acceptance Relation).     Acceptance is an empirical relation between users and sentences of a language, observed by an experimenter who asks questions by means of a set of sentences forming a logical theory. Whenever an agent answers affirmatively to (has a positive attitude towards) one of these sentences we say that the agent accepts that sentence (which must belong to the set of sentences given by the experimenter) at that time.

Definition 2 (Subjective Quasi-Intension).     The notion of subjective quasi-intension for an individual constant (term) is defined as the properties associated with the term as expressed in the sentences which a given language user accepts at a certain time.

Definition 3 (Intersubjective Quasi-Intension).     This concept regards groups of language users, rather than individuals, at a certain time. An intersubjective quasi-intension is the equivalence class of all the subjective quasi-intensions of a certain group of users of the language.

2.8

Intertemporal Quasi-Intensions are relative to a particular language user at all times. Objective Quasi-Intensions can also be defined on the basis of acceptance. They are at the same time the intertemporal and intersubjective quasi-intension of expressions, that is, a class whose members are members of subjective intensions of all language users at all times. They are said to be an essential property, as they are universally accepted (within a specific community). One last type of quasi-intensions is that of Societal Quasi-Intension which relates to a particular group of agents^[2]. In Martin's theory, Co-Intensiveness is defined as a relation between terms that have the same subjective quasi-intension (or indeed for any of the types of quasi-intensions mentioned above).

2.9

In this theory, a proper understanding of a concept can be defined as the situation in which the subjective intension of a term relative to an agent is the same as the intersubjective intension of all agents, some expert group or a specialist.

Intensional Ontologies of Terms

2.10

We here take ontology to mean very much the same as proposed by Gruber (1993), i.e. the definition of a set of representational terms^[3] (stated as a logical theory). However, it is important to bear in mind that the theory of intensionality presented here deals only with individual terms. The major contribution of this approach to description of ontologies is that its underlying theory allows us to work towards providing agents with mechanisms for dealing with ontologies themselves.

2.11

The following definition expresses our conception of ontology:

Definition 4 (Intensional Ontology of Terms).     An Intensional Ontology of Terms (IOT) is a set of terms where each one is associated with the minimal set of predicates (properties) that is necessary and sufficient to distinguish (unequivocally) itself from every other term in the universe of discourse of a communicating society of agents.

2.12

In this approach, the definition of a term is a set of predicates that are considered to hold for that term. It is important to appreciate that not all predicates that hold for the term are needed for its ontological description: there is a difference between knowledge representation and commitment to ontological conventions (Gruber 1993). Therefore, if some notion of order for the predicates is available (e.g. a hypernymy relation^[4]), this can reflect on the minimal set of predicates: it would include only the most generic ones which are enough to distinguish the term unequivocally.

Ascription of Intensional Ontologies of Terms

2.13

We have seen above that, based on quasi-intensions, a definition for an expression can be given by a set of properties that are accepted by a group of agents as being related to the expression. This is the key point for allowing an anthropologist agent to ascribe an ontological description to a community of agents; it can do so by interviewing the group of informant agents that it takes from that particular community. Terms that have a unanimous definition among the informant agents should be registered in the construction of an ontology for that community. It is important to note that the anthropologist agent itself needs a theory (i.e., a set of attributes for each term) with which to interview the informant agents. The sentences in this theory will be submitted to the informant agents in order to check whether they accept the sentences or not. In general, the set of sentences to be used in an interview should be the result of observations of the use of language in that society, in the fashion of ethnographers.

2.14

We have argued in Bordini and Campbell (1995) that an anthropologist agent can use its past experience with other communities in its current fieldwork with an unfamiliar society. This idea also applies for the problem of creating the set of sentences to be used in the interview. The initial theory for a term to be tested with the informant agents can be taken from previous experiences with other communities or from the definition of that term for the anthropologist agent itself. In case of completely unknown terms, for which observations of communicative actions in the society also do not lead to a useful set of hypothetical sentences, a more elaborate interview will have to take place. The anthropologist agent should then ask the informant agents to state all sentences they have associated with that term in their knowledge representation, instead of just asking them to confirm or deny an initial theory. Once the anthropologist agent has an initial theory obtained from at least one informant agent, it can proceed with the interview as described before. It is reasonable to expect that not all informant agents in all societies will be able to participate in this more complex form of interview. However, in most cases the anthropologist agent should be able to figure out a reasonable initial set of sentences, and in these cases our approach requires very little from the informant agents (only that they be able to accept or reject sentences of the language they use). This is a great advantage of the approach, as our aim is to restrict or interfere as little as possible with societies of agents while still allowing them all to interoperate.

2.15

Finally, for societies with reduced communication languages, it may be worth presenting all possible sentences (instead of wasting time with observations) for the informant agents to verify them. It appears that the creation of the set of sentences to be used in interviews is culture-dependent (how complex the interview can be depends on how elaborate the society is). In any case, it should be based on observations of the language use in particular societies. The techniques that anthropologist agents may use for this can also be drawn from the types of observations carried out by social anthropologists. However, they are not in the scope of the present formalisations.

Discovering Taxonomies in Social Anthropology

3.1

This section describes the approach to ethnographic study of cognitive systems as seen by social anthropologists of the cognitive school, and the main concepts involved in the elaboration of taxonomies by anthropologists. It relies heavily on the ideas presented in Frake (1969), which have allowed us to see that our previous approach to ontologies contained the necessary means to augment ascribed ontologies of terms with the description of the taxonomical relations among those terms.

3.2

A common practice among ethnographers is simply "getting names for things" by, e.g., pointing or holding up apparent objects, eliciting their native names and matching them with the investigator's own words for the objects. Instead, Frake proposed the redefinition of the task as one of "finding the 'things' that go with the words" (which, interestingly, resembles the task of our proposed anthropologist agent which must elicit the properties of the words it observes in the traffic of messages in a target society).

3.3

Cognitive anthropologists have redefined the task in that way because of their understanding that objects^[5] must be defined according to the conceptual systems of the people being studied rather than that of the anthropologist/ethnographer. They are interested in finding out what are the "things" that the members of that community find relevant in their environment. This leads to the discernment of how they interpret their world of experience from the way they talk about it, therefore moulding the "analysis of terminological systems in a way which reveals the conceptual principles that generate them." (Frake 1969).

3.4

Frake goes on to say that different peoples see "things" differently, and mentions that in the past anthropologists sometimes believed this to indicate deficient abstractive ability in primitive societies. He quotes an example concerning a Brazilian Indian tribe which allegedly has no word for parrot but only words for kinds of parrots. These Indians clearly have a mode of classification for the birds they see which "means that individual bird specimens must be matched against the defining attributes of conceptual categories and thereby judged to be equivalent for certain purposes to some other specimens but different from still others. Since no two birds are alike in every discernible feature, any grouping into sets implies a selection of only a limited number of features as significant for contrasting kinds of birds." Further, the features that are significant are learnt culturally (by every individual from his fellows). Therefore, there is no reason why Brazilian Indians should consider the same attributes which, for an English speaker, make equivalent all the individual birds labelled parrots. Knowing how those Indians group objects and which attributes they select as dimensions to generate their taxonomies helps in the construction of a sketch map of the world in the view of the tribe (Frake 1969). Accordingly, we find that some treatment of taxonomical relations must occur in computational societies if one is trying to facilitate migration of agents. We are now able to generate taxonomies (as we shall show in the next section) with the explicit purpose of allowing migrant agents to use a target society's language; but we believe that, in the future, much can be learnt by migrant agents about the culture of target societies by analysing formal descriptions of ontologies and of taxonomical relations among the terms that occur there (see further discussion in Section 6).

3.5

One might wonder whether (or why) a culture's terminological system is really revealing about the cognitive world of its members (even if not exhaustively so). On this point, it suffices to quote Frake: "Culturally significant features must be communicable between persons in one of the standard symbolic systems of the culture. A major share of these features will undoubtedly be codable in a society's most flexible and productive communication device, its language. ... To the extent that cognitive coding tends to be linguistic and tends to be efficient, the study of referential use of standard, readily elicitable linguistic responses--or terms--should provide a fruitful beginning point for mapping a cognitive system." In MAS that is particularly true, as the communication language is likely to include all the terms used for cognitive purposes. Our approach to ontology (which, incidentally, concerns only terms) is comparable to ethnography of communication (Hymes 1977) and should therefore be a well-based starting point for a treatment of MAS resembling cultural anthropology.

3.6

Next we introduce the concepts related to the method of arrangements used by anthropologists that is of concern here, namely taxonomies:

Segregate

A terminologically distinguished array of objects is a segregate^[6].

Contrast

Culturally appropriate responses which are distinctive alternatives in the same kinds of situations (i.e., occur in the same "environment") can be said to contrast.

Contrast Set

A series of terminologically contrasted segregates forms a contrast set.

Attributes and Dimensions of Contrast

The criterial attributes which generate a contrast set fall along a limited number of dimensions of contrast, each with two or more contrasting values or components (see further comments below). For example, if in a particular culture a contrast set includes a term for the segregate of 'woody plants', another for 'herbaceous plants' and another for 'vines', two dimensions of contrast may be used in the classification of objects: woodiness and rigidity. The first segregate includes objects having attributes "woody" and "rigid", the second "not woody" and "rigid", and the third "not rigid".

Inclusion

The notion of contrast cannot account for all the significant relations among segregates. Some of them include a wider range of objects than others and are subpartitioned by a contrast set. Those with a wider range are said to include each of the segregates in their subpartitioning contrast sets.

Taxonomy

A system of contrast sets where some segregates in different contrast sets may be related by inclusion is a taxonomy.

3.7

It is helpful to make some observations about various consequences of the definitions above:

• Segregates are categories, but not all categories known or knowable to an individual are segregates by the definition above. Segregates are categories designated by particular speech units (terms).
• When one makes a decision about the category membership of an object (by giving it a verbal label), one is selecting a term out of a set of alternatives. When one asserts "This is an X" one is implicitly stating that it is not other things, which are not all conceivable things but those alternatives among which a decision was made. These alternatives are what characterise a contrast set.
• The cognitive relation of contrast is not equivalent to the relation of class exclusion in formal logic and set theory. Two categories contrast only when the difference between them is significant for defining their use. In other words, having three categories that are mutually exclusive as far as membership is concerned does not mean that they form a contrasting set (i.e., distinctive alternatives in a classifying context).
• To find the relevant attributes is an important task, because having a list of known members of a category is not sufficient to decide how to categorise objects properly. One must find out what natives know in order to classify an object correctly as belonging to a specific segregate or to distinguish objects that belong to contrasting segregates in their cultural context. (This is another connection with our approach to ontology: we register the properties, i.e. attributes, that are relevant for a term, which allows the classification of objects as belonging to the segregate it denotes). As Frake puts it, "Categorization, in essence, is a device for treating new experience as though it were equivalent to something already familiar." A definition of a category in a particular culture is not given by a list of the specimens it contains but by a rule for distinguishing newly-encountered specimens of that category from contrasting alternatives. Again the maxim of the approach of cognitive anthropology stands out very clearly when Frake says: "The distinctive 'situations,' or 'eliciting frames,' or 'stimuli,' which evoke and define a set of contrasting responses are cultural data to be discovered, not prescribed, by the ethnographer. ... It is those elements of our informants' experience, which they heed in selecting appropriate actions and utterances, that this methodology seeks to discover." This is also the basis of the inspiration of our work.

3.8

Anthropologists (or ethnographers) start their work by recording culturally significant noises and movements from what is heard or seen during observation of a particular community. Recording complementary names applied to the same objects (and eliminating referential synonyms) may yield a recorded sequence like^[7]:

Object A is named: something to eat, sandwich, ham sandwich.
Object B is named: something to eat, pie, apple pie.
Object C is named: something to eat, pie, cherry pie.
Object D is named: something to eat, ice-cream.

3.9

The diagram of the sub-partitioning of the segregate 'something to eat', as revealed by the naming responses to the four objects above, is in Figure 1.

  

Fig. 1 Sub-partitioning of the Segregate 'Something to Eat' Based on the Naming Responses of Objects A-D (adapted from Frake 1969)

3.10

This resembles remarkably our approach to intensional ontology. It therefore allowed us to realise that we already had all the information we needed for the generation of taxonomical relations. Instead of complementary names applied to each object, we have the properties (attributes) that characterise each term in the communication language. Accordingly, by retriving properties in common and those that differ, we should be able to do exactly the same as ethnographers do, and actually create taxonomies extended with the relevant attributes used to classify objects in one or other segregate. This is what we present in Section 4.

3.11

The ethnographers' work in arriving at diagrams like the one above from their observation and recordings can involve complications, which are not mentioned here. The reader interested in further details of the proceedings of anthropologists should refer to our source (Frake 1969). One can also find there: the advantages of the use of a taxonomy (e.g., regulation of the amount of information communicated about a particular object in a given situation, hierarchical ordering of categories), with which researchers in the Artificial Intelligence are already familiar; and what are the factors that are likely to determine the degree of elaboration of taxonomies along vertical dimensions of generalization and horizontal dimensions of discrimination in particular cultural contexts. For those who need reminding, the source says about taxonomy's use that "it is a fundamental principle of human thinking."

3.12

Another aspect of ethnographic work that is clearly relevant for counterpart computational work on MAS concerns the verification of generated taxonomies. Once a taxonomic partitioning has been worked out, anthropologists have to test it systematically for terminological contrast by means of questions such as "Is that an X?" with an expectation of a negative reply^[8]. Using the lunch counter example again, one could point out an apple pie and ask the questions below at the left, to which the answers at the right, reflecting the taxonomy presented above, would be expected:

"Is that something to drink?" "Is that a sandwich?" "Is that a cherry pie?"

"No, it is something to eat." "No, it is a pie." "No, it is an apple pie."

3.13

Frake mentions that "it is easier to do this kind of questioning in a culture where one can assume the role of a naive learner." This is exactly how our anthropologist agents should behave, but it does require that societies of agents provide informant agents that are willing to cooperate, as we have remarked in Bordini and Campbell (1995).

3.14

The similarities also apply at the level of the general motivations of our work. Frake concludes his paper by saying that the real content of culture is how people organise their experience conceptually so that it can be transmitted as knowledge from person to person and from generation to generation. He quotes W.H.Goodenough in saying that culture does not consist of things, people, behaviour, or emotions, but the forms or organisation of these things in the minds of people. The principles of a particular culture reveal how people within it segregate the pertinent from the insignificant, how they code and retrieve information, how they anticipate events, how they define courses of action and make decisions among them. One of the consequences of this approach to ethnographic description (giving central place to the cognitive processes of the actors involved) is that it should result in "descriptions of cultural behaviour, descriptions which, like the linguists' grammar, succinctly state what one must know in order to generate culturally acceptable acts and utterances appropriate to a given socio-ecological context". This is exactly our goal, except that the 'socio-ecological context' concerns computational agents rather than living organisms. The cognitive approach to anthropology also aims at pointing up critical dimensions for meaningful cross-cultural comparison (as do we in our anthropological approach to MAS) and contributing reliable cultural data to problems of the relations between language, cognition, and behaviour, which is also a key problem for the MAS community.

3.15

This concludes the description of ideas from outside the MAS area that have influenced our most recent work. We now turn to a formal presentation of our approach.

Formal Specifications

4.1

In this section, an improved formalisation for the process of ascription of intensional ontologies (Bordini, Campbell, and Vieira 1997; 1996) is given, together with a formalisation for retrieval of taxonomical relations. We make reference to the framework for formalisation of agent theories specifically, which was elaborated by d'Inverno and Luck 1998; d'Inverno and Luck 1996a; 1995; Luck and d'Inverno 1996) based on the Z formal specification language (Spivey 1992, Potter, Sinclair, and Till 1996). We provide, in an Appendix, some basic ideas of the Z notation; however, some familiarity with formal specification methods and mathematical and logical notions is assumed.

The Basic Setting

4.2

Before we introduce the formalisation of how an anthropologist agent can ascribe intensional ontologies to societies of agents, the basic setting in which it can occur must be presented (this is much improved in comparison with our previous formalisation). This section introduces the basic types used in the formalisation, and provide the specifications for informant agents, target societies, and some global functions needed in the rest of the specifications for access to available target societies and to deal with time instants.

4.3

We begin by introducing the basic types:

and the following abbreviation for the type Sent:

where TimeInstant is taken to be the set of constants representing time instants as it is intuitively understood. Term is the set of terms (also called individual constants) of the Communication Language (CL) used by the agents in any target society^[9]. Pred is the set of predicative constants (predicates) from CL. A sentence (Sent) of CL is a pair containing a predicate and a term, meaning that the term has the property (attribute) indicated by the predicate. We consider here only sentences of this sort; the consistent acceptance of sentences including the logical connectives by communicating agents within the quasi-intensional approach is given in Vieira and da Rocha Costa (1993).

4.4

We now present the definition of an InformantAgent, which is built on the definition of AutonomousAgent that is part of Luck and d'Inverno's framework (see, e.g., d'Inverno and Luck 1996a). The only requirement that we impose on the agents that will work as Informant Agents (IA) to the Anthropologist Agents (AA) (the specification of AA is in the next section) is that they make available an acceptance relation accepts, in the sense of acceptance we mentioned in Section 2 (note that the relation accepts is used in the prefix notation). This should be seen as the interface between IAs and the world, as it is how AAs access the information they need from these agents (for the particular purpose of ontological ascription). The type of the relation makes it clear that each individual IA may or may not accept a certain sentence s of its CL, given a set of sentences S, at one particular time instant ti.

4.5

The single explicit constraint in the predicate part of the schema above says that IAs only manifest their acceptance of sentences which have been presented to/inquired of them by an AA; this is how (Martin 1959) conceived it in his theory of subjective intensionality. Clearly, this is not sufficient to specify whether an agent accepts a sentence or not. However, the definition of accepts is purposely left loose. A complete definition of that relation would need to refer to particular informant agents' mental states and their architectures (and this is of course not desirable in a project aiming at interoperability). For example, if the informant agent works as a theorem prover (Fisher 1995), accepting a sentence means simply trying to prove it, and accepting it if it is a theorem in the present set of beliefs of the agent. If the IA is a database system with an agent "wrapping" (Genesereth and Ketchpel 1994), all that is necessary is to check whether the information affirmed in a particular sentence is consistent with the information in the database or not. However agents work, it should always be quite straightforward for designers of agent systems to add this relation as an interface to some particular agents so that they can work as IAs. This is the only requirement that we impose to allow interoperation of agents as far as ontological ascription is concerned. It appears to be quite a reasonable one (especially when contrasted with the degree of constraint implied by the alternative approach of having everything standardised).

4.6

Having defined the state space of informant agents, we can now show what designers of societies of agents need to add to their systems so that ascription of intensional ontologies can occur (i.e., the specification of TargetSociety below). Before that, we introduce two more basic types. These are the set of constants used as identifiers to TSs (TSocId) and to IAs (InfAgId). The anthropologist agents and the migrant agents (presented below) should be able to refer to all existing societies of agents (the former analyse them and the latter may need to migrate to them), and for each TS its set of IAs must be identified as well (by the AAs only; remember that AAs can only ascribe IOTs by relying on the IAs of each society). That is why we introduce the following basic type for the constants used for identification (of TSs and IAs).

4.7

A TargetSociety is based on the schema MASystem defining what a MAS is (d'Inverno 1998, Section 4.2.2) to which we add all the necessary features for a society of agents to be a target society (that is, agents can, in our approach, migrate to them). It has a partial injection iag from informant agents' identifiers to the actual informant agents in the society. This is used to access the IAs in that particular society (which is why a partial injection is used: two identifiers cannot correspond to the same IA). In order to make certain predicates to be introduced later easier to specify, we add a variable ias which is constrained to contain all members of the current domain of iag (in other words, it contains the set of all identifiers of the IAs that are available in that TS). It is necessarily a non-empty set () because, as we have said, informant agents are fundamental in this context. Further, a TS has three non-empty sets related to the CL used in it. First, clterms is the specific set of terms used in that particular CL. Second, clpreds is the set of predicates (or predicative constants) of that CL. As one can see in the predicate part of the schema below, these sets are defined by checking all the terms and predicates that happen to exist in the acceptance relations of all IAs. Finally, clsents is the set of all possible sentences created from the particular terms and predicates of that CL.

4.8

We now introduce in the axiomatic description below some global variables and functions, which will be needed in the rest of the specifications. The bijection tsoc gives a mapping between target society identifiers and actual TSs (there should be a one-to-one correspondence between them, thus a bijection). This is to represent the idea that all existing societies of agents should have an identification, and that there is always a way to access the actual TS through their identifiers^[10]. Again for simplicity, we add a variable tsocs which contains the set of identifiers for all existing TSs (i.e., all members of the current domain of tsoc).

4.9

Because some of the concepts to be formalised are dependent on time, we need some definitions for handling it. An injective sequence over time instants the_time must be available. It is supposed to be the clock of the system: it defines the order in which each constant of type TimeInstant occurs. Being an injective sequence, it is assured that a constant denoting a time instant occurs no more than once over time, and we must add a predicate saying that all possible time instants are present in the range of the sequence the_time, thus giving a complete order for their occurrence. We then have a binary relation (in infix notation) before_eq stating whether a time instant t₁ either occurs before or is the same as a time instant t₂. It is defined by checking whether the natural number associated with t₁ in the sequence the_time (we do this by using the inverse relation denoted by "~" superscript) is less than or equal to the one associated with t₂. It will make our next definitions easier if we provide a global function most_recent which, given a non-empty set of time instants, returns the one that is most recent (i.e., the last to occur, the one with the largest number associated with it in the domain of the_time). This is easily defined in terms of the relation before_eq, by means of a -expression which gives the one ti in the provided set of time instants for which it is true that each time instant in the provided set either occurs before ti or is ti itself.

4.10

Given these basic definitions, we are now ready to see how an anthropologist agent can ascribe an intensional ontology to a target society.

A New Formalisation of Ascription of Intensional Ontologies

4.11

First we define abbreviations for some types which will be used later. Referring back to Section 2 makes it easy to understand that the signature IntensionalOntologyOfTerms is a partial function from terms to non-empty sets of predicates. It is a partial function because it is possible that the AA will not be able to find definitions for all terms used in the TS (and TS itself only uses a subset of them), but if there is an entry for a term in the IOT, then there must be a non-empty set of predicates which defines it. Referring to Section 2 leads to the definition of the type SubjectiveQuasiIntension: the subjective quasi-intension of a term, for a particular IA, who is from a TS , given a set of sentences (informed by an AA), at a specific time, is a set of predicates which are the properties that the agent accepts as being related to that term. Note that this can be an empty set of predicates if it happens that the IA does not know the particular term in question. The type IntersubjectiveQuasiIntension is the same, except that it does not depend on a specific IA (recall that these are relative to the whole group of IAs from a particular TS).

4.12

We now give axiomatic definitions for the functions subjective_quasi_intension and intersubjective_quasi_intension, which will be used later (when defining the ascription of IOTs). For all terms t used in the CL of that TS, all ia that are informant agents of a target society ts, all sets of sentences S (which are necessarily from that TS's particular CL), and all time instants ti, the subjective_quasi_intension of t, for an ia from ts, given S, at time ti, is the set of predicates that ia accepts as being associated with term t, for the set of sentences S, at ti. The intersubjective_quasi_intension of t in the TS ts, given S, at ti, is the set of predicates accepted by all informant agents from ts: it is the intersection of the subjective quasi-intensions of all IAs from that TS for that term t (again given S and ti). Note that we need to make use of the tsoc function and of the TS's iag function to map from identifiers to actual TSs or IAs. We also give below the definition of co_intensive which is a predicate that holds when two terms have the same set of predicates associated with them in a given intensional ontology of terms (note that in this case we refer to co-intensiveness of intersubjective quasi-intension, which is used in the ascription of ontologies, as we see later).

4.13

The definition of AnthropologistAgent is given below. It is based, as for the definition of IA, upon the fact that it is an AutonomousAgent (provided in the framework) with some additional particular features.

4.14

We first say that an AA is able to generate the questions that are needed to interview the IAs (function generate_sentences). It is evident that this function is not properly defined in the predicate part of the schema below. The process of generating the necessary questions (i.e., the set of sentences that are submitted for IAs to accept or reject) is discussed in Section 2, but no formalisation is as yet available for this. However, it is known that the generation of sets of sentences is dependent on the target society and the particular time instant when the interview will take place, thus the signature of generate_sentences is as given below. Note that this function can return an empty set in situations where the AA does not have much experience with a particular TS at a particular time.

4.15

Next, there is the function history_of_intensional_ontologies. This is the most important part of AAs because it keeps track of all IOTs an AA has ascribed. Because a TS's IOT may vary over time (we shall comment further on this later), the function history_of_intensional_ontologies maps a pair stating a TS and a time instant to the IOT that was ascribed to that TS at that time.

4.16

The two items mentioned above are the important aspects of AAs, but we have included a few more variables in the schema in order to make the access to the information from the AA easier in later specifications. The set known_societies records all TSs that have been analysed by a particular AA so far; it is the set of all TSocId that appear as the first members of the pairs belonging to the domain of history_of_intensional_ontologies. There is also all_versions which is a function that, given a target society identifier ts, provides all the time instants at which IOTs were ascribed to ts, provided, of course, that ts is in the set of known_societies. Finally, current_ontology maps ts (which is as before) to the time interval ti that is the most_recent of the time intervals associated with all_versions of IOTs existing for that ts in the history_of_intensional_ontologies. We also provide a relation which may be useful for migrant agents' reference: it is current_synonyms which is a (reflexive and transitive) relation over terms created with the help of the predicate co_intensive given above in regards to the current_ontology from each particular target society ts.

4.17

Having defined the state space of AnthropologistAgent, to be precise with the Z method we now need to say what are the initial values for the variables in it. The only relevant variable is history_of_intensional_ontologies', and its initial value is evidently the empty set.

4.18

We can now specify the operation AscribeIntensionalOntologyOfTerms, which alters the state of an AA ( ). This operation is given two inputs: ts? is the target society for which an IOT should be ascribed and the time ti? when the ascription is taking place. The operation consist of asserting that history_of_intensional_ontologies' should be overridden from its previous definition to map the pair (ts?,ti?) to the IOT which maps each of the terms of that TS to its intersubjective quasi-intension, provided this is not an empty set^[11]. The set of sentences S that must be provided to the function intersubjective_quasi_intension as a parameter (alongside ts?, ti? and, of course, the term t) is produced by the function generate_sentences for that particular ts? at ti?.

4.19

In brief, the non-empty intersubjective quasi-intension of a term is its definition, in our approach. When the intersubjective quasi-intension is an empty set, the AA cannot ascribe a definition to that term. Recall that by the type of the IOTs (i.e., a partial function) we express the fact that there may not be definitions for all existing terms.

4.20

Because agents only accept sentences that are in the set of sentences they were given by an AA (stated in InformantAgent), and the intersubjective quasi-intension of a term is based on accepted sentences (stated in the axiomatic descriptions), and an ascribed ontology only contains those terms whose intersubjective quasi-intensions are non-empty (in the schema above), we can derive the theorem below which concerns the state space of AnthropologistAgent (but only now are we able to introduce it). It says that if there is a term t in an ascribed IOT, it is guaranteed that there was at least one sentence concerning that term in the set of sentences generated by the AnthropologistAgent. (A corollary would be that if the set of generated sentences is empty, the ascribed IOT is an empty set too).

4.21

We emphasise that, given that we use the notion of intersubjective quasi-intension, which is time-specific, for the definitions of the terms in the ontology (see AscribeIntensionalOntologyOfTerms), these definitions may not be valid ad infinitum. Thus, the anthropologist agent may need to review the ontology it has ascribed to a particular society from time to time, as autonomous evolution within societies takes place or the AA alters its set of IAs, or the AA's set of sentences to be given to the IAs is changed, etc. That is why we refer to this type of ontology as evolutionary, since we intend agents to be able to improve them with time. Since in our definitions we state that AAs keep track of the whole history of ontologies they have ascribed to each of the TSs, this allows one to analyse how that TS has evolved as far as ontology is concerned. Some agents may be able to analyse the historical evolution of ontologies provided by an AA: one could find it interesting in the future to consider historian agents, or linguist agents interested in agent archaeology, who might make use of that information.

4.22

However, based on the concept of objective quasi-intentions (see Section 2), some subset of the ontology may form an immutable part of it, composed of the terms universally accepted in that community. In order to deal with this point, we start by providing abbreviations for the types (as we did for subjective and intersubjective quasi-intension). One should note that IntertemporalQuasiIntension is the same as SubjectiveQuasiIntension except that it does not depend upon TimeInstant. Likewise, ObjectiveQuasiIntension is the same as IntersubjectiveQuasiIntension except for the dependence on time; alternatively, one can see ObjectiveQuasiIntension as based on IntertemporalQuasiIntension except that the former does not concern particular informant agents.

4.23

The axiomatic description below states that the function intertemporal_quasi_intension, given a term t, informant agent ia, target society ts, and set of sentences S, yields a set of predicates which ia accepts as being associated with term t at all times, given the set of sentences S. The objective_quasi_intension of t in society ts, given S, is the set of predicates accepted by all IAs from ts, for that term, at all times: it is the intersection of the intertemporal quasi-intensions of all IAs in that TS for that term t (again, given S).

4.24

In order to say that AAs may also provide immutable intensional ontologies, based on the concepts specified above, we introduce the schema ExperiencedAnthropologistAgent which is built on the schema AnthropologistAgent and includes a function immutable_intensional_ontology which maps TSs to IOTs (it does not depend on time as before, as these IOTs are the ones that are not supposed to change). As in the case of history_of_intensional_ontologies, it only maps terms that have a non-empty set of predicates to define them, except that in this instance the set of predicates is given by objective_quasi_intension instead of intersubjective_quasi_intension. Note that the TS identified by ts must necessarily be in the set of known_societies of that AA, and the set of sentences S to be verified by informants is defined here as the union of all sentences that the AA generates for that society at all times (the larger this set is the better, as the chances of finding which are the immutable terms in that society are increased).

4.25

Migrant agents may well find it useful to know which subset of the intensional ontology is immutable. Note that some societies may never keep immutable terms, or it may take a long time to arrive at a sound conclusion that there is a immutable subset of an intensional ontology. There is further discussion on this point in Section 6.

4.26

This completes our specification of ascriptions of intensional ontologies of terms. We continue by considering how to retrieve taxonomical relations from the ontologies that anthropologist agents have ascribed to target societies using this approach.

Retrieval of Taxonomical Relations

4.27

First of all, we describe the type Taxonomy using a free type definition. We first define Segregate (refer to Section 3 for the concepts of segregate, contrast set and taxonomy) by means of the type constructor segregate, which takes a non-empty set of terms and a non-empty set of predicates of the agents' CL. It means that one or more terms (in case of synonyms) are used to refer to a particular segregate in that society and what characterises it is that set of predicates (i.e., the set of properties common to all members of that segregate). In this respect, we are presenting here taxonomies that are augmented with the characteristic properties of each segregate. Therefore, a taxonomy not only gives a logical structure for the terms used to communicate in that society, but it also records the peculiarities of each segregate in the taxonomy (the attributes in the terminology of Section 3), which allows the identification of the objects that belong to them. Evidently, there are circumstances when such information will be very useful for migrant agents.

4.28

A taxonomy is, structurally, a tree. We define the type Taxonomy by means of a type constructor contrastset which takes a Segregate and a set of taxonomies, each one being a subtree representing one of the contrast sets related to that segregate. The leaves of the tree are segregates that have an empty set of Taxonomy for their contrasting sets (i.e., there are no contrast sets for them).

4.29

The axiomatic description below presents four functions which are responsible for the retrieval of the taxonomical relations from IOTs.

4.30

First, segregate_size takes an intensional ontology of terms iot and a predicate p as parameters. It provides the size of the segregate related to that particular predicate in iot. In order to do that, it suffices to count how many terms have the predicate p associated with them in iot.

4.31

Second, find_segregate is always given an iot whose terms all belong to a single segregate; that is, they all have at least one predicate in common. It then produces that segregate and a new IOT siot in the following way. Let P be the set of all predicates common to all terms in iot. Then T is the set of all terms having exactly P as their definition in iot (note that if they have the same set of predicates, they are synonyms). These are the terms that represent the whole segregate (and P is what characterises it), and all other items in iot belong to the segregates that for the contrast set for this particular segregate. We define siot as an intensional ontology which is the same as iot but does not include any of the terms that are in T (as these are already used in the taxonomy, to define the present segregate). Besides, we remove all the predicates (P) that are common to the definition of all the remaining terms (the ones in siot); again this information is already in the segregate of which the terms in siot form the contrast set. The function find_segregate then returns the segregate formed by T and P, and also returns siot, to be used by the next function in this process of retrieving taxonomical relations. (Once the common predicates are removed from the definitions of the remaining terms (siot), the remaining predicates can be used to split siot into contrasting segregates, in the next step).

4.32

Third, find_contrast_set is a recursive function which splits iot into a set of IOTs so that each of these IOTs resulting from the split is guaranteed to have at least one predicate in common (that is, all the terms in it belong to a single segregate and can then be used by the previous function). The end of the recursion occurs when the current iot is empty, in which case an empty IOT is returned. Otherwise, the predicate sp which yields the largest segregate^[12] in the current iot is selected and an IOT csiot is created by gathering all terms which belong to that segregate (i.e., have sp in their definition in iot). Thus, the terms in csiot belong to one of the contrasting segregates that is present in iot and the remaining terms in it (iot \ csiot) are given recursively to find_contrast_set for the remaining IOTs (representing the other contrasting segregates) to be added to the final set of IOTs which is returned. We emphasise here that the criteria used to select the segregates for the contrast set (i.e., based on the predicate that yield the largest segregate first) may in some cases create taxonomies which do not have the exact structure used by the IAs. This is why we have mentioned that the taxonomy created is just a clue which the AA should check by interviewing the IAs again in order to determine whether they accept that structure (see further discussion in Section 6).

4.33

Finally, find_taxonomical_relations is also a recursive function which takes an IOT and returns a Taxonomy. Given an iot it returns a contrastset whose Segregate is given by the first coordinate of the pair returned by find_segregate applied to that iot. The set of taxonomies associated with that Segregate in contrastset is created by applying find_taxonomical_relations recursively to a set of IOTs. These are returned by find_contrast_set when applied to the IOT that is the second coordinate of the pair returned by find_segregate applied to that iot. In other words, one creates a segregate, eliminates from iot the terms already used in the creation of the segregate, eliminates from the remaining terms the common predicates (already in the created segregate), splits the resulting ontology into IOTs representing contrasting segregates, and proceeds in the same way for each of them. At some point, find_segregate returns, as second coordinate, an empty IOT which will lead to an empty set of taxonomies (denoting a leaf of the tree) thus ending the recursion.

4.34

One more definition will be necessary for the specifications that follow. The function generate_taxonomical_relations maps an IOT to functions from predicates to taxonomies. The idea is that for each iot there is a function which, given a predicate, returns the taxonomy that can be retrieved in a subset of iot which only contains the terms that have that particular predicate in their definitions. We need this because when the whole IOT of a TS is considered, several of the terms may not be related to each other (in the example to be given in the next section, the ontology includes terms for cricket players bearing no relation to the terms for field divisions in the same ontology). Therefore, it is necessary to give a general subject for which a taxonomy is required before actually proceeding with the algorithm for retrieval of taxonomical relations presented above.

4.35

The first constraint in the axiomatic description below states that for a predicate p to be in the domain of the function yielded by the application of generate_taxonomical_relations to iot, there must exist at least one term having p in its definition in iot. Further, when one applies generate_taxonomical_relations to iot and then applies the resulting function to a predicate p, an IOT piot, containing only the terms in iot which have p in their definitions, is passed as a parameter to the function find_taxonomical_relations defined earlier so that a taxonomy for that particular subject (the predicate p) is generated.

4.36

We can now improve the capabilities of an AA to include the generation of taxonomies as well. The schema TaxonomistAnthropologistAgent is built upon ExperiencedAnthropologistAgent. The function generate_subjects resembles the function generate_sentences, but it is intended to generate a set of predicates (for a given TS at a certain time ti) which are the subjects for which taxonomies exist (or could exist) in that particular TS at ti. Similarly to the process of finding the sentences to be used in the interview, the AA should be able to generate these subjects by means of its observation of the use of the CL of that TS. As in the case of generate_sentences, this process is not yet formalised, so generate_subjects is also loosely defined. Also as before, generate_subjects returns an empty set should the AA not be experienced enough in the study of a TS to be able to decide what are the subjects for which it is worth generating taxonomies in that society.

4.37

Apart from the ability to generate subjects, a TaxonomistAnthropologistAgent makes available a function taxonomical_relations which, given a target society identifier, leads to a set of taxonomies used in that society. The target society represented by ts, for which taxonomies are required, clearly must be in the set of known_societies (otherwise the AA could not have any information about it, let alone generate taxonomical relations). We take ti to be the most_recent of all_versions of IOT existing for that ts. The taxonomical_relations for ts will then be the set of all taxonomies recovered from the current_ontology of ts. Each taxonomy is associated with one of the predicates (subjects) that are generated for that ts at ti (the time at which the current ontology was generated).

4.38

Similarly to the theorem derived from AnthropologistAgent before, we can now derive a useful theorem concerning the schema above. It says that, given that ts belongs to the set of known_societies, ti is the time at which the most recent IOT has been ascribed to ts, and SP is the set of all the sets of predicates that are at the root of each of the current taxonomies for ts ( taxonomical_relations(ts)), the following applies. For each of the sets of predicates in SP, there exist at least one predicate p that: (i) is one of the subjects for ts at ti, generated by an AA ( generate_subjects(ts,ti)); and (ii) at least one term in the current_ontology(ts) has p associated with it. This follows from the definitions of taxonomical_relations (which generates a taxonomy for each of those subjects) and the definition of generate_taxonomical_relations (which selects a subset of the IOT concerning a particular subject).

4.39

A corollary, similar to the one for the previous theorem, would be that if the AA's observation does not lead to indications of what are the main subjects relevant to that TS (i.e., generate_subjects(ts,ti) returns an empty set), no taxonomical relation can be retrieved for it; the same applies if the predicate is one of the subjects but is not present in the current IOT. It is interesting to note that the theorems are similar, the one for AnthropologistAgent being concerned with propositions about terms, whilst the one for TaxonomistAnthropologistAgent is concerned with propositions about predicates.

4.40

This ends the formalisation of the retrieval of taxonomical relations. It is additionally worth formalising a few general ideas about migration of agents, which we examine next.

Migration of Agents

4.41

In order to round off the ideas formalised so far, we present some specifications on migration of agents (showing what is the information that an AA has collected which can be used by migrant agents in their process of migration). Below is the schema MigrantAgent. As before for IA and AA, it is based on AutonomousAgents with a few extra features. Its variable ts identifies the TS that the migrant agent intends to join. Further, two IOT variables are needed, one for the current intensional_ontology from ts and another for the immutable_ontology, in case there is any. Also, there is the relation for the synonyms and the set of taxonomies used in that ts.

4.42

As for AnthropologistAgent, we need to define the initial state for the schema above. We introduce to mean an identifier to an undefined TS. The variable ts' begins with this value, and all other variables stand initially for empty sets.

4.43

Finally, we define the operation Migrate which changes an MA ( ) and also needs the mediation of an AA whose state is not thereby altered ( ). This operation takes as input a TS identifier ts? that must belong to the set of known_societies of the relevant AA. The value of the input ts? is used to set ts'; intensional_ontology' is given the current_ontology for that ts? (i.e., the last IOT the AA has ascribed to ts?); immutable_ontology' gets its value from the function provided in the ExperiencedAnthropologistAgent schema; synonyms' receives the current_synonyms (recall, from the current_ontology) from ts?; and taxonomies' has the taxonomical_relations for ts?.

4.44

We have found, as d'Inverno (1998) claims and demonstrates for applications of a size similar to this one, that Z is an excellent basis for clear specification of agents with special properties. It has allowed a rapid and effective progression from the initial qualitative ideas on agency with an anthropological flavour to the precise form given above, and to theorems that they satisfy. Furthermore, it should allow us to formalise the missing parts incrementally (some are mentioned in Section 6). Building on definitions from Luck and d'Inverno's framework (i.e., AutonomousAgent and MASystem), makes it possible for us to integrate our approach with other agent theories specified in the same framework (e.g., Sichman et al. 1994, see d'Inverno and Luck 1996a), besides the obvious advantage of exempting us from specifying those basic concepts. Also, as d'Inverno and Luck (1996a) indicate, the framework can be used directly in the implementation of simulations of the agent theories that have been formalised. As a matter of fact, we have type-checked these specifications using ZTC (Jia 1995) and animated a simplified^[13] version of them using PIZA (Hewitt 1997).

4.45

Any difficulties remaining from the reading of the formalisation presented should be resolved by the illustration of their use given in the next section.

Case Study: an Ontology from the Game of Cricket and Two of its Taxonomies

5.1

In order to illustrate the meaning of the specifications presented in the previous section, we shall make use of some terms used in the game of cricket. We have made the exotic choice of cricket because we have been using a simulation for the game of cricket as a testbed for some of our ideas (see Bordini and Campbell 1995, Bordini 1998), and because the information content of this example is not trivial. (Routinely, it baffles foreign human observers).

Two Cricket Taxonomies

5.2

A few cricket terms are presented in the form of two taxonomies, some of which will be used later in the example of the use of the specifications. Figure 2 includes some of the terms used to refer to the players. Figure 3 holds terms related to the field where the game is played. In the figures, "..." means that a whole subtree of terms is omitted from the figure (for the sake of space and clarity). In Figure 3, the symbol "*" means that there are alternative and non-exclusive ways of partitioning a cricket field, which we do not mention there.

  

Fig. 2 Taxonomy of Terms Referring to the Cricket Players

  

Fig. 3 Taxonomy of Terms Related to the Cricket Field

5.3

In the next section we shall use a few of these terms to show how an intensional ontology for them can be ascribed to a cricket society of agents. Later, we show how the taxonomical relations among them can be retrieved from the intensional ontology.

Ascribing an Intensional Ontology to the Cricket Society

5.4

The ascription of intensional ontologies relies essentially on the acceptance relations of informant agents. In order to specify their acceptance relations, we first need to introduce the particular set of terms we use, and give acronyms for the appropriate predicates. We do so in the form of the following Z predicates:

where CSoc is a TSocId referring to the cricket society; we say that the cricket society has two informant agents identified by IAg₁ and IAg₂ (only two for the sake of simplicity); and we have used the following acronyms: Human Being (HB), Throws the Ball (TB), Throws the Ball Fast (TBF), Throws the Ball Slowly (TBS), Is Strong (IS), Is Accurate (IA), Carries a Bat (CB), Wears Gloves (WG), location Where the game is Played (WP), Field Partition (FP), to the Left of a Right-handed Batsman (LRB), to the Right of a Right-handed Batsman (RRB) and Centre of the Field (CF). We have also used fastblr for fast-bowler, slowblr for slow-bowler and wicketkpr for wicketkeeper.

5.5

We now define the IAs' acceptance relations. Again for simplicity we assume that all possible sentences ( tsoc(CSoc).clsents) are presented by the AA to the IAs for them to verify each of them, and we only consider one time instant ti₁. In most practical cases, to produce all possible sentences would be intractable, but given the small number of terms and predicates of the CL used here as an example and that the point to be made clear here does not concern the interview (which is not formalised), this simplification is quite reasonable.

5.6

Note that IAg₂ does not agree with IAg₁ with respect to whether a fast-bowler is necessarily strong (IS) or not. Therefore, the AA will not consider this predicate as part of the intensional definition for fastblr, as this is likely to be the consequence of individual observations or experiences of some of the IAs.

5.7

If we execute the operation AscribeIntensionalOntologyOfTerms in this context, that is:

we get the following IOT:

5.8

Note that the AA's relation for CSoc in current_synonyms would be {(on,leg), (leg,on)} (i.e., they are co-intensive terms, or synonyms). We do not give an example regarding immutable ontologies of terms, since we are only representing a single time instant for the sake of simplicity and space.

Recovering the Taxonomical Relations from the Cricket Ontology

5.9

What remains to be illustrated now is how the taxonomical relations can be recovered from the intensional ontology presented in the previous section. We use Tx₁ and Tx₂ as global variables over Taxonomy and we show what their contents are in Figure 4 and Figure 5 respectively, so that their visualisation is made clearer.

  

Fig. 4 Tx₁--Recovered Taxonomy of Terms Referring to the Cricket Players

  

Fig. 5 Tx₂--Recovered Taxonomy of Terms Related to the Cricket Field

5.10

We now show some steps of the generation of the taxonomy Tx₁ above so that the algorithm used may become clearer. We shall use csiot to refer to the IOT created for the cricket society in the previous section. When using generate_taxonomical_relations(csiot,HB) we would get the following new IOT hbiot:

which would be passed on to find_taxonomical_relation. This in turn would call find_segregate(hbiot) which would return a pair, its first coordinate being segregate(player,HB), because HB is the predicate that all terms have in common. The second coordinate returned by find_segregate would be rhbiot, the remaining terms from hbiot:

5.11

Next, find_taxonomical_relations calls find_contrast_set(rhbiot), which returns a set with three IOTs, split according to the largest segregate_size; TB is chosen first because it yields a segregate with three terms, and the same is done until there are no more terms in the IOT to be split. This gives the set of IOTs (a contrast set) cshbiot as below:

5.12

Now find_taxonomical_relations is called recursively to each of the three IOTs in cshbiot and this leads, by the same process, to a set of taxonomies txhbiot. The final result of calling find_taxonomical_relation(hbiot) is contrastset(segregate(player,HB) , txhbiot), which is Tx₁ in Figure 4. A similar process occurs then with generate_taxonomical_relations(csiot,WP), for the taxonomy for field terms, yielding Tx₂, shown in Figure 5. The taxonomies are free of mistakes about cricket and therefore more reliable than the reasoning of some foreign observers of that game.

5.13

We continue by discussing several issues arising from our general method.

Discussion

6.1

The first thing to consider in terms of comparison of our work on ontological ascription with other approaches to ontology, is that a limitation of the approach is that it concerns the use of individual constants only. The suitability of our approach for other sorts of language units (e.g., representing actions rather than individual constants) remains to be studied. Also, it could be claimed that the expressive power of traditional approaches to ontology is greater, since each term has a logical statement associated with it rather than just a set of predicates.

6.2

On the other hand, our approach is, to the best of our knowledge, the only one to consider that ontologies are not designed by programmers or designers of MAS, but that agents may change them evolutionally. More importantly, our approach aims at allowing interoperation of MAS even if we consider that ontologies are neither fixed nor provided in advance by designers, by allowing agents to ascribe ontological descriptions to societies of agents. Further, if we did compromise on expressive power of our approach this was so in order to provide for its generality: as can be seen, even for very simple "informant agents" the method still applies. Additionally, our approach is well-founded, being based on a theory from Pragmatics.

6.3

Concerning the formal specifications we present, we have mentioned that an IOT maps a term to a set of predicates (any set), even though Definition 4 clearly says that the precise definition of a term is necessarily the set of predicates that are necessary and sufficient to distinguish the term from every other term in the universe of discourse of a particular society of agents (unless it has synonyms). In the formalisation, it is not assured that every set of predicates in the range of an IOT conforms to this minimal-set criterion. Therefore, an IOT ascribed to a society of agents is not guaranteed to be either complete or sound by the anthropologist agent. It is simply tentative, and the anthropologist agent should keep studying the society for evidence that it is correctly built. This should done by observing the communication in the target society (the same process that should be used for the generation of the set of sentences to be given to the informant agents in the interview). Therefore, further work is needed on the generation of the sentences used in the interview of informant agents, and on its revision in case the anthropologist agent finds that a wrong definition has been ascribed. On the other hand, an ontological mismatch (between actual and ascribed ontologies) may be due to an actual evolution of the ontology used by the agents, in which case a new ascription was at any rate due.

6.4

The same situation happens in regard to the recovery of taxonomical relations as presented in this paper. The taxonomical relations generated by an anthropologist agent, from an intensional ontology it has ascribed to a society, should be regarded simply as "clues" to what the actual taxonomical relations are. Furthermore, the process of recovery of taxonomical relations should be followed, as is the case with ethnographers, by a confirmation of the relations that were found, e.g., by the anthropologist agent interviewing the informant agents again. This time, instead of the acceptance of sentences, the inquiries to be made should resemble the way ethnographers systematically test taxonomies, by asking questions expecting a negative reply (see Section 3). Better still, the anthropologist agent could ask whether the informant agents accept that two terms denote contrasting segregates or whether they have an inclusion relation (of course this would increase the abilities that are required from the informant agents; they would need to be more specialised agents and understand concepts like segregates, contrast sets, inclusion, etc.). We plan to present the formalisation of this confirmation process in a future paper. As is the case with ontologies, taxonomical relations also may evolve, therefore the anthropologist agents must be attentive to possible changes (in fact, changes in taxonomical relations reflect changes in intensional ontologies).

6.5

Presently, our concern with ontological and taxonomical ascriptions aims at solving the problem of migrant agents being able to use the communication language of the target societies. However, it is widely accepted among anthropologists that a taxonomy of terms is quite revealing about the peculiarities of a society, as we saw in Section 3. Therefore, further research linking social anthropology and MAS should provide useful techniques for migrant agents to use the kind of information we consider in this paper for a more thorough understanding of the target societies, rather than just for a linguistic compatibility.

6.6

As for the ascription of immutable ontologies, one remark is worth making. The amount of time over which an anthropologist agent has been studying a particular society is not taken into account when generating immutable ontologies (in the presented formalisation). Therefore, an immutable ontology could be ascribed even if the anthropologist agent does not have long-term information about the society, in which case the immutable ontology is bound not to be completely reliable (i.e., it may come to change in the near future). In order to determine how long it takes for the use of an ascribed immutable ontology to be advisable, a study with real-life applications using MAS should be conducted, but there is certainly no harm in providing them to migrant agents.

6.7

Our research method, the reader cannot have failed to observe, is basically one of providing formal specifications rather than "informative experimentation," which is more usual in research on artificial societies. On the same lines as (Conte and Castelfranchi 1995), formal here means that we deal with abstract aspects of the subject studied; further, it means "explicit, consistent, controllable and unequivocal (or almost unequivocal) ways of expressing thoughts." Although formal methods for the presentation of research ideas are well accepted in artificial intelligence, some still seem to think that they should be used only for the purpose of theorem proving. Is support of the opposite view, with which we agree, we quote Conte and Castelfranchi 1995: "In any case, we challenge the idea that (logical) formalism is fundamentally aimed at theorem proving. ... A primary objective ought to be to provide good concepts, clear notions, and heuristic categories of description. Logical instruments are essential for concepts and categories of description to be defined in a rigorous, explicit, concise and controllable way." They further say that they are concerned with "producing computational models, and therefore constructing systems performing tasks in accordance with theoretical expectations."

6.8

Further, we support the view that research on Artificial Intelligence (and also Computer Science in general) needs both theoretical support and practical testing, and clearly the theoretical work must come first. There have been plenty of "experiments without theory" and this has not been good for the subjects. Also, formal specification is certainly more on the theoretical rather than experimental side of work, but it has an element of experimentation in it too. Not only can one refine the theory and correct mistakes in initial intuitions (those familiar with formal work know how inevitable this is), but also it points out the parts of the system being built that should be focused on in subsequent experimentation--the parts that proved difficult to produce to one's satisfaction in the specification are the ones in question. Our specification can therefore be regarded partly as an (another kind of) experimental activity.

6.9

The reason for our using, in particular, Luck and d'Inverno's formal framework (1995) based on Z, is that we can rely on specification of other features of autonomous agents (which are necessarily complex systems) being made by other researchers, allowing us to concentrate on the particular problems we have set out to investigate. d'Inverno and Luck aim at providing a unifying framework where effort in different sub-fields of MAS can be harmonised (d'Inverno and Luck 1996b, d'Inverno and Luck 1996a); an ambitious task that is arguably an important current issue in MAS. They claim that Z's modularity and abstraction can be helpful in that enterprise (Luck and d'Inverno 1995, d'Inverno and Luck 1996a; d'Inverno and Luck 1998). Further, on other general advantages of Z itself, they mention its sufficient expressiveness, suitability for moving from specifications to implementation of computational prototypes, the availability of supporting books and tools, etc.

6.10

Concluding the argument on our research method, as for (Conte and Castelfranchi 1995) the main purpose of our specification is in respect of rigorous presentation of ideas. Also, because of the use of the Z framework, we were able to provide a computational model, which is important in the context we are working on, namely MAS. As we have mentioned in Section 4, a simplified version of the specifications presented there has been animated using PIZA (Hewitt 1997). This allows us to verify that the specifications are correct (i.e., that the computations they generate produces results in accord with the theoretical definitions). Besides, it provides a computational tool which can be used for tests in several other domains so as to check the generality of our approach.

6.11

As for the case study presented here, even though the peculiarities of the cricket ontology allow us to demonstrate the nature of our approach to ascription of ontologies and recovery of taxonomical relations, it has, of course, been scaled down in order to serve this purpose here--it is, as usual in AI work, a "toy problem." Issues of scalability to real-world MAS application remain to be addressed. Also, one could consider in the future issues of scalability to human languages (rather than agent communication languages as intended here): anthropologist agents could be conceived to work as "lexicographers," supporting the creation of dictionaries (of human languages).

6.12

As we have mentioned, we are working on an anthropological approach to the cultural adaptation of migrant agents. Evidently, Distributed Artificial Intelligence (DAI) techniques can be used for studies in anthropology (as indeed for all social science)--see, e.g., (Doran et al. 1994, Doran and Palmer 1995), which use artificial societies to study the emergence and perpetuation of hierarchical societies. In Bordini (1998) we aim at showing that the converse also holds: anthropology can provide the basis for resolving open research issues in DAI. Fortunately, Doran's own work presents further evidence in support of our claim. His idea that collective misbeliefs can be beneficial for a society of agents (Doran 1998a, Doran 1998b), which clearly was inspired by his longstanding work on computer simulation of societies supporting anthropological and archaeological models, can have a decisive impact in future MAS. Although the idea has not been used in practical applications of MAS, it seems to be a contribution to MAS design that has a quite general appeal, and is therefore relevant to our overall project, of which the work in this paper is part.

6.13

Doran's work also recognises the importance of emotional aspects of agents in explaining certain social phenomena (Doran 1997). This is connected to other work related to our general project--see (Bazzan, Bordini, and Campbell 1999; 1997)--which argues in favour of an "emotional stance" in MAS. It is inspired by ideas on Moral Sentiments by Ridley (1996), who also argues that emotions are "universally recognisable". Being a necessary cross-cultural link, we expect them to reduce the need for standards in MAS to promote interoperability, which is the usual approach; we however argue that it is not sufficient in the particular context of societies of cognitive autonomous agents (Bordini 1998). Further, issues of moral sentiments in agents seem to be, as we remarked in Bazzan, Bordini, and Campbell (1999), closely related to important research problems in MAS, e.g., (i) how to ensure or encourage adherence of agents to social norms (i.e., conventions), given that emotions can be instrumental in arranging that suitable rewards (for a reputation for compliance with norms) and penalties (for non-compliance) are applied to individual agents (Castelfranchi, Conte, and Paolucci 1998); and (ii) the very formation of norms by autonomous agents (Conte, Castelfranchi, and Dignum 1999).

6.14

We remark, en passant, that the activity of an anthropologist agent ascribing ontologies to communities of agents could be regarded as the computational counterpart of work on the multidisciplinary subject of ethnography of communication (see, e.g., Hymes 1977 and Bauman and Sherzer 1989).

6.15

We present our anthropological approach as a new way of dealing with some basic questions of DAI, the area of which MAS is a part. It implies the relevance for the foundations of DAI of a discipline not normally considered in this context, namely social anthropology. We suggest that it should be among the disciplines of interest to MAS if promoting interoperation of disparate agencies is to grow into a substantial MAS topic. This is the underlying thesis in Bordini (1998). Yet another field of social sciences which has been neglected so far with respect to DAI, despite being of relevance to the area, as the most recent part of this work demonstrates, is ethnography of communication, mentioned above.

6.16

In addition, it is interesting to note that the theories present in both strands of social thought used in this paper (on the anthropological and semantic/pragmatic sides) follow philosophical principles that are familiar to the logical positivist (or logical empiricist) school. It is currently argued that such theories are dead for social sciences because they fail to comply with the intrinsic "human" aspects of the problems involved. However, it seems they still have contributions to make to the computational counterpart problems in DAI, where the formal aspect is essential. Thus, peripherally, this paper also suggests that it is helpful to make further investigation of fairly old work on social sciences as sources of inspiration for "open problems in DAI" (Gasser and Huhns 1989, Gasser 1991). However, we do agree with Gasser (1991), as we stated in Bordini and Campbell (1995), that theories in social sciences more recent than those provide the basic principles underlying the appropriate conception of DAI as an inherently social one. It is a matter of finding the best inspirations for each problem in the most relevant approaches of the social sciences.

Conclusion

7.1

We have presented a new way of specifying ontologies used in societies of agents based on a theory of intensionality, which connects with our previous anthropological approach to migration of agents. It allows intensional ontologies to be ascribed to societies of agents, hence its importance for our anthropological approach which aims at allowing interactions among agents of disparate communities. We have reformalised it here in a an improved and more complete way.

7.2

Further, inspired by works on ethnography, we have presented for the first time a means for an anthropologist agent to recover taxonomical relations from the intensional ontologies it has ascribed to societies of agents, and we have formalised it along with the ascription process. This expanded capability of an anthropologist agent is a necessary step towards the generation of cultural descriptions of societies of agents. Migrant agents should be able to adapt much more effectively to a target society if they are given access not only to intensional ontologies, but also to taxonomies for (subsets of) the terms that are used in the target's "foreign" culture.

7.3

We have also presented an example of our approach using an ontology and taxonomies from a non-trivial ball game, to illustrate the process given in the formal specifications, and to demonstrate that the process is effective even for the exotic culture of cricket.

7.4

This work is part of our project of allowing autonomous intelligent agents to migrate among different societies of agents. The advantage of this approach as opposed to the usual approach to interoperability is twofold, for the kind of MAS that is founded on complex aspects of social and cognitive sciences  (Conte and Castelfranchi 1995). Providing agents that can learn to interact with different communities not only allows interoperation of disparate MAS without the need for standardisation on models and languages of agents, but also brings to light several issues of interest in the disciplines that form the foundations of MAS. Further, we aim at showing the importance of placing social anthropology among the disciplines of interest to an appropriate conception of MAS. The work described in this paper is required if a migrant agent is to be able to use a foreign communication language (which is not merely a fixed language that can be programmed into the design of all relevant agents) properly. We expect to present further extensions, to deal with related problems, in future papers.

Acknowledgements

We acknowledge some nice suggestions from various participants in the CIA97 meeting (see Bordini, Campbell, and Vieira 1997) and the comments made by Mark d'Inverno and Michael Luck on an earlier version of that paper. Michael Luck also helped with the Appendix on the elements of Z and other remarks on its advantages. We thank Antônio Carlos da Rocha Costa and Rosa Maria Viccari for their valuable contributions to the initial conceptions of both the work on subjective intensionality and on migration of agents. We gratefully acknowledge the comments and suggestions by Nigel Gilbert and two anonymous reviewers. We are also grateful to the Brazilian government agencies CAPES and CNPq for the PhD grants to, respectively, Rafael Heitor Bordini and Renata Vieira.

Notes

¹ Since these are notions intrinsic to the users of the language, they can also be called pragmatical intensions.

² We do not formalise the idea of groups of agents (and therefore the concept of Societal quasi-intension cannot be formalised either) in this paper, but the extension should not impose any difficulties.

³ In this particular context, the representational terms are those used in the communication language of a MAS.

⁴ An example in the context of the game of cricket, which is used as a case study in Section 5, is the predicate "is a cricket player" in hypernymy relation to "is a batsman", as batsman is a type of player.

⁵ Note that Frake uses the word object meaning anything regarded as a member of a category, whether perceptible or not.

⁶ We shall use that technical term below, even though it does not sound natural in ordinary English as a noun.

⁷ The example given in Frake (1969) concerns a conversation at a lunch counter, and has been abridged here.

⁸ It seems to us that, as the ethnographer is interested in testing terminological contrast, asking a question with the expectation of a negative reply has the following rationale. Forming a question with a wrong segregate, but one that is at the one particular level of inclusion (i.e., the vertical dimension of generalisation) where contrast is to be tested, will direct the answer from the informant--in its complementary part, that is, after "No"--to state the appropriate segregate at that particular level of inclusion, thus giving evidence of the contrasting relation between the inquired-about segregate and the one that occurs in the reply.

⁹ Note that Term (and Pred, mentioned next) are infinite domains; particular target societies will specify the subset of terms (and predicates) they use, as we shall see later.

¹⁰ Given the actual infrastructure of network services, this is not an unrealistic supposition.

¹¹ Note that in the present formalisation we do not constrain the ontological description of a term to have a minimal set of properties as suggested in Definition 4. See further discussion about this in Section 6.

¹² Note that a -expression is not allowed here because several predicates yielding the same segregate size may exist. We therefore state only that sp belongs to the set of predicates yielding the same largest segregate size (which is a somewhat ambiguous, but suitable for the purpose here).

¹³ The simplifications concern mainly some of the global definitions for the basic setting (e.g. access to TSs), which are not directly implementable in the Z tools used. All main algorithms are shown to work as intended in the animated version.

References

BAUMAN, R., and Sherzer, J., eds.    1989.   Explorations in the Ethnography of Speaking.    Cambridge: Cambridge University Press, second edition.

BAZZAN, A. L. C., Bordini, R. H., and Campbell, J. A.    1997.    Agents with moral sentiments in an iterated prisoner's dilemma exercise.    In Dautenhahn, K., Masthoff, J., and Numaoka, C., eds., Proceedings of the AAAI Fall Symposium on Socially Intelligent Agents, 8-10 November, Cambridge, MA, 4-6.    Menlo Park, CA: AAAI Press.    AAAI Press Technical Report FS-97-02. UCL-CS [RN/97/74]. http://www.cs.ucl.ac.uk/staff/R.Bordini.

BAZZAN, A. L. C., Bordini, R. H., and Campbell, J. A.    1999.    Moral sentiments in multi-agent systems.    In Müller, J. P., Singh, M. P., and Rao, A. S., eds., Intelligent Agents V--Proceedings of the Fifth International Workshop on Agent Theories, Architectures, and Languages (ATAL-98), held as part of the Agents' World, Paris, 4-7 July, 1998, in Lecture Notes in Artificial Intelligence,    Heidelberg: Springer-Verlag.    UCL-CS [RN/98/29]. http://www.cs.ucl.ac.uk/staff/R.Bordini.

BERNARD, H. R.    1994.   Research Methods in Anthropology: Qualitative and Quantitative Approaches.    Thousand Oaks, California: Sage Publications, second edition.

BORDINI, R. H., and Campbell, J. A.    1995.    Towards an anthropological approach to agent adaptation.    In Proceedings of the First International Workshop on Decentralized Intelligent and Multi-Agent Systems (DIMAS'95), II/74-II/83.    Krakow, Poland: Dom Wydawnictwa Naukowych, 22-24 November, 1995.    UCL-CS [RN/95/78]. http://www.cs.ucl.ac.uk/staff/R.Bordini.

BORDINI, R. H., da Rocha Costa, A. C., Hübner, J. F., and Viccari, R. M.    1995.    Linguistic support for agent migration.    In Lesser, V., and Gasser, L., eds., Proceedings of the First International Conference on Multi-Agent Systems (ICMAS'95), 12-14 June, San Francisco, CA, 441.    Menlo Park, CA: AAAI Press / MIT Press.    Extended Abstract. http://www.cs.ucl.ac.uk/staff/R.Bordini.

BORDINI, R. H., Campbell, J. A., and Vieira, R.    1996.    Ascribing intensional ontologies in anthropologically-based cultural descriptions of multi-agent systems.    In Durfee, E., ed., Proceedings of the Second International Conference on Multi-Agent Systems (ICMAS'96), 11-13 December, Kyoto, Japan, 427.    Menlo Park, CA: AAAI Press.    http://www.cs.ucl.ac.uk/staff/R.Bordini.

BORDINI, R. H., Campbell, J. A., and Vieira, R.    1997.    Ascription of intensional ontologies in anthropological descriptions of multi-agent systems.    In Kandzia, P., and Klusch, M., eds., Proceedings of the First International Workshop on Cooperative Information Agents (CIA'97), 26-28 February, Kiel, Germany, volume 1202 of Lecture Notes in Artificial Intelligence, 235-247.    Berlin: Springer-Verlag.    UCL-CS [RN/97/1]. http://www.cs.ucl.ac.uk/staff/R.Bordini.

BORDINI, R. H.    1994.    Suporte lingüístico para migração de agentes.    Master's thesis, Curso de Pós-Graduação em Ciência da Computação, Universidade Federal do Rio Grande do Sul, Porto Alegre, Brazil.

BORDINI, R. H.    1998.   Contributions to an Anthropological Approach to the Cultural Adaptation of Migrant Agents.    Ph.D. Dissertation, University of London.    To appear.

CASTELFRANCHI, C., Conte, R., and Paolucci, M.    1998.    Normative reputation and the costs of compliance.   Journal of Artificial Societies and Social Simulation 1(3).   <https://www.jasss.org/1/3/3.html>.

CONTE, R., and Castelfranchi, C.    1995.   Cognitive and Social Action.    London: UCL Press.

CONTE, R., Castelfranchi, C., and Dignum, F.    1999.    Autonomous norm acceptance.    In Müller, J. P., Singh, M. P., and Rao, A. S., eds., Intelligent Agents V--Proceedings of the Fifth International Workshop on Agent Theories, Architectures, and Languages (ATAL-98), held as part of the Agents' World, Paris, 4-7 July, 1998 in Lecture Notes in Artificial Intelligence    Heidelberg: Springer-Verlag.

DA ROCHA COSTA, A. C., Hübner, J. F., and Bordini, R. H.    1994.    On entering an open society.    In XI Brazilian Symposium on Artificial Intelligence, 535-546.    Fortaleza: Brazilian Computing Society, October, 1994.    http://www.cs.ucl.ac.uk/staff/R.Bordini.

d'INVERNO, M., and Luck, M.    1996a.    A formal view of social dependence networks.    In Zhang, C., and Lukose, D., eds., Distributed Artificial Intelligence: Architecture and Modelling--Proceedgins of the First Australian Workshop on DAI, in conjunction with the Eighth Australian Joint Conference on Artificial Intelligence (AI'95), November 1995, Canberra, Australia, number 1087 in Lecture Notes in Artificial Intelligence. Berlin: Springer-Verlag.    115-129.

d'INVERNO, M., and Luck, M.    1996b.    Understanding autonomous interaction.    In Wahlster, W., ed., Proceedings of the 12^th European Conference on Artificial Intelligence (ECAI'96).

d'INVERNO, M., and Luck, M.    1998.    Engineering AgentSpeak(L): A formal computational model.   Journal of Logic and Computation 8(3):1-27.

d'INVERNO, M.    1998.   Agents, Agency and Autonomy: A Formal Computational Model.    Ph.D. Dissertation, University of London.

DORAN, J., and Palmer, M.    1995.    The EOS project: Integrating two models of palaeolithic social change.    In Gilbert, N., and Conte, R., eds., Artificial Societies: The Computer Simulation of Social Life. London: UCL Press.    103-125.

DORAN, J., Palmer, M., Gilbert, N., and Mellars, P.    1994.    The EOS project: Modelling Upper Palaeolithic social change.    In Gilbert, N., and Doran, J., eds., Simulating Society: The Computer Simulation of Social Phenomena. London: UCL Press.    chapter 9, 195-221.

DORAN, J.    1997.    Artificial societies and emerging hierarchies.    Unpublished manuscript. http://cswww.essex.ac.uk/staff/doran.html.

DORAN, J.    1998a.    Simulating collective misbelief.   Journal of Artificial Societies and Social Simulation 1(1).   <https://www.jasss.org/1/1/3.html>.

DORAN, J.    1998b.    Social simulation, agents and artificial societies.    In Demazeau, Y., ed., Proceedings of the Third International Conference on Multi-Agent Systems (ICMAS'98), Agents' World, 4-7 July, Paris, 4-5.    Washington: IEEE Computer Society Press.    Extended Abstract for an Invited Talk.

FISHER, M.    1995.    Representing and executing agent-based systems.    In Wooldridge, M. J., and Jennings, N. R., eds., Intelligent Agents--Proceedings of the International Workshop on Agent Theories, Architectures, and Languages (ATAL-94), held as part of ECAI-94, Amsterdam, 8-12 August, 1994, number 890 in Lecture Notes in Computer Science, 307-323.    Berlin: Springer.

FRAKE, C. O.    1969.    The ethnographic study of cognitive systems.    In Tyler (1969).    pp.28-41.

GASSER, L., and Huhns, M. N.    1989.    Themes in distributed artificial intelligence research.    In Gasser, L., and Huhns, M. N., eds., Distributed Artificial Intelligence, volume II. London / San Mateo, CA: Pitman / Morgan Kaufmann.    vii-xv.

GASSER, L.    1991.    Social conceptions of knowledge and action: DAI foundations and open system semantics.   Artificial Intelligence 47(1-3):107-138.

GENESERETH, M. R., and Ketchpel, S. P.    1994.    Software agents.   Communications of the ACM 37(7):48-53.    http://logic.stanford.edu/sharing/papers/.

GRUBER, T. R.    1993.    Toward principles for the design of ontologies used for knowledge sharing.    In Guarino, N., and Poli, R., eds., Formal Ontology in Conceptual Analysis and Knowledge Representation. Kluwer Academic Publishers.    http://www-ksl.stanford.edu/knowledge-sharing/papers/

HEWITT, M. A.    1997.   PiZA: Prolog Z Animator, User Guide, version 1.0.9.    http://www.noodles.demon.co.uk/PiZA/PiZADocs.html.

HYMES, D.    1977.   Foundations in Sociolinguistics: An Ethnographic Approach.    London: Tavistock Publications.

JIA, X.    1995.   ZTC: A Z Type Checker, User's Guide, version 2.01.    Division of Software Engineering, School of Computer Science, Telecommunication, and Information Systems, DePaul University, Chicago, Illinois.    Available on anonymous ftp at ise.cs.depaul.edu.

LUCK, M., and d'Inverno, M.    1995.    A formal framework for agency and autonomy.    In Lesser, V., and Gasser, L., eds., Proceedings of the First International Conference on Multi-Agent Systems (ICMAS'95), 12-14 June, San Francisco, CA, 254-260.    Menlo Park, CA: AAAI Press / MIT Press.

LUCK, M., and d'Inverno, M.    1996.    Formalising the contract net as a goal-directed system.    In Van de Velde, W., and Perram, J., eds., Agents Breaking Away: Proceedings of the Seventh European Workshop on Modelling Autonomous Agents in a Multi-Agent World, number 1038 in Lecture Notes in Artificial Intelligence. Eindhoven: Springer-Verlag.    72-85.

MARTIN, R. M.    1959.   Toward a Systematic Pragmatics.    Amsterdam: North-Holland.

POTTER, B., Sinclair, J., and Till, D.    1996.   An Introduction to Formal Specification and Z.    Hemel Hempstead: Prentice Hall, second edition.

RIDLEY, M.    1996.   The Origins of Virtue.    London: Viking Press.

SICHMAN, J. S., Demazeau, Y., Conte, R., and Castelfranchi, C.    1994.    A social reasoning mechanism based on dependence networks.    In Cohn, A., ed., 11 ^th European Conference on Artificial Intelligence (ECAI'94), 188-192.    Amsterdam: ECCAI & John Wiley & Sons Ltd., August, 1994.

SPIVEY, J. M.    1992.   The Z Notation: A Reference Manual.    Hemel Hempstead: Prentice Hall, second edition.

TYLER, S. A., ed.    1969.   Cognitive Anthropology.    New York: Holt, Rinehart and Winston Inc.

VIEIRA, R., and da Rocha Costa, A. C.    1993.    The acceptance relation and the specification of communicating agents.    In Schlageter, G., Huhns, M., and Papazoglou, M., eds., Proceedings of the First International Conference on Intelligent and Cooperative Information Systems - Special Track in Issues on Cooperating Heterogeneous Intelligent Agents, 247-255.    Rotterdam, The Netherlands: IEEE Computer Society Press, May, 1993.

WIEDERHOLD, G.    1994.    Interoperation, mediation, and ontologies.    In Proceedings of the International Symposium on Fifth Generation Computer Systems (FGCSOB94), Workshop on Heterogeneous Cooperative Knowledge-Bases, volume W3, 33-48.    Tokyo, Japan: ICOT, December, 1994.    http://db.stanford.edu/pub/gio/gio-papers.html.

Appendix: Elements of the Z Notation

This appendix is intended to help the reader who is unfamiliar with the Z notation, although it is probably not helpful to the reader who is completely unfamiliar with formal specification. The Z notation is based on set theory and first order logic. Further, as Spivey (1992) puts it: "The other main ingredient in Z is a way of decomposing a specification into small pieces called schemas." He further remarks that: "A Z specification document consists of interleaved passages of formal, mathematical text and informal prose explanation. The formal text consists of a sequence of paragraphs which gradually introduce the schemas, global variables and basic types of the specification, each paragraph building on the ones which come before it." The notion of schema is very clearly explained by d'Inverno and Luck (1998): "Z schemas have two parts: the upper declarative part, which declares variables and their types, and the lower predicate part, which relates and constrains those variables. The type of any schema can be considered as the Cartesian product of the types of each of its variables, without any notion of order, but constrained by the schema's predicates. Modularity is facilitated in Z by allowing schemas to be included within other schemas." It also provides for the specification of systems at different levels of abstraction (i.e., details of the system can be added by means of a process of refinement). A last comment that is worth making here is again quoted from (Spivey 1992):

In Z, schemas are used to describe both static and dynamic aspects of a system. The static aspects include:

the states it can occupy;

the invariant relationships that are maintained as the systems moves from state to state.

The dynamic aspects include:

the operations that are possible;

the relationships between their inputs and outputs;

the changes of state that happen.

We next introduce in a concise way the subset of the Z notation that we have used in this paper. The Figure is borrowed, with their kind permission, from d'Inverno and Luck (1998), but adapted to the particular subset of the Z notation that has been used in this paper. Also, we have improved and restructured their figure, based partially on (Jia 1995) and (Spivey 1992).

  

Fig. 6 The Relevant Subset of the Z Notation (adapted from d'Inverno and Luck 1998)

Return to Contents of this issue

© Copyright Journal of Artificial Societies and Social Simulation, 1998