Alain Trognon

Christine Sorsana

Martine Batt

Dominique Longin

Peer interaction and problem solving: one example of a logical-discursive analysis of a process of joint decision making 1

Keywords: peer interaction, problem solving, conversation, Interlocutory Logic

This article proposes an analysis of a dialogue between two children solving the Tower of Hanoï problem. To carry out such an analysis, we use the Interlocutory Logic which is a formal system constructed to express the logical and phenomenological properties of natural conversation.

The studies of the interpersonal forms of learning, initiated by [START_REF] Doise | Social interaction and the development of cognitive operations[END_REF], led to propose a psychosocial model of cognition development (see also [START_REF] Doise | Le développement social de l'intelligence[END_REF][START_REF] Mugny | Psychologie sociale du développement cognitif[END_REF][START_REF] Perret-Clermont | La construction de l'intelligence dans l'interaction sociale[END_REF]. This is the structuralist model of socio-cognitive conflict. It accounts for the fact that, under certain conditions, working in pairs produces individual cognitive progress greater than that of an individual working alone. "Something" happens therefore in the interpersonal interaction which could provide the beginning of an empirical model of Vygotsky's (1962) idea. According to whom the construction of new interpersonal coordination is accomplished thanks to the internalization of interpersonal coordination. The analysis of researchers of the procedural approach enabled the characterisation of this "interpersonal coordination" hypothesis in describing the actions that are effectively carried out by the partners working together [START_REF] Gilly | Mécanismes psychosociaux des constructions cognitives: perspectives de recherche à l'âge scolaire[END_REF][START_REF] Gilly | Social psychology of cognitive constructions: european perspectives[END_REF][START_REF] Gilly | Approches socioconstructives du développement cognitif[END_REF][START_REF] Blaye | Interactions sociales et constructions cognitives: présentation critique de la thèse du conflit sociocognitif[END_REF][START_REF] Blaye | Mécanismes générateurs de progrès lors de la résolution à deux d'un produit de deux ensembles par des enfants de 5-6 ans[END_REF][START_REF] Dalzon | Conflit cognitif et construction de la notion Droite/Gauche[END_REF][START_REF] Zhou | Norme égalitaire, conduites sociales de partage et acquisition de la conservation des quantités[END_REF][START_REF] Gilly | Social marking in ordering tasks: effects and action mechanisms[END_REF][START_REF] Roux | Contribution à l'étude des mécanismes d'action du marquage social dans une tâche d'ordination à 12-13 ans[END_REF]. They have shown that the separate actions of the protagonists organize themselves into procedural sequences of resolution. In other words, "they coordinate themselves to become a sequential cognitive procedure," (Gilly, 1989, p. 497). Thus, in certain conditions, children can go beyond interdependence (Deutch, 1949(Deutch, , 1962) ) arising from reciprocal control of actions whilst developing a collective intentionality [START_REF] Dascal | On the pragmatic structure of conversation[END_REF][START_REF] Searle | On Searle on Conversation[END_REF].

A new step in the knowledge of the role of interactions in acquisition was made when researchers became attentive to utterances considered also as actions besides the resolution processes of those interacting [START_REF] Perret-Clermont | L'extorsion des réponses en situation asymétrique[END_REF][START_REF] Trognon | Psychologia cognitiva e analisi delle conversazioni[END_REF]. The objective of contemporary analysis is to identify the conversational "materials" that denote (even constitute) knowledge building operations [START_REF] Gilly | Apprendre dans l'interaction. Analyse des médiations sémiotiques[END_REF]Trognon & Batt, 2003;[START_REF] Trognon | L'apprentissage dans l'interaction: Essai d'analyse interlocutoire[END_REF]. This identification is made on the basis of a formal system -the interlocutory logic -conceived to express the logical properties of natural conversation, whilst respecting its phenomenological properties [START_REF] Trognon | Eléments d'analyse interlocutoire[END_REF][START_REF] Trognon | Speech acts and the logic of mutual understanding[END_REF][START_REF] Trognon | La Logique Interlocutoire: Un programme pour l'étude empirique des jeux de dialogue[END_REF]Trognon & Batt, 2003, 2004, 2007a, 2007b;[START_REF] Trognon | Logique interlocutoire de la résolution en dyade d'un problème d'arithmétique[END_REF]; [START_REF] Trognon | La modélisation des raisonnements générés dans les interlocutions[END_REF][START_REF] Trognon | Eléments d'une théorie sociocognitive de l'interaction conversationnelle[END_REF]. The interlocutory logic theory thus proposes an analysis of the socio-cognitive production of a conversation. Analyses that made explicit the emergence of diverse knowledge in interactions, taking place within the framework of interlocutory logic, were published in the last few years. These include the following: (1) knowledge pertaining to the correct placement of a cursor during a word processing tutorial (Trognon & Saint-Dizier, 1999); (2) knowledge pertaining to the handling of a pneumatic drill during learning in the context of an alternance vocational training system [START_REF] Sannino | Les connaissances émergeant d'une relation tuteur-apprenti sur le lieu de travail[END_REF][START_REF] Sannino | A model for analyzing knowledge content and processes of learning a trade within alternance vocational training[END_REF]; (3) during liquid conservation tasks [START_REF] Marro | Processus interlocutoires dans une tâche de conservation des liquides[END_REF]; (4) during educational learning: number division [START_REF] Trognon | Résolution conjointe d'un problème arithmétique[END_REF] and proportionality [START_REF] Trognon | L'apprentissage dans l'interaction: Essai d'analyse interlocutoire[END_REF], 2006); (5) during hypothetical deductive reasoning applied to an empirical problem (Trognon & Batt, 2003), to a logic problem [START_REF] Trognon | Logique Interlocutoire des jeux de dialogue: Un programme en Psychologie Sociale de l'usage du langage[END_REF] or to a diagnostic procedure [START_REF] Brixhe | Résolution interlocutoire d'un diagnostic[END_REF]. After presenting interlocutory logic, the present study examines the co-resolution of the Hanoï Tower problem by two children.

INTERLOCUTORY LOGIC

Interlocutory logic is a theory of the logical form of interlocutory events as they occur phenomenologically. That is to say, as they occur with natural language whose sequential production is distributed between several interlocutors (Trognon & Batt, 2007c;[START_REF] Trognon | Logique interlocutoire du problème des quatre cartes posé à une dyade[END_REF]. As a formal theory, it constitutes a system of logical methods selected for their capacity to reflect the phenomenological property of the interlocution. Thus, for example, interlocutory logic will resort preferentially to dialogical methods and to natural deduction methods or those derived from them, like the sequent method 2 . The ambition of interlocutory logic is to provide a natural logic of the usage of speech in interaction.

Interlocutory logic is a theory of dialogue movement in its context

More technically, to analyze an interlocution fragment in interlocutory logic amounts to decomposing this fragment into a series of utterances. Each utterance is represented by an expression ф of the system: <M i , {M i-k },{M i-k }├ M i , RD, DG>.

M i is the conversational move accomplished by the utterance under examination. {M i-k } is the set of all the conversational moves that precede the move M i and from which M i follows. M i can then be conceived as a conclusion that results from premises {M i-k }. The reasoning that leads from {M i-k } to M i , and that is represented by the schema {M i-k } ├ M i , is called, in logic, a sequent 3 .

Let's specify this notion more precisely by adapting an analysis proposed by [START_REF] Carlson | Dialogue games. An approach to discourse Analysis[END_REF] 4 .

Suppose that A goes to the stadium to attend a pole-vaulting final between Jack and Bob. Delayed, he only arrives at the stadium once the competition has finished. When arriving A entertains the following "ideas": If someone won it is Jack or Bob and someone has won. Moreover, he asks himself "Who has won?" Catching the sight of his friend B, he engages in the following dialogue: 2 A very accessible presentation of these methods can be found in [START_REF] Vernant | Introduction à la logique standard[END_REF].

3 "a sequent" is a pair (note Γ ├ F) where: -Γ is a finite set of formulas. Γ represents the hypotheses that one can use. This set is also called the sequent context -F is a formula. It is the formula that one wants to demonstrate. This formula is said to be the conclusion of the "sequent" (David, Nour, & Raffali, 2003, p. 24). 4 Even in his recent publications (1996, for example) Carlson does not refer to the logic theory of sequents. We think nevertheless that his theory calls for this extension. (2) is a response to (1). The rule (or rules) (RD) of dialogue (DG) allowing to derive (2) from ( 1) is represented by the sequent {1A} ├ 2B. The rules that lead from the premise to the conclusion are the questioned rules of semantics exposed in the research of [START_REF] Hintikka | Languages-Games[END_REF][START_REF] Hintikka | Rules, utilities, and strategies in dialogical games[END_REF][START_REF] Hintikka | Fondements d'une théorie du langage[END_REF] of whom

Carlson is a student. (3) comes from the "thoughts" entertained by A5 and from the information 2B

worked out together by the logic rule of the disjunctive dilemma6. ( 5) is again deduced from the thoughts entertained by A and from 4B in using reductio ad absurdum.

In a relatively informal yet sufficient manner for understanding the meaning of our approach, the previous short dialogue has just been reproduced as the product of a set of dialogue rules formulated as sequents. Some of these rules belong to (dialogical forms of) standard logic. This is the case with the disjunctive dilemma or the classic reductio ad absurdum rule which would be used to demonstrate 5A. Other rules concern, instead, the semantics and pragmatics of natural language.

We call sequents of dialogue the setting of the relationship in a set of dialogical events (Trognon & Batt, 2007c;[START_REF] Trognon | Logique interlocutoire de la résolution en dyade d'un problème d'arithmétique[END_REF]. This relationship is an inference composed on the one hand from a set of premises given in the dialogue and, on the other hand, of events which are deduced from these premises. The rules intervening in this inference are rules of a dialogue game. For example, the dialogue sequent {1A}├ 2B rests on a rule belonging to the game theory of the question-response dialogue. This example shows that interlocutory logic seems to generalize the sequent notion to all the illocutory acts used in an interlocution.

The internal composition of the movement of a dialogue

From the viewpoint of its internal composition, a move M i is an expression of the system 7 : < F(P) >. F is the force of the speech act accomplished by the uttering the utterance. F = <f 1 , f 2 , f 3 , f 4 >. f 1 is the force literally expressed, f 2 the indirect force of the act (if it occurs), f 3 the implicatures of the act, and f 4 the conversational function of the act 8. We anticipate a little bit the interlocutory analysis which will follow, but let us consider, for example, the utterance 12Au that has been emitted by Audrey while she is interacting with Vanessa:

12Au: on the brown (disc b)

This elliptic utterance (in fact, it is only a Prepositional Group) is literally an assertive and, non literally, a directive as well as a commissive speech act (because a commissive act is a directive act that the speaker aims at himself). Its conversational function in the interlocution within a framework of problem resolution is 1) to make a proposal for a joint action and 2) in consequence, to refuse the joint action suggested by Vanessa in the preceding speech turn.

P is the propositional content of the speech act that realises the move Mi. This propositional content is described by expressions of the quantified modal first-order predicate logic 9 . For example, the propositional content of 12Au is the modal expression presented below which describes a future action of the children.

12Au: A simplified way to write the propositional content of this action is (Awb) if we identify Audrey's proposal with the goal that she aims at when she is uttering «on the peg A white on brown».

E a {[shall E v+a (Awb)]}
Moreover, because (Awb) ⊃ ¬(Bwp) is likely to be a mutual knowledge between the two girls, with the Bwp formula which means white disc on pink disc on peg B, consequently the (Awb) proposal amounts to declining (Bwp) which is Vanessa's proposal.

In the calculations of interlocutory logic, the forces of speech acts are processed as modalities. An utterance like 12Au will therefore be written: Directive (Awb). If we assume that the laws of General Semantics [START_REF] Vanderveken | Meaning and Speech Acts[END_REF] belong to the speakers'mutual knowledge while they talk process described in [START_REF] Trognon | La Logique Interlocutoire: Un programme pour l'étude empirique des jeux de dialogue[END_REF], [START_REF] Trognon | L'enchaînement conversationnel[END_REF], Trognon & Saint Dizier (1999). The formula that describes, in interlocutory logic, the different levels (from the utterance to the direct act, from the direct act to the indirect act, from the indirect act to the conversational move) of the interpretative genesis of the sign-for-interlocutors is borrowed from [START_REF] Jones | Communication and Meaning. An Essay in Applied Modal Logic[END_REF]. For more detail see Trognon & Batt (2007b[START_REF] Trognon | Logique interlocutoire du problème des quatre cartes posé à une dyade[END_REF]. 9 "Quantified modal first-order predicate logic" was amended, as suggested by Hintikka, in order to adapt it to the « natural logic of the discourse ». The connectors of interlocutory logic are the connectors of Hintikka's semantic games [START_REF] Hintikka | The game of language[END_REF]. But presentation of this complication is unnecessary in the present study.

together, then the logical expression Directive (Awb) ⊃ To Desire (Awb) belongs to the speakers'mutual knowledge too, as well as the To Desire (Awb) propositional attitude, thanks to Modus Ponens. As a result, the partners both gain access to (at least) one world w av in which Vanessa's desire is satisfied, that is to say a world in which (Awb) is true. In this case, w av is just the content of Audrey and Vanessa's mutual desire. It's an alternative of the real world w 0 , which is the world in which Audrey and Vanessa desire (Awb). The expressions of w av are therefore the expressions of w 0 relieved of their modalities. In interlocutory logic, an expression of this kind is called a formula reduced to the propositional content of the speech act. This reduction, legitimate when the dialogue is entirely cooperative, allows the analysis to focus on the dialogue's conceptual content.

THE SOLVING OF THE TOWER OF HANOÏ PROBLEM BY CHILDREN Anticipation and planning abilities in children

Research on children solving the Hanoï Tower problem does not provide consistent results.

According to [START_REF] Byrnes | Developmental progression of performance on the Tower of Hanoï problem[END_REF], planning appears to be very rare before 7-8 years old and only becomes widespread from 14 years old upwards. The problem with two discs is achieved by almost all the subjects as early as 8 years old. The problem with three discs is only successfully solved with the minimum number of moves by 70% of adolescents aged 14 and over. There is rapid progress between 7 and 9 years old, a plateau between 9 and 12, again important progress between 12 and 14 and, once again, a plateau. These results are in accordance with the different resolution stages reported by [START_REF] Piaget | La prise de conscience[END_REF] who placed children in front of an increasing number of discs to move.

This line of research was resumed and disputed by [START_REF] Klahr | Goal formation, planning and learning by pre-school problem solvers or "my socks are in the dryer[END_REF] and [START_REF] Klahr | Formal assessment of problem solving and planning processes in preschool children[END_REF].

Using problems with gradual increases in difficulty, the authors showed that children of 5-6 years old presented rudimentary forms of recursive type planning. This planning involved the working out of goals, the detection of obstacles that would prevent the realization of these goals and the detection of rules indicating the conduct to adopt in this case. These subjects would not develop only trial and error behaviour but a more sophisticated attitude with non-random choices. [START_REF] Richard | Planification et organisation des actions dans la résolution du problème de la Tour de Hanoï par des enfants de 7 ans[END_REF] -There is a series of positions, of which the preceding ones are a subset where subjects systematically avoid making correct choices. It all happens as if, for them, it was about overcoming a series of obstacles.

Consequently, for [START_REF] Richard | Planification et organisation des actions dans la résolution du problème de la Tour de Hanoï par des enfants de 7 ans[END_REF], planning 10 intercedes only in a rather late stage of the resolution and corresponds to a transformation of the problem representation. This transformation is motivated by the failure of rules elicited by early problem representations and results in taking into account crucial aspects of the situation that were neglected up till then. [START_REF] Richard | Problématique de l'analyse des protocoles individuels d'observations comportementales[END_REF] see also [START_REF] Richard | Les activités mentales: comprendre, raisonner, trouver des solutions[END_REF]1991) subsequently proposed a modelling of this problem solving. It represents research processes that are missing planning, in the strictest sense of the word. These research processes appear to be, according to the authors, characteristic of new situations where it is not possible to find an analogical situation in memory that could serve as a reference point. The authors define three processes:

1)

The representation state, expressed in the form of hierarchical constraints that are, either real constraints of the situation or are imagined by the subject (inappropriate interpretation of the instructions and procedures, goals, rules of action that result).

2)

The construction processes of the state of representation corresponding: a. To the memorisation rules b. To the production rules of the goals

3)

The third process corresponds to the action and control rules.

The solving of the Hanoï Tower problem in dyadic situations

10 For [START_REF] Richard | Les activités de planification chez l'enfant[END_REF], planning, in the strictest sense of the word, occurs: either "when the actions necessary to satisfy the instructions can be calculated by action calculation rules but when their execution must be delayed because other constraints must be taken into account to determine the actions' sequential layout"; or "when the situation and the knowledge about the actions is such that other action calculation rules are required to satisfy the task demands" (p. 35).

He describes different forms of planning. Glachan and[START_REF] Glachan | Peer interaction and learning: can two wrongs make a right?[END_REF]Light &[START_REF] Light | Facilitation of individual problem solving through peer interaction[END_REF] used wooden material, including discs with handles, while [START_REF] Light | Collaborative interactions at the microcomputer keyboard[END_REF]McClelland (1987) (andLight &Foot, 1987) programmed this task on a computer. These studies were aimed at children aged 7 to 9 years old and included the same experimental paradigm (pre-test /training /post-test).

The results, with the wooden material, showed that the "dyadic" condition, with participants of similar initial skills, produces significantly better results than the "individual" condition.

Nevertheless, the high-performing dyads are the ones that have children who had shown a strategic approach during the pre-test. A closer examination of the possible causes of observed dyadic results

showed that regardless of the type of material, only the interactional modality that forced the children to move the discs together produced significant improvements in the post-test.

Performance in two other modalities, one where children are not told to move the discs together and another where the experimenter guides each dyad about the optimal sequence for placement without explanation or justification, was significantly lower. In any case, when children used the "computer" version in the same manner as the wooden one, the peer facilitator effect was less prominent than with the wooden material.

INTERLOCUTORY LOGIC OF A SEQUENCE OF CO-RESOLUTION

The conversational sequence from which the logic form will be constructed is taken from a recording of a dyad of children who are in the process of solving the Hanoï Tower problem with four discs (cf. figure 1).

[ INSERT FIGURE 1 HERE] This dyad, of Vanessa and Audrey, comes from a sample of 44 dyads of children aged 6 to 8 participating in research whose objective was to study the effect of the quality of children's relationship on their cognitive performance. More precisely, it was to study how some noncognitive determinants, here the affinity11 , shape particular behaviours that could result in a specific form of cognitive management at the point at which the Hanoï Tower problem, with four discs, is solved [START_REF] Sorsana | Relations affinitaires et co-résolution de problème: analyse des interactions entre enfants de six-huit ans[END_REF][START_REF] Sorsana | Affinités enfantines et co-résolution de la Tour de Hanoï[END_REF][START_REF] Sorsana | Stratégies sociocognitives dans la résolution de la Tour de Hanoï[END_REF][START_REF] Sorsana | Power and knowledge: how can rationality emerge from children's interactions in a problem-solving situation[END_REF]. The experimental apparatus is standard: pre-test (towers with three discs)/ social interaction (with two attempts of co-resolution with four discs) /post-tests (towers with three and four discs). To coerce the children into interacting, the discs were made heavier and they were equipped with handles. Furthermore, the instructions given demand that every disc is moved together and stipulates "Be careful: to move the discs well it is necessary that you look for the solution together, talk it over together and reach an agreement."

The comparison of the "affinity" and "no affinity" dyads, for the second attempt only, showed a difference in performance and duration of the task depending on the type of dyad: the "affinity" dyads performed better than the "no affinity" dyads (z = -2,424, p =. 007) and are quicker (z = -1,908, p =. 02). In the post-test with four discs, there is a significant difference between the subjects performances, in favour of the "affinity" subjects (z = -1,652, p =. 04) with similar task durations (z = -1,393, p =. 08). In the post-test with three discs, the differences are not significant.

Only three dyads succeeded in one of the two attempts to rebuild the tower with four discs using the minimum number of moves (i.e. 15). The Vanessa/Audrey dyad was one of them. In addition, the children that were part of this dyad appreciated each other (i.e. it was an "affinity" dyad). The first attempt was accomplished in 35 moves and in 661 seconds. The second attempt was accomplished with an optimum score (15 moves) in 122 seconds. Initially, these two subjects had failed the pretest (i.e. the reconstruction of the tower with three discs). In the post-test with 4 discs, Vanessa rebuilt the tower in 16 moves and 60 seconds; Audrey in 24 moves and 120 seconds. In the post-test with 3 discs, Vanessa accomplished an optimum score (7 moves) in 60 seconds and Audrey, 9 moves in 60 seconds also. For the children in this dyad, interaction will obviously have been beneficial on the cognitive level.

The choice of this sequence is motivated by the examination of the interlocutory processes employed in order to resolve contradictions that are unavoidably generated by the achievement of a collective intentionality. These contradictions present themselves as socio-cognitive conflicts (cf. [START_REF] Doise | Le développement social de l'intelligence[END_REF][START_REF] Doise | Social interaction and the development of cognitive operations[END_REF][START_REF] Gilly | Mécanismes psychosociaux des constructions cognitives: perspectives de recherche à l'âge scolaire[END_REF][START_REF] Gilly | Social psychology of cognitive constructions: european perspectives[END_REF][START_REF] Gilly | Approches socioconstructives du développement cognitif[END_REF][START_REF] Mugny | Psychologie sociale du développement cognitif[END_REF][START_REF] Perret-Clermont | La construction de l'intelligence dans l'interaction sociale[END_REF]. These conflicts are, one the one hand, cognitive conflicts: the children's strategies are contradictory; they share the same goal, but can disagree on how to attain it (i.e. on the sequencing of the sub-goals that the task seems to impose on them). These conflicts are also, on the other hand, social, perhaps even emotional, conflicts. The one who wins over the argument in a conflict of responses occurring within a close relationship undermines their partner's face. Consequently they endure the dissonance of infringing upon friendship obligations in wanting the dyad to succeed. The interactional "cost" of a socio-cognitive conflict seems then higher within an affinity dyad than within a dyad with no affinity12.

To study this conflict of responses within the Vanessa/Audrey dyad, we start by reproducing the sequence within which it appears. We then analyze the internal composition of each utterance.

Then, we reveal the (dia)logical structure of the utterances that form the socio-cognitive conflict, from its inauguration in the dialogue until its resolution.

A(-, -, w, b) & B(-, -, p, g) & C(-, -, -, -) A(-, -, -, b) & B(-, w, p, g) & C(-, -, -, -) A(-, -, -, -) & B (-, w, p, g) & C(-, -, -, b)
The choice is crucial from two points of view. From a logical standpoint, it is clear that to move the white disc on the green disc (Vanessa's proposal) is less interesting than to move the white disc on the brown disc (Audrey's proposal) because, in the latter proposal, then the pink disc may be moved on the green one, then the white disc on the pink one, and finally the brown disc on peg C. From a psychological standpoint now, in their modelling of the solution of the problem, [START_REF] Richard | Problématique de l'analyse des protocoles individuels d'observations comportementales[END_REF] and [START_REF] Richard | Les activités mentales: comprendre, raisonner, trouver des solutions[END_REF][START_REF] Richard | Analyse de procédures et modélisation de la résolution de problème[END_REF] demonstrate that in this solving stage the participants (including adults) avoid placing another disc on the larger disc -finally released -and favour the movement of disc w onto the peg B.

From 11Va to 21Au, the children will find the best solution. But they will have to exceed a sociocognitive conflict before. This conflict develops as follows. From 10 to13Va 2 , we attend the installation of the conflict. Each girl states the goal she wants to carry out (11Va versus 12Au), then the incompatibility with the partner's goal (13Va 1 versus 14Au 1 ): the contradiction of the propositional contents involves an incompatibility of the acts [START_REF] Searle | Foundations of illocutionary logic[END_REF]. An argumentative phase follows, more or less superimposed on the preceding phase. During this phase, each player argues her thesis (14Au 2 -16Au 2 versus 17Va 2 ). Then, a phase of resolution may close the conflict, like in the interaction that we are examining (cf. table 1), where one of the girls will adopt the option initially suggested by her partner.

[INSERT TABLE 1 HERE]

By calculating her proposal with her partner's proposal taken as an assumption, each girl deduces a contradiction, by a simple reasoning ad absurdum. Because the interaction cannot continue on the mode of opposition, except by entering a "dialogue of the deaf" where each interlocutor indefinitely repeats his point of view, alternatively at each turn of speech, the girls must adopt another dialogue game if they wish to prolong their cooperation. Then they engage in a mixed dialogue of argumentation [START_REF] Rips | Reasoning and Conversation[END_REF][START_REF] Walton | Commitment in Dialogue: Basic Concepts of Interpersonal Reasoning[END_REF], in which each player is supposed to persuade her partner by using a battery of strategies. To challenge her partner to argue in favour of her own thesis is one of these strategies. A player receiving a challenge must put forward an argument, otherwise he loses the game. In this interaction, no challenge is uttered, but the children put forward their arguments respectively. Examining both the justification put forward by Vanessa (17Va 2 ) and the arguments uttered by Audrey in order to reject Vanessa's proposal (16Au 1 + 16Au 2 ), we notice that the former follows from the latter:

(16Au 1 & 16Au 2 ) → 17Va 2
The dialogue game theory of persuasion [START_REF] Walton | Commitment in Dialogue: Basic Concepts of Interpersonal Reasoning[END_REF] Vanessa's proposal will be followed by a move of the pink disc on the brown one, proposal which is not uttered by Vanessa (yet?). In any case, the positive relationships between the two girls are likely to support the resolution of the disagreement (17Va 3-4 ). Therefore they accomplish Audrey's solution (18-19), and Vanessa approves its accuracy (20Va) to Audrey's satisfaction which she expresses with her smiles (21Au).

In the analysis that we propose here, on the one hand, Vanessa will not have needed to devote herself to a comparative study of the consequences of both her proposal and Audrey's on the rest of the play to adopt her partner's standpoint: the interest of Audrey's proposal is "staring her in the face". On the other hand, the success of Audrey's strategy, that the children will then test, will reinforce their decision positively. It may be thanks to a contingent interaction like the one that we have just examined that Audrey and Vanessa acquired the solution of the Tower of Hanoï problem.

CONCLUSION

In this article, we showed how interlocutory logic can formalize the socio-cognitive conflict, which is an essential ingredient of development for the psychology of social genetics "school" [START_REF] Doise | Le développement social de l'intelligence[END_REF][START_REF] Doise | Social interaction and the development of cognitive operations[END_REF][START_REF] Mugny | Psychologie sociale du développement cognitif[END_REF][START_REF] Perret-Clermont | La construction de l'intelligence dans l'interaction sociale[END_REF].

Until now, interlocutory logic, which is generally meant as a theory on the "logic form" of interlocutions or as a theory of the "natural logic" contained in discourse usage in interaction, has mainly been used to formally demonstrate socio-cognitive events. The interlocutory events in these analyses are taken as conclusions to be inferred in a dialogue system. For example, in the present article, interlocutory logic explains why Vanessa grants Audrey's suggestion whilst abandoning hers. This amounts to solving the socio-cognitive conflict in which the children were involved. This resolution mode differs from the one considered most effective from the standpoint of cognitive development by the social genetic psychology school. Vanessa's agreement is situated, in effect, between the obliging agreement (compliance) and the integration of two viewpoints in a synthesis that preserves them and exceeds them. What remains is that, even though demonstrative, our (dia-)logical explanation constitutes speculation among others. It will only be possible to ascertain it by appealing to the "cutting edge" of experimentation.

Compared to the psychosocial theory of the cognitive development, interlocutory logic constitutes a formal improvement because it clarifies the semiotic mediations in which the sequential cognitive procedures are expressed. Interlocutory logic also constitutes a theoretical improvement insofar as the sequential cognitive procedures are rarely given directly in the interaction, that is to say in the "ordinary life" [START_REF] Trognon | Psychologie sociale et raisonnement[END_REF][START_REF] Trognon | L'interaction sociale[END_REF].

Other uses of interlocutory logic are conceivable in developmental psychology. For example: to design a developmental model of interactional competences and their cognitive effects, following up on the works of [START_REF] Bruner | Child's Talk: Learning to Use Language[END_REF][START_REF] Bruner | Actual Minds, Possible Worlds[END_REF][START_REF] Bruner | Acts of Meaning[END_REF], [START_REF] Harris | The work of the imagination[END_REF] and [START_REF] Tomasello | The cultural origins of human cognition[END_REF]; to better control the situation that constitutes "the uphill struggle" of developmental psychology and all the others; that is, "the indeterminacy of radical translation" [START_REF] Quine | Word and Object[END_REF], of which Piaget was, in his own way, surely acutely aware when he devised the clinical interview [START_REF] Piaget | La représentation du monde chez l'enfant[END_REF]. Table 1.

Interlocutory analysis of a disagreement between two children

Sequential verbal exchanges

  E a : means the (E) action achieved by Audrey (a). The propositional content of this action: [shall E v+a (Awb)], with the Awb formula which means white disc on brown disc on peg A, is describing a state of the world (Awb) which would be realized in the future ('shall' is the modal marker of the future) by the joint action of the two girls, Vanessa and Audrey (E v+a ).

  studied the forms of action organisation present in the solving of the three discs problem with 495 children aged 7 (tested individually). The following are the principal results:-The frequency of the correct choices increases when children approach the goal, but there is a lack of continuity. A significant proportion of children (.42 in the first attempt; .31 in the second) do not reach the goal and a minimal proportion of children attain it with the minimum number of moves (.06 in the first attempt; .16 in the second). Even in subjects who do not reach the goal in seven moves, the first move (a deciding factor for the remainder of the problem) does not seem to be the object of any planning that would aim to liberate the larger disc as well as position C in order to be able to move disc 1 onto it.-Interruptions are observed in the research behaviour (stopping, attempted illegal moves, steps backwards) and these typically happen at certain positions: 55% of the subjects have at least two experimenter interventions in the first attempt for violation of the instructions or stopping completely, and 26% in the second attempt.

Figure 1 .

 1 Figure 1. The Tower of Hanoï problem with four discs

  afterwards, let's put that one there (p on g using her hand gesture

  demonstrates that a player wins the game when he manages to demonstrate his thesis starting from the opponent's concessions. If we supposed that Vanessa took Audrey's assertions for assumptions in her own reasoning, then she should deduce 17Va 2. Consequently, Vanessa hasn't got any more reason to reject Audrey's proposal. Moreover, if Audrey's proposal and Vanessa's both lead to the same situation -the release of the peg C -Audrey's proposal remains strategically higher, because it makes it possible to reach a key sub goal of the problem more quickly. And it's subjected to the condition that

This is the cognitive environment of A defined by[START_REF] Sperber | Relevance. Communication and cognition[END_REF].

p v q, or ∼p, so q.

Interlocutory logic integrates general semantics[START_REF] Searle | Foundations of illocutionary logic[END_REF][START_REF] Vanderveken | Meaning and Speech Acts[END_REF] as one of its most fundamental components.

f 2 , f 3 , f 4 are not given simultaneously in the discourse. They result from a process of sharing the inter-comprehension which transforms the "meaning of the locutor" into the "interlocutors' meaning"[START_REF] Clark | Using language[END_REF][START_REF] Clark | On the origins of conversation[END_REF], according to a

Through the use of a sociometric questionnaire, aimed at children, and a standardized interview with the teachers, we selected pairs of children that appreciated each other (that we called "affinity" pairs in reference to the work of[START_REF] Maisonneuve | Psycho-sociologie des affinités[END_REF] and pairs of children that did not appreciate each other (called "no affinity" pairs).

In game theories (and in particular dialogue game theory), this factor would play a important role (cf.[START_REF] Bromberg | La psychologie sociale de l'usage du langage[END_REF], 2004;[START_REF] Hintikka | Knowledge and Belief. An Introduction to the Logic of the Two Notions[END_REF][START_REF] Hintikka | Languages-Games[END_REF][START_REF] Hintikka | Rules, utilities, and strategies in dialogical games[END_REF].

1 This article comes from work carried out within a workshop coordinated by Sorsana and Trognon at the University of Nancy 2 (during 2002, 2003 & 2004) and entitled This workshop was subsidized by the Scientific Counsel of the University

Dialogue extract containing the socio-cognitive conflict

Note: from the smallest one to the biggest one, the colours of the discs of the Tower of Hanoï are: white (w), pink (p), green (g) and brown (b).

1Va: Let's put it (disc w) there (peg B) 2: co-action 3Va: let's put it (disc p) there (peg C) 4: co-action 5Va: after we take the other disc… 6Va: let's put it (disc w) there (peg C) 7: co-action 8Va: let's put it (disc g) there (peg B) 9: co-action 10: (lift up disc w) 11Va: on the green (disc g) 12Au: on the brown (disc b) 13Va1: no 13Va2: on the green 14Au1: no 14Au2: let's put the pink one there (disc p) 15Va1: wait, wait 15Va2: (looks at the experimenter) 15Va3: let's put it on the green 16Au1: no 16Au2: afterwards let's put that one there (disc p on disc g using her hand gesture) 17Va1: yes 17Va2: but we must build the tower there (peg C) 17Va3: ah yes 17Va4: that's it 18: co-action (disc w) on disc b on peg A) 19: co-action (disc p on disc g on peg B) 20Va: OK! 21Au: (smiles) Internal decomposition of the series of dialogue moves contributing to the socio-cognitive

conflict

Our analysis concerns the extract (11Va…21Au) that is produced immediately following the lifting up of disc 1 (w) by the two children. This sequence sets the stage for a disagreement between the two children. From this disagreement an inter-comprehension process emerged that then leads to an agreement. Even though, from 11Va to 15Va, the disagreement is concerned with the place where to put (w), it is Audrey's reasoning, in 14Au and 16Au, that ends up imposing itself as illustrated by what Vanessa expresses in 17Va.

Once the 9 co-action is carried out, the four discs arise on the pegs as follows: the brown disc is on peg A, so we write [A(-, -, -, b)], the green disc is on peg B, so we write [B(-, -, -, g)] and the white and pink discs are on peg C, so we write [C(-, -, w, p)]. When several discs are on the same peg, they are written from the smallest one to the biggest one. Thus, the overall configuration of pegs and discs is:

The different stages followed by the children until the preceding configuration are as follows: The girls progressed as if they were following the exact pattern of the recursive model 13 of the resolution of the Tower of Hanoï problem. According to this model, "in order to move n discs from peg A to peg C, one must necessary proceed in three stages. The first stage consists in transferring n-1 discs from peg A to peg B, the second stage in transferring one disc (the biggest one) from peg A to peg C and the last stage in transferring n-1 discs from peg B to peg C" (Gochet, Gribomont & Thayse, 2000, pp. 262-264). By applying this method n-1 times, "one gets the optimal list of the elementary moves" (p. 264); and it's exactly the way that will be followed by Audrey and Vanessa. The authors hold at the disposal of readers a recursive data-processing model of the children's enacted reasoning.


Andreas Herzig

Dominique Longin

Belief Dynamics in Cooperative Dialogues

We investigate how belief change in cooperative dialogues can be handled within a modal logic of action, belief, and intention. We first review the main approaches of the literature, and point out some of their shortcomings. We then propose a new framework for belief change. Our basic notion is that of a contextual topic: we suppose that we can associate a set of topics with every agent, speech act and formula. This allows us to talk about an agent's competence, belief adoption, and belief preservation. Based on these principles we analyse the agents' belief states after a speech act. We illustrate our theory by a running example.

Introduction

Participants in task-oriented dialogues have a common goal, viz. to achieve the task under consideration. Each of the participants has some information necessary to achieve the goal, but none of them can achieve it alone. Consider e.g. a system delivering train tickets to users. The system cannot do that without user input about destination and transport class. The other way round, the user needs the system to get his ticket.

Each of the participants is supposed to be cooperative. This is a fundamental and useful hypothesis. Informally, a person is cooperative w.r.t. another one if the former helps the latter to achieve his goals (cf. Grice's cooperation principles, as well as his conversation maxims [START_REF] Grice | Logic and conversation[END_REF]). For example, if the system learns that user wants a train ticket, then the system will intend to give it to him. The other way round, if the system asks for some piece of information it needs to print the ticket, then the user answers the questions asked by the system.

Each participant is supposed to be sincere: his utterances faithfully mirror his mental state. If a participant says "the sky is blue" then he indeed believes that the sky is blue. Such a hypothesis means that contradictions between the presuppositions of a speech act and the hearer's beliefs about the speaker cannot be explained in terms of lies. Note that our sincerity assumption is much weaker than in other approaches, where sincerity is sometimes viewed as the criterion of input adoption (Cohen and Levesque, 1990c).

Under these hypotheses, how should the mental state of a rational agent participating in a conversation evolve? In the sequel we call belief change the process leading an agent from a mental state to a new one. This illustrates that in a conversation agents might change their mind, make mistakes, understand wrongly, . . . Since by our cooperation hypothesis the agents interact with each other in order to achieve the dialogue goal, they are the victims of such phenomena. They must consequently be taken into account when modelling the evolution of mental states.

In our example, the system

• accepts some information (e.g. information about destination and class -cf. u 1 );

• derives supplementary information not directly contained in the utterance by using laws about the world (e.g. to derive the price if the user informs about his destination and class -cf. s 2 );

• sometimes accepts information contradicting its own beliefs, in particular when the user changes his mind (e.g. switching from a first-class ticket to a second class ticket -cf. u 2 );

• preserves some information it believed before the utterance (e.g. the system preserves the destination even when the class changes -cf. u 2 );

• may refuse to take over some information, in particular if the user tries to inform the system about facts the user isn't competent at (e.g. prices of train tickets -cf. s 4 ).

To sum up, s has two complementary tasks: (1) dealing with contradictions between his mental state and consequences of the input, and (2) preserving his old beliefs that do not contradict this input.

We consider each participant to be a rational agent having mental states represented by different mental attitudes such as belief, choice, goal, intention . . . Belief change takes place within a formal rational balance theory and a formal rational interaction theory à la (Cohen andLevesque, 1990a, 1990c). These approaches analyse linguistic activity within a theory of actions: this is the base of so-called BDI-architectures (for Belief, Desire and Intention). Each utterance is represented by a (set of) speech act(s) [START_REF] Austin | How To Do Things With Words[END_REF][START_REF] Searle | Speech acts: An essay in the philosophy of language[END_REF], in a way similar to [START_REF] Sadek | Dialogue acts are rational plans[END_REF].1 Belief change triggered by these speech acts is analysed in terms of consequences of these speech acts.

From an objective point of view, a dialogue is a sequence of sets of speech acts (α 1 , . . . , α n ), where each α k+1 maps a state S k to a new state S k+1 :

S 0 α 1 -→ S 1 α 2 -→ . . . αn -→ S n .
S 0 is the initial state (before the dialogue starts). Given S k and α k+1 , our task is to construct the new state S k+1 .

The background of our work is an effective generic real-time cooperative dialogue system which has been specified and developed by the France Telecom R&D Center. This approach consists in first describing the system's behaviour within a logical theory of rational interaction (Sadek, 1991[START_REF] Sadek | Dialogue acts are rational plans[END_REF][START_REF] Sadek | A study in the logic of intention[END_REF], and second implementing this theory within an inference system called ARTIMIS [START_REF] Bretier | A rational agent as the kernel of a cooperative spoken dialogue system: Implementing a logical theory of interaction[END_REF][START_REF] Sadek | Effective human-computer cooperative spoken dialogue: The AGS demonstrator[END_REF][START_REF] Sadek | ARTIMIS: Natural dialogue meets rational agency[END_REF]. For a fixed set of domains, this system is able to accept nearly unconstrained spontaneous language as input, and react in a cooperative way. The activities of the dialogue system are twofold: to take into account the speaker's utterances, and to generate appropriate reactions. The latter reactive part is completely defined in the current state of both the theory and the implementation. On the other hand, the acceptance of an utterance is handled only partially, in particular its belief change part.

In our approach, building on previous work in [START_REF] Del Cerro | Belief reconstruction in cooperative dialogues[END_REF], we implement belief change by an axiom of belief adoption and one of belief preservation. Both of them are based on our key concept of topic of information. We refine our previous work by contextualizing topics by mental attitudes of the agents.

We aim at a logic having both a complete axiomatization and proof procedure, and an effective implementation. This has motivated several choices, in particular a Sahlqvist-type modal logic (for which general completeness results exist) that is monotonic (contrarily to many approaches in the literature) and which has and a notion of intention that is primitive (contrarily to the complex constructions in the literature).

In the next section we discuss the failure of the existing approaches to correctly handle belief change (Sect. 2). Then we present an original approach based on topics (Sect. 3). This is embedded in a BDI framework (Sect. 4). Finally we illustrate the approach by a complete treatment of our running example (Sect. 5).

Existing approaches

The most prominent formal analysis of belief change has been done in the AGM [START_REF] Alchourrón | On the logic of theory change: Partial meet contraction and revision functions[END_REF] and the KM [START_REF] Katsuno | On the difference between updating a knowledge base and revising it[END_REF] frameworks. There, a belief change operator • is used to define the new state S • A from the previous state S and the input A. 2 There are two difficulties if we want to use such a framework. First, update operators have only been studied up to now for classical propositional logic, and not for epistemic or doxastic logic. 3 But an appropriate theory of dialogues should precisely be about the change of beliefs about other agents' beliefs: an agent i believing that p and that another agent j believes p must be able to switch to believing that j believes ¬p, while maintaining his belief that p. Nothing is said about that in the current theories of revision and updates.

The second difficulty is that both revision and update have several common properties that must be refined or rejected. For example, the postulate (S • A) → A (input A has always priority) is problematic : in some approaches the new information may be rejected (as in Sadek's) ; in our approach, the new information is always accepted, but not all its consequences. We reject the postulate (S • A) ↔ S if S → A because it neglects the over-informing nature of some information: our agents may have different behaviour in the cases of over-information.

In the rest of this section we review the logical analyses of belief change in dialogues that have been proposed in the literature. Due to the above difficulties to formalise belief change within the existing frameworks for revision or update, belief change is integrated into a formal theory of rational behaviour.

Cohen and Levesque

Cohen and Levesque have defined in (Cohen andLevesque, 1990a, 1990c) a formal theory of rational interaction where an agent may accept new pieces of information ("inputs" for short). In this approach, the input rather corresponds to the speaker's intention to obtain some effect than to the speech act itself. The hearer's belief adoption is conditioned by the speaker's sincerity. Their theory allows the agent both to change his beliefs, and to reject the input (if the speaker is believed to be insincere).

However, as Sadek notes (Sadek, 1991), even lies might generate some effects (e.g. the hearer adds to his beliefs that the speaker is insincere). Thus even if the input is rejected the mental state of the hearer evolves.

Finally, in their approach beliefs not undermined by the act are never preserved from the preceding mental state to the new one. (cf. the frame problem in Artificial Intelligence [START_REF] Mccarthy | Some philisophical problems from the standpoint of artificial intelligence[END_REF].) Thus inconsistency of the newly acquired beliefs with old ones is never the case, simply because old beliefs are given up by the agent. (Such a behaviour corresponds to what has been called the trivial belief change operation in the AGM and KM literature.)

Perrault

Perrault's system is based on Reiter's default logic [START_REF] Reiter | A logic for default reasoning[END_REF]

Do Assert i,j A ,t ⇒ Bel i,t A (5)
Moreover there is a default schema saying that if A ⇒ B is a default then Bel i,t A ⇒ Bel i,t B is also a default, for every agent i and timepoint t.

Here sincerity is not required in order to admit an act (as illustrated by the axiom ( 3)). But an agent consumes its effects only if he doesn't believe the converse of this effect yet (in terms of defaults: if the effect is consistent with his current beliefs, cf. ( 5)). Thus the speaker does not have the right to lie, to make mistakes or to change his mind, else the effect of his act will never be consumed (in technical terms, the default will be blocked). This is at the origin of an even more radical behaviour: as highlighted in [START_REF] Appelt | A nonmonotonic logic for reasoning about speech acts and belief revision[END_REF]), Perrault's agents never question old beliefs and expand their mental state (in the sense of the AGM framework). Indeed, it follows from the axioms (1) and ( 2) that Bel i,t A → Bel i,t+1 A. Consequently if a belief stemming from memory conflicts with a belief stemming from the act then the default (5) will never been applied, and the effect will never be consumed.

Perrault is aware of that and suggests to achieve persistence by a default rule:

Persistence (bis):

Bel i,t+1 Bel i,t A ⇒ Bel i,t+1 A (6)
But as he notes himself, in this case there are always two extensions: one where the agent preserves his (old) beliefs and then adopts the input if it is consistent with these beliefs, and another one where the agent adopts the input and then preserves those old beliefs that are consistent with the new information. But there seems to be no way of determining which choice the agent should make.

Perrault's approach has some other problems that we do not discuss here (e.g. if the speaker ignores whether A is the case, then he starts to believe it as soon as he utters that A, cf. [START_REF] Appelt | A nonmonotonic logic for reasoning about speech acts and belief revision[END_REF])).

Sadek

Sadek defines a theory of rationality similar to Cohen and Levesque's, enriching it with two new mental attitudes, viz. uncertainty and need (Sadek, 1991[START_REF] Sadek | A study in the logic of intention[END_REF]. In his belief reconstruction [START_REF] Sadek | Towards a theory of belief reconstruction: Application to communication[END_REF], he presents an alternative to Perrault's approach. He enriches the latter's theory by an axiom of admission, and orders the application of his axioms of memory, admission, effects acceptance and preservation. His axiom of admission describes the behaviours that can be adopted by an agent, but does not specify the way the agent chooses between different possible behaviours. In particular he enables the hearer to reject an act. The latter point seems problematic to us, given that hearers do not reject an act that has been performed, but rather (hypothetically) accepts it in order to derive that it was not this one that has been performed.

Rao and Georgeff

In several papers, Rao and Georgeff have proposed theories and architectures for rational agents [START_REF] Rao | Modeling rational agents within a BDI-architecture[END_REF]. Such a theory can in principle be applied to dialogues. In [START_REF] Rao | An abstract architecture for rational agents[END_REF], in a way similar to STRIPS, actions and plans are represented by their preconditions together with add-and delete-lists. The latter lists are restricted to sets of atomic formulas. In such a framework, one can a priori neither represent non deterministic actions nor actions with indirect effects (obtained through integrity constraints). Even more importantly, actions can only have effects that are factual: this excludes the handling of speech acts, whose effects are epistemic, and are typically represented by means of nested intensional operators (such as intentions to bring about mutual belief). Recently, they defined a tableau proof procedure for their logic [START_REF] Rao | Decision procedures for BDI logics[END_REF].

Appelt and Konolige

Appelt and Konolige highlight the problems of Perrault's approach [START_REF] Appelt | A nonmonotonic logic for reasoning about speech acts and belief revision[END_REF]. They propose to use hierarchic auto-epistemic logic (HAEL) as a framework.

Basically, what one gains there is that application of defaults rules can be ordered in a hierarchy. This can be used to fine-tune default application and thus avoid unwanted extensions.

Apart from the relatively complex HAEL technology, it appears that Appelt and Konolige's belief adoption criterion encounters problems similar to Perrault's. Suppose the hearer has no opinion about p. Now if the speaker informs the hearer that p, then under otherwise favourable circumstances the hearer adopts p. But if the speaker informs the hearer that the hearer believes p (or that he believes the hearer believes p), then it is clearly at odds with our intuitions that the hearer should accept such an assertion about his mental state. The only means to avoid the latter behaviour is to shift the hearer's ignorance about p to the level of the HAEL hierarchy that has priority (level 0). But in this case the acceptation of the assertion that p would be blocked as well.

Topic-based belief change

The modal language

Like the previously cited authors, we work in a multimodal framework, with modal operators of belief, mutual belief, intention and action. Our language is that of first-order multimodal logic without equality and without function symbols [START_REF] Chellas | Modal Logic: an introduction[END_REF][START_REF] Hughes | An Introduction to Modal Logic[END_REF][START_REF] Popkorn | First Steps in Modal Logic[END_REF]. We suppose that ∧, ¬, and ∀ are primitive, and that ∨, →, ⊥ and ∃ are defined as abbreviations in the usual way. Let AGT be the set of agents. For i, j ∈ AGT , the belief operators Bel i and Bel i,j respectively stand for "the agent i believes that" and "it is mutual belief of i and j that". For each i ∈ AGT , the intention operator Intend i stands for "the agent i intends that". In our running example, we use two particular agents, s and u, which stand for the system and the user.

Speech acts are represented by tuples of the form FORCE i,j A where FORCE is the illocutionary force of the act, i, j ∈ AGT , and A is the propositional content of the act. For example Inform u,s Dest(Paris) represents a declarative utterance of the user informing the system that the destination of his ticket is Paris. Let ACT be the set of all speech acts.

With every speech act α ∈ ACT we associate two modal operators Done α and Feasible α . Done α A is read "speech act α has just been performed, before which A was true"; Feasible α A is read "speech act α is feasible, after which A will be true". 4 In particular, Done α and Feasible α are respectively read "α has just been performed" and "α is feasible" (or "can be performed"). Using the Done α operator, the beliefs of the system at the state S k can be kept in memory at state S k+1 : if B is the conjunction of all beliefs of the agent i at the (mental) state k, and α has just been done, then Bel i Done α B is the memory of i in the state k + 1.

To express temporal properties, we define the Always operator, and its dual operator Sometimes. AlwaysA means "A always holds" and SometimesA means "A sometimes holds". The operator Always will enable us in particular to preserve the domain laws in all states.

Formally, acts and formulas are defined by mutual recursion. This enables speech acts where the propositional contents is a non-classical formula. For example : Bel s Done Informu,s Bel u Bel s p Bel s Bel u Bel s ¬p is a formula.

The problem of belief change

In our approach, unlike to Sadek's, we always accept5 speech acts, but we proceed in two steps: the agent accepts the indirect and intentional effects, but only adopts the speaker's beliefs if he believes the speaker to be competent at these beliefs. Thus, speaker competence is our criterion to determine which part of the input must be accepted by the hearer and which part must be rejected. For example, s accepts input about the new class (after u 2 ) but rejects input about the price (after u 3 ), the reason being that he considers u to be competent at classes but not at ticket prices.

Which beliefs of the hearer can be preserved after the performance of a speech act? Our key concept here is that of the influence of a speech act on beliefs. If there exists a relation of influence between the speech act and a belief, this belief cannot be preserved in the new state. In our example, the old transport class cannot be preserved through u 2 , because the act of informing about classes influences the hearer's beliefs about classes.

How can we determine the competence of an agent at beliefs and the influence of a speech acts on beliefs? The foundation of both notions will be provided by the concept of a topic: we start from the idea that with every agent, speech act, and formula, some set of topics can be associated. Thus, an agent i is competent at a formula A if and only if the set of topics associated with A is a subset of the set of topics associated with i -the set of topics i is competent at. And a formula A is preserved after the performance of a speech act α if A and α have no common topic, i.e. occurring both in the set of topics associated to A and in the set of topics associated to α. We give the formal apparatus in the rest of the section.

Topic structures

The concept of topic has been investigated both in linguistics and philosophical logic. For example, in [START_REF] Büring | Topic[END_REF] a semantical value related to the topics is associated with each English sentence. Van Kuppevelt has developed a notion of topic based on questions, and has applied it to phenomena of intonation [START_REF] Van Kuppevelt | Topic en Comment[END_REF][START_REF] Van Kuppevelt | Discourse structure, topicality and questioning[END_REF]. In [START_REF] Ginzburg | Resolving questions I,II[END_REF], some sets of topics play a decisive role in the coherence of dialogues.

Several approaches to the notion of topic exist in the philosophical logic literature, in particular those of [START_REF] Lewis | General semantics[END_REF] and [START_REF] Goodman | About. Mind[END_REF]. Goodman's notion of "absolute aboutness" is defined purely extensionally. Hence for him logically equivalent formulas are about the same topics, while this is not the case for us. Moreover, as he focuses on the "informative aspect" of propositions, the subject of a tautology is the empty set. [START_REF] Epstein | The Semantic Foundations of Logic Volume 1: Propositional Logic[END_REF] notion is quite different from Lewis' and Goodman's. He defines the relatedness relation R as a primitive relation between propositions because "the subject matter of a proposition isn't so much a property of it as a relationship it has to other propositions" (Epstein, 1990, page 62). Thus, he does not represent topics explicitly. Then he defines the subject matter of a proposition A as s(A) = {{A, B} : R(A, B)}. More precisely, s is called the subject matter set-assignment associated with R (Epstein, 1990, page 68). Epstein shows that we can also define s as primitive, and that we can then define two propositions as being related if they have some subject matter in common. Our subject function can be seen as an extension of this function to a multi-modal language.

For us, topics as themes in context, where the set of themes is an arbitrary set and contexts correspond to mental attitudes of agents. We define three functions associating topics to formulas, agents, and speech acts.

Themes, contexts, and topics

A theme is what something is about. For example, information on the destination is about the destination but not about the transport class.

Let T = ∅ be a set that we call the set of themes. In our running example, we suppose that T contains destinations, classes, prices, and payment.

Definition 1 Let i ∈ AGT . Then ma i is called an atomic context. A context is a possibly empty sequence of atomic contexts. The empty context is noted λ. C is the set of all contexts. ma i stands for "the mental attitude of agent i ".

Definition 2 A topic of information (or contextual thematic structure) is a theme together with a context, denoted by c:t, where t ∈ T and c ∈ C.

For example, ma u :price is a topic consisting in the user's mental attitude at prices, and ma s :ma u :price is a topic consisting in the system's mental attitude at the user's mental attitude at prices.

For the empty context λ, we have

λ:c = c:λ = c. ( 7
)
By convention, we identify λ:t with t. In order to take into account introspection, we postulate

ma i :ma i = ma i . ( 8
)
Given a set of themes and a set of agents we note T the associated set of topics. T n is the set of topics whose contexts have length at most n. As we have identified λ:t with t, T 0 is the set of themes. In this paper, for reasons of representational economy we shall suppose that the length of each context is at most 2. Hence we restrict T to T 2 . 6Note that we have overloaded the operator ":". As we only use λ, c, ma i , . . . for contexts and only t, t , . . . for themes, there should be no confusion.

The subject of a formula

Definition 3 The subject of a formula A is a set of topics associated with A (the topics A is about). This notion is formalised by a function subject mapping every formula to a set of topics from T.

We give the following axioms.

Axiom 1 subject(p) ⊆ T and subject(p) = ∅ where p is atomic.

An intuition that might be helpful is to think of the subject of p as the predicate name of p.

Axiom 2 subject( ) = ∅.

Note that this slightly differs from Epstein's account.7 Axiom 3 subject(¬A) = subject(A).

Axiom 4 subject(A ∧ B) = subject(A) ∪ subject(B). Axiom 5 subject(Bel i A) = {ma i :c:t | c:t ∈ subject(A)}.
Note that c might be the empty context here. Thus, in our running example:

subject(Class(1st)) = {class} subject(Dest(Paris)) = {destination } subject(Bel s Bel u Price(80 ) ∧ Bel s Price(100 )) = {ma s :ma u :price} ∪ {ma s :price}. Axiom 6 subject(Bel i,j A) =subject(Bel i A)∪ subject(Bel j A)∪ subject(Bel i Bel i,j A)∪ subject(Bel j Bel i,j A). Axiom 7 subject(Intend i A) = subject(Bel i A). Axiom 8 subject(Done α A) = subject(A)∪subject(A ) where A is the propositional content of α. 8
Axiom 9 subject(∀xA) = subject(A).

Axiom 10 subject(A[t/x]) ⊆ subject(A), where A[t/x] is the formula resulting from the substitution of the variable x by the term t.

This expresses that if an instance of A is about some topic, then A is about that topic as well.

Due to our restriction to contexts of length 2 we suppose that contexts of the form ma i :ma j :c are reduced to ma i :ma j . The corresponding subject function can be obtained by first simplifying the topics by ( 7), ( 8), and the above equation λ:t = t; and then by reducing those of length greater than 2 to topics of length 2. For example, subject(Bel u Bel u Price( 150)) = {ma u :price}, and subject(Bel u Bel s Bel k Price( 150)) = {ma u :ma s :price}, for any agent k.

The competence of an agent

Definition 4 The competence of an agent i is a set of topics associated with i (the competence of i). This notion is formalised by a function competence mapping every agent to a set of topics from T.

We assume every agent is competent at his mental states.

Axiom 11 competence(i) ⊇ {ma i :t | t ∈ T }.
An agent may be competent at some facts. For example, competence(u) contains destinations and classes, but not prices. 9Competence will allow us to formulate in the next section our belief adoption axiom which basically says: "an agent j adopts the belief of another agent i about a formula A if j considers that i is competent at the subject of A".10

The scope of an act

Definition 5 The scope of a speech act α is a set of topics associated with α (the scope of α). This notion is formalised by a function scope mapping every speech act to a set of topics from T.

Suppose the user informs the system about his destination. As the user is competent at destinations, this speech act influences the system's factual beliefs about the destination. It also influences its beliefs about prices, because a destination change possibly entails a price change. Hence scope( Inform u,s Dest(Paris) ) contains the topics destination , price, ma s :destination and ma s :price.

The scope of a speech act determines which mental attitudes of an agent might be changed by this act.

In the formalisation of speech acts the illocutionary force determines a set of formula schemes (the preconditions and the effects of the act) instantiated by the propositional content. The scope of a speech act is the set of topics associated with this act, and must depend on its illocutionary force and its propositional content.

Roughly speaking, the themes of a speech act are determined by its propositional content, and the context by its illocutionary force. Thus, contexts tell us which mental attitudes might change. We propose some axioms in order to compute the scope of a speech act.

The performance of a speech act always influences some mental attitudes of the hearer. In particular: Axiom 12 scope( FORCE i,j A ) ⊇ {ma j :ma i :t | t ∈ subject(A)}, for every illocutionary force FORCE.

For example, consider the speech act where the user informs the system about the ticket price. This speech act influences the system's belief about the user's belief about prices. Now consider the case where α is a request act. We postulate that the type of mental attitudes ma j :ma i :t is the only one that is in the scope of α.

Axiom 13 scope( Request i,j A ) ⊆ {ma j :ma i :t | t ∈ T }.

Topic structures

We have thus defined three functions mapping the different types of expressions in our language to topics. Definition 6 Given a set of themes and a set of agents, a topic structure consists of the associated set of topics T together with the subject, scope, and competence functions.

Is there an interaction between these functions? Consider the speech act α = Inform u,s Class(2nd) . It follows from the axiom we gave for the scope function that ma s :ma u :class ∈ scope(α). Given that the user is competent at classes, α also influences s's factual beliefs about the class, i.e. ma s :class ∈ scope(α).

We propose the following constraint for acts of the informative type.

Axiom 14 If A contains no modal operator, α = Inform i,j A , and t is a theme such that t ∈ subject(A) ∩ competence(i) then t ∈ scope(α) and ma j :t ∈ scope(α).

Note that if this axiom is violated, then the mental state of the hearer might become inconsistent: suppose ma s :class ∈ scope(α). Then Bel s ¬Class(2nd) would be preserved after α, while the indirect effect Bel s Bel u Class(2nd) of α would entail Bel s Class(2nd) by the belief adoption axiom.

A given topic structure will allow us to compute the new state by means of two principles: belief adoption and preservation. In the next section we shall present these principles.

Axioms for belief change

Our axioms for belief change are based on a given topic structure. The first one allows to preserve beliefs:

Axiom Schema of Belief Preservation. Done α A → A if scope(α) ∩ subject(A) = ∅ and
A contains no Done β operator, for any β.

The restriction to formulas without Done β operators is necessary because our reading of Done β is that β has just been performed (and not at some arbitrary time point in the past).

The second axiom schema allows to adopt beliefs.

Axiom Schema of Belief Adoption.

Bel i A → A if subject(A) ⊆ competence(i)
The schema expresses that if agent i both believes that A and is competent at A, then A is true. For example the formula Bel s Bel u Dest(Paris) → Bel s Dest(Paris) can be proved from the instance Bel u Dest(Paris) → Dest(Paris) of the belief adoption axiom. Indeed, the belief adoption axiom applies because subject(Dest(Paris)) ⊆ competence(u), and we can then use the standard modal necessitation and K-principles for Bel s . On the contrary, Bel u Price(80 ) → Price( 80) is not an instance of our axiom schema, because subject(Price( 80)) ⊆ competence(u). 11 11 In our preceding approach [START_REF] Del Cerro | Belief reconstruction in cooperative dialogues[END_REF] we had used non-contextualised topics to formulate axioms for belief change. This turned out to be too weak. Suppose the system believes p, and believes that the user believes p: Bel s p ∧ Bel s Bel u p. Now suppose the user informs the system that he does not know whether p. Then the belief Bel s Bel u p should go away, while Bel s p can be expected to be preserved. Hence the scope of this speech act should contain the system's attitudes towards the users's attitudes towards p, but not the system's attitudes towards p. We were not able to distinguish that before.

Discussion

Our subject function is not extensional: logically equivalent formulas may have different topics. In particular, subject(p ∨ ¬p) = subject( ). Indeed, p ∨ ¬p being an abbreviation of ¬(¬p ∧ ¬¬p), we have subject(p ∨ ¬p) = subject(p) = ∅, while subject( ) = ∅. 12It follows from our axioms that the subject of an arbitrary formula is completely determined by the subjects of its atomic formulas. This is representationally interesting, but it is certainly a debatable choice. Notwithstanding, the way we use the subject function is sound: suppose e.g. subject(p) = {t}, subject(q) = {t }, and scope(α) = {t }. Hence p and p ∧ (q ∨ ¬q) do not have the same subject, and Done α p → p is an instance of the preservation axiom, while Done α (p ∧ (q ∨ ¬q)) → (p ∧ (q ∨ ¬q)) is not. But the latter formula can nevertheless be deduced from the former by standard modal logic principles: as p ↔ p∧(q∨¬q) we have Done α p ↔ Done α (p∧(q∨¬q)). Hence the theorem Done α p → p enables us to deduce Done α (p ∧ (q ∨ ¬q)) → (p ∧ (q ∨ ¬q)).

We did not formulate such strong compositionality axioms for the scope function. The reason is that a speech act might influence more than the topics of its propositional contents. For example, the scope of Inform u,s Class(1st) contains not only ma u :ma s :class but also ma u :ma s :price. Our hypothesis here is that the scope of a speech act is determined by the subject of its propositional contents together with the integrity constraints e.g. linking destinations, classes, and prices. This is subject of ongoing research.

Finally, as we have mentioned, competence can be generalised in order to involve an agent j believing i to be competent at some topic. Then our axiom schema would take the form Bel j (Bel i A → A) if subject(A) ⊆ competence(j, i).

The multimodal framework

Axiomatics

In this section we give the logical axiom and inference rule schemas. They are those of a normal modal logic of the Sahlqvist type [START_REF] Sahlqvist | Completeness and correspondence in the first and second order semantics for modal logics[END_REF], for which general completeness results exist.

Just like in (Cohen and Levesque, 1990b;[START_REF] Perrault | An application of default logic to speech act theory[END_REF]Sadek, 1991), with each belief operator we associate the (normal) modal logic KD45 [START_REF] Halpern | A guide to the modal logics of knowledge and belief: preliminary draft[END_REF]. Thus we have the following schemas:

A Bel i A (RNBel) Bel i A ∧ Bel i (A → B) → Bel i B (KBel) Bel i A → ¬Bel i ¬A (DBel) Bel i A → Bel i Bel i A (4Bel) ¬Bel i A → Bel i ¬Bel i A (5Bel)
The rule schema of necessitation (RNBel) and the axiom schema (KBel) are in every normal modal logic, (DBel) is the "axiom of rationality" (if i believes A then he doesn't believe ¬A), (4Bel) is the axiom of positive introspection (if i believes A then he believes that he believes A), and (5Bel) is the axiom of negative introspection (if i doesn't believe A then he believes that he doesn't believe A).

With each operator of mutual belief we associate the normal modal logic KD45, whose logical axioms are similar to these of belief operators. We suppose that mutual belief of i and j implies belief of both i and j, i.e. we have the logical axiom

Bel i,j A → (Bel i A ∧ Bel j A) ( 9 )
To keep things simple we suppose that the logic of each operator of intention is the normal modal logic KD. (The inference rule (RNIntend) and the axioms (KIntend) and (DIntend) are just as (RNBel), (KBel) and (DBel).)

Obviously, our notions of mutual belief and intention are oversimplified: first, our condition ( 9) linking belief and mutual belief is weaker than usual, where mutual belief Bel i,j A is identified with the infinite formula Bel i A ∧ Bel j A ∧ Bel i Bel j A ∧ Bel j Bel i A ∧ . . .. We argue that such an inductive construction is not necessary at least in a first approach: as Cohen and Levesque, we suppose that mutual belief directly comes as the indirect effect of a speech act. (This is different e.g. from Perrault's view, where mutual belief is constructed via default rules. See (Traum, 1999, sect. 7.2.1) for a discussion of these issues.) Second, we offer no particular principle for intentions. We did this because the existing analyses of intention vary a lot, and the systems that have been put forward in the literature are rather complex. A normal modal logic for intention is too strong: for example, (KIntend) is not a theorem of Cohen and Levesque's logic (and neither is its converse). 13All Done α and Feasible α operators obey the principles of the (normal) modal logic K. As they are modal operators of "possible" type, the rule of necessitation and the K-axiom take the form:

¬A ¬Done α A (RNDone) (¬Done α A ∧ Done α B) → Done α (¬A ∧ B) ( K Done) ¬A ¬Feasible α A (RNFeasible) (¬Feasible α A ∧ Feasible α B) → Feasible α (¬A ∧ B) ( K Feasible)
For example the first rule means 'it is never the case that inconsistent formulas hold before action α'.

We suppose speech acts to be deterministic: their performance should lead to a single state. This is expressed by the converse (DC) of the modal axiom (D). 14 Done α A → ¬Done α ¬A (DCDone)

Feasible α A → ¬Feasible α ¬A (DCFeasible)
For example the last axiom says that there is only one way of executing α (and not one where A holds afterwards, and another one where ¬A holds afterwards). The following conversion axioms [START_REF] Van Benthem | The Logic of Time[END_REF] account for the interaction between the Done α and Feasible α operators:

Feasible α ¬Done α A → ¬A (10) Done α ¬Feasible α A → ¬A (11)
The logic of the Always operator is the normal modal logic KT4. (KTime) and (4Time) are just as (KBel) and (4Bel).

AlwaysA → A (TTime)
The dual to Always is Sometimes:

SometimesA def = ¬Always¬A (DefSometimes)
In order to describe some interactions between the different mental attitudes (Cohen and Levesque, 1990b), we propose the following logical axioms.

Intend i A → Intend i Bel i A (12) Bel i Intend i A ↔ Intend i A (13) Bel i ¬Intend i A ↔ ¬Intend i A ( 14
)
Intend i Bel j A → Bel i A ∨ Intend i Bel i A (15) Bel i Done FORCE i,j A ↔ Done FORCE i,j A (16)
The semantics of each of these logical axioms is given in (Longin, 1999) and (Herzig and Longin, 2000a).

Laws

Laws are non-logical axioms. We suppose that laws cannot be modified by the belief change process in a dialogue. We use the Always operator to preserve them in every state. We note LAWS the set of all laws. (which might also be called our non-logical theory).

There are three kinds of laws: static laws (alias domain laws, similar to integrity constraints in data bases); laws governing speech acts (to describe the different preconditions and effects of the speech acts); reactive laws (to describe some reactive behaviours generating intentions).

Static laws

Some of the static laws are believed only by the system, such as those relating destinations, classes, and ticket prices:

AlwaysBel s (Dest(Paris) ∧ Class(1st) → Price(150 )) ( 17
)
AlwaysBel s (Dest(Paris) ∧ Class(2nd) → Price( 100)) (18) ... Some static laws are known both by the system and the user. More precisely, they are mutual beliefs:

AlwaysBel i,j ¬(Class(1st) ∧ Class(2nd)) (19) AlwaysBel i,j ¬(Dest(Paris) ∧ Dest(New-York)) (20)
...

(There is only one class for a particular ticket, etc.)

Laws governing speech acts

Following [START_REF] Sadek | Dialogue acts are rational plans[END_REF], we associate with each speech act

• a precondition;

• an indirect effect (viz. the persistence of preconditions after the performance of the speech act);

• an intentional effect (in the Gricean sense [START_REF] Grice | Utterer's meaning and intentions[END_REF]));

• a perlocutionary effect (expected effect).

Preconditions take the form AlwaysBel k ¬Done α ¬A where A is a precondition of α, and k an agent. Note that there is no constraint on k: k may be the speaker or some hearer (mutual belief). For example the precondition of an informative act is:

AlwaysBel k ¬Done Inform i,j A ¬(Bel i A ∧ ¬Bel i Bel j ¬Bel i A∧ ¬Bel i BelIf j A ∧ ¬Bel i Bel j BelIf j A) (21)
where BelIf j A is an abbreviation of Bel j A ∨ Bel j ¬A. 15 (Preconditions and effects of our speech acts follow from [START_REF] Sadek | A study in the logic of intention[END_REF][START_REF] Sadek | Dialogue acts are rational plans[END_REF].) The precondition means:

• the agent i believes A;

15 If we suppose that p must be either true or false (in the real world), and if BelIf j p holds, then j knows necessarily what is true in the real world (but we do not knows whether p is true or false). Then, BelIf j A is read "j knows if A is true or not". In KD45, Bel j BelIf j A is equivalent to BelIf j A. In (21), we keep Bel j BelIf j because the precondition is a simplification of an infinite conjunction in the original precondition [START_REF] Sadek | Dialogue acts are rational plans[END_REF].

• i doesn't believe that j believes that he doesn't believe A (sincerity condition)16 ;

• i doesn't believe that j knows if A holds or not;

• i doesn't believe that j believes that j knows if A holds or not (condition of context relevance)17 .

From this law and the standard principles of normal modal logics we can prove formulas of the form AlwaysBel k (Done α → Done α A ), where A is a precondition of α. For informative acts we have:

AlwaysBel k (Done Inform i,j A → Done Inform i,j A (Bel i A∧ ¬Bel i Bel j ¬Bel i A ∧ ¬Bel i BelIf j A)) (22)
Suppose the user informs the system he wants a first class ticket. 22) with k = i = u, j = s, and principles of normal modal logics).

The formulas 2. and 4. are what we call presuppositions: immediately after a speech act α its observers believe that the preconditions of α were true just before the performance of this act. As illustrated by 4., the speaker is also viewed as an observer of his act. In this case, presuppositions are part of his memory (he remembers what he believed just before the performance of the speech act).

The indirect effect is the preservation of preconditions, and must be derived from presuppositions (cf. 2nd and 4th items in the above example) by formulas of the form AlwaysBel k (Done α A → A ) where A is a precondition of α: this will follow from our axiom schema of belief preservation (cf. Sect. 3.4).18

The intentional effect is always accepted by the hearer and corresponds to the hearer's recognition of the speaker's intention (in Grice's sense). The acceptance of this effect is expressed by formulas of the form AlwaysBel k (Done α → A ), where A is the intentional effect of α. For an informative speech act the instance of this schema is:

AlwaysBel k (Done Inform i,j A → Intend i Bel j Intend i Bel j A) ( 23
)
The perlocutionary effect does not obtain systematically: our agents being autonomous, the expected effect of an act does not obtain systematically. Hence the propositional content is not necessarily added to the hearer's belief state. In the case where the new state (obtained by the admission of a speech act and the acceptance of its indirect and intentional effects) entails the perlocutionary effect, we say that the latter has been accepted.

Reactive laws

The reactive laws allow us to generate some intentions:

AlwaysBel i (A ∧ Bel j ¬A → Intend i Bel j A) (24) AlwaysBel i (A ∧ Done Inform j,i A Bel i ¬A → Intend i Bel j Bel i A) ( 25
)
AlwaysBel i (Done α (Done γ ∧ Bel i Done β ) → Intend i Bel j Bel i Done α Done γ ) (26) . . .

For example, ( 24) is used for the first part of the utterance s 4 in our running example: the system invalidates the price of 80 , and informs the user that the price is 100 .

Formally: 24), 1. and 6.) (We didn't give the logical axioms we use; s and u are the agents i and j in the law (24), respectively.) The intentions in 5. and 7. are associated with a denying speech act (the price isn't 80 ) and an informative act (the price is 100 ), respectively.

1

Discussion

We have sketched a theory of change in the context of dialogues. Our framework is based on the notion of topic of information, which is exploited through topic-based axioms of belief adoption and preservation. We think that our concepts are natural and appealing. It is intuitively clear that these two mechanisms permit to implement all possible evolutions of belief.

The framework can be augmented by other concepts such as that of sincerity can be added. The latter could be implemented in a way similar to competence.

Beyond the example dialogue given in the paper, we have tested our approach on a list of toy dialogues provided by France Telecom R&D Center.

In our running example, the propositional contents of the speech acts is rather simple. However, in (Sadek, 1991;Longin, 1999) there have been defined laws permitting to treat more complex propositional contents.

Note that in some applications it might be necessary to revise part of the competence of an agent. This happens in particular when it turns out that an agent has forgotten information he is competent at. Suppose e.g. in u 4 the user says "Hum, finally I'll pay cash that first-class ticket." If we do not modify the competence function this case is handled as if u changed his mind about the train class: as u is competent at classes, s starts to believe that he now wants a first-class ticket again. What is needed here is to dynamically modify the competence function during the dialogue. This is possible in our framework. (As competence is a parameter of our logic, it amounts to modifying the logic.)

Perrault and Appelt & Konolige have argued that defaults are crucial elements in a theory of speech acts because they permit to transform absence of knowledge into knowledge. In a sense, what we do is to transfer that task to the metalinguistic relations of competence and scope. This permits to keep a monotonic framework, whose behaviour is considerably simpler and predictable than the nonmonotonic approaches of the literature.

  . A ⇒ B denotes a normal default. Do α,t means that action α is performed at time t, Observe j,t A means that agent j observes A at time t, and Assert i,j P means that agent i communicates propositional content P to agent j. The main axioms and default rules of Perrault's approach are as follows:

	memory: Bel i,t A → Bel i,t+1 Bel i,t A	(1)
	persistence: Bel i,t+1 Bel i,t A → Bel i,t+1 A	(2)
	observability: Do α,t ∧ Observe j,t Do α,t → Bel j,t+1 Do α,t
	where α is performed by the agent i	(3)
	belief transfer: Bel i,t Bel j,t A ⇒ Bel i,t A	(4)
	assertion rule:

  Intend s Bel u ¬Price(80 ) (by (24), 4. and 2.) 6. Bel s Bel u ¬Price(100 ) (by 2. and 3.) 7. Intend s Bel u Price(100 ) (by (

. Bel s Price(100 ) ( h y p o t h e s i s ) 2. Bel s Bel u Price(80 ) ( h y p o t h e s i s ) 3. Bel s,u ¬(Price(100 ) ∧ Price(80 )) (static law) 4. Bel s ¬Price(80 ) (by 1. and 3.) 5.

We rather use "set of speech acts" than "a speech act", because a (literal) speech act may entail indirect speech acts. We develop this question in(Herzig and Longin,

2000b).2 We view S as not closed under logical consequence. Therefore it can be confused with the conjunction of its elements). Just as[START_REF] Katsuno | On the difference between updating a knowledge base and revising it[END_REF], we view • as a (metalanguage) operator mapping the formulas S and A to a formula.

Nevertheless, it is known in the belief revision literature that the AGM revision postulates must be considerably weakened if the language contains modalities (Fuhrmann's impossibility theorem,[START_REF] Fuhrmann | Reflective modalities and theory change[END_REF],(Hansson, 1999, section 5.1)).

Doneα A et Feasibleα A are just as α -1 A and α A of dynamic logic[START_REF] Harel | Dynamic logic[END_REF].

"Accepting" an act means that we admit that it has been performed.

We did not find examples requiring length 3. Nevertheless, this restriction can be relaxed easily.

Indeed, Epstein stipulates that R(A, A) for every formula A. On the contrary, the present axiom makes that not(R( , )). More generally, we have R(A, A) iff the set of atoms of A is nonempty. Due to the logical operators and ⊥ in the language we had to modify that.

Another choice would have been subject(Doneα A) = subject(A) ∪ scope(α). But this would too much mix up the reading of the subject function of 'being about something' with that of the scope function of 'modifying the truth value'.

Note that an agent might be competent at mental attitudes of some other agent. This means that the former agent controls the latter. We do not exploit this further here.

Hence competence should be a 2-argument function. As we only have two participants in our examples, we have dropped the second argument for the sake of simplicity.

Note also that this is the reason why we didn't state as usually done in textbooks " abbreviates p ∨ ¬p, for some p", and instead added to the primitive operators ∧ and ¬ of our language.

However, one can define intention operators in a minimal models semantics à la(Chellas, 1980, Chap. 7). This has been undertaken in[START_REF] Herzig | Beliefs, intentions, speech acts and topics[END_REF] Herzig et al., 2000).

The second term is an abbreviation of Sadek's infinite conjunction:¬Bel i Bel j ¬Bel i A ∧ ¬Bel i Bel j Bel i ¬Bel i A ∧ ¬Bel i Bel j Bel i Bel j ¬Bel i A ∧ . . .

The second term is an abbreviation of Sadek's infinite conjunction:¬Bel i Bel j BelIf j A ∧ ¬Bel i Bel j Bel i BelIf j A ∧ ¬Bel i Bel j Bel i Bel j BelIf j A ∧ . . .

While the preservation of sincerity preconditions seems to be intuitively correct, it seems that the preservation of context relevance preconditions is an a priori choice of the agent, supposing that his act failed. In[START_REF] Herzig | Beliefs, intentions, speech acts and topics[END_REF] we have proposed to introduce a transient state of ignorance to overcome that.

We note that a possible worlds semantics for our multimodal logic can be given by adapting the one presented in (Fariñas del Cerro et al., 1998) (see (Herzig and Longin, 2000a)). Completeness can be proven in a fairly standard way. Indeed, all the semantical conditions are in a particular class that has been investigated in mathematical logic, and for which general completeness results exist (Sahlqvist, 1975;Catach, 1989;Gasquet, 1994). The only difference here is that the preservation and adoption conditions depend on topics. It has been shown in (Castilho et al., 1999) that nevertheless the standard Henkin proof technique applies straightforwardly.

We are currently implementing a tableau theorem prover for our logic. In previous work we have extended the standard tableaux method in order to deal with dependence information in reasoning about actions (Castilho et al., 1997;Castilho et al., 1999). The extension of our approach to the present topic-based framework is straightforward.

Acknowledgements

This work has been supported by the France Telecom R&D Center, scientific area "Intelligent Interactions and Dialogue", in the framework of contract 97 1B 046.

Thanks to Renata Wassermann, David Sadek and Jrme Lang for relevant discussions. The detailed comments and suggestions of an anonymous referee of Amstelogue'99 and of the reviewers of the present special issue have (hopefully) contributed to improve the paper both in form and contents.

We illustrate our analysis of the belief change process by means of our running example.

To each utterance we associate a speech act (e.g. α u i corresponds to utterance u i ). We describe parts of the different states S s i during our example. These parts correspond to the mental state of the system after the different speech acts of the user.

The set of themes is T = {class, destination , price, payment }.

The speech acts are:

The subjects of the atomic formulas are the predicate name, e.g. subject(Class(1st)) = {class}. The scopes of the speech acts are:

• scope(α u 1 ) = {ma s :ma u :t, ma s :t, t | t ∈ {class, destination , price};

• scope(α u 2 ) = {ma s :ma u :t, ma s :t, t | t ∈ {class, price};

• scope(α u 3 ) = {ma s :ma u :price};

The competence of the user and the system is:

We use the following abbreviations:

• C1 and C2 are Class(1st) and Class(2nd), respectively;

• P 1, P 2 and P 3 are Price(150 ), Price(100 ) and Price(80 ), respectively;

We have simplified the preconditions of the speech acts. α u 1 has the following effects.