Manuel Rebuschi
email: manuel.rebuschi@univ-nancy2.fr

L H S P -

Extended Game-Theoretical Semantics

Keywords: Game semantics, NL semantics, Meaning and interpretation, Skolem functions

A new version of Game-Theoretical Semantics (GTS) is put forward where game rules are extended to the non-logical constants of sentences. The resulting theory, together with a refinement of our criteria of identity for functions, provide the technical basis for a game-based conception of linguistic meaning and interpretation.

Introduction

Game-theoretical semantics (hereafter, GTS) was created by Hintikka during the 1960s and intended as a formalization of Wittgenstein's remarks on language games. Like other formal connections drawn between logic and game theory, it embodies several philosophically relevant features into semantics: the dynamics of language, language as an activity, language as a collective matter. A specific insight is offered by GTS through the notion of strategic meaning. I will propose to use this notion in order to account for linguistic interpretation, to be contrasted with meaning constitution. It will yield solutions to several issues every theory of linguistic meaning is confronted with, especially those involving an epistemic dimension. My proposal will be based on two moves: [START_REF] Van Benthem | The Epistemic Logic of IF Games[END_REF] the extension of semantic games to the subatomic components of sentences, and (2) a shift in our usual criteria of individuation of functions. The resulting conception of meaning is a two-component theory, but it does not use entities such as Frege's senses or Montague's functions defined on possible worlds. The main idea can be summed up as follows: in addition to the truth-conditions of a sentence, which are given by the existence of a winning strategy for the initial verifier of some semantic game, one should also consider the particular (implemented) strategies employed by concrete speakers. Such strategies correlated with the non-logical expressions of a given natural language consist in functions that pick up their extension relative to a given context. 1 However, they need not realize winning strategies in every context, what is required being that they reach socially acceptable approximations of the extension at stake. Sets of such functions are what is mastered by the agents to understand linguistic expressions. This informal account of truth-conditional meaning and strategy-based interpretation will get a more precise working out within the framework of GTS.

In the next section I will briefly sketch the required technical apparatus: standard and extended GTS for first-order formal languages, and the conception of Skolem functions as components of winning strategies. In Section 3 I will look into the application of GTS to natural language, and deal with the question of how to use and individuate Skolem functions in extended GTS. Two notions will be defined: that of eGTS meaning, as a set of implemented Skolem functions, and that of eGTS stereotype (more or less regimenting Putnam's idea of idiolectal meaning) as a set of implemented (but not always winning) strategies. Next, Section 4 will be devoted to examining a few puzzles of the philosophy of language.

2 Game-Theoretical Semantics and Skolemization

Usual GTS in a nutshell

Semantic games The general idea of GTS 2 is to associate to each firstorder (FO) sentence ϕ evaluated relative to some structure M = D, I a semantic game, denoted by G(ϕ, M) and played between two abstract players, the initial verifier ∃loise and the initial falsifier ∀belard, s.t. the first player (resp. the second one) has a uniform winning strategy iff the formula is true (resp. false) in M. Such evaluation games are played according to the following rules:

• (R.At). If α is a true atomic sentence (or identity) in M, then the verifier wins G(α, M), and the falsifier loses. If α is a false atomic sentence (or identity), the reverse obtains.

• (R.∨) In the game G(ϕ 1 ∨ ϕ 2 , M) the verifier picks out an index i ∈ {1, 2}.

The rest of the game is as in G(ϕ i , M).

• (R.∧) In the game G(ϕ 1 ∧ ϕ 2 , M) the falsifier picks out an index i ∈ {1, 2}.

The rest of the game is as in G(ϕ i , M).

• (R.∃)

The game G(∃xϕ(x), M) starts with the verifier choosing a member d ∈ D and a new name c to designate it; the rest of the game is as in G(ϕ(c), M).

• (R.∀)

The game G(∀xϕ(x), M) is similar, except that the choice is made by the falsifier.

• (R.¬)

The game G(¬ϕ, M) is like G(ϕ, M), except that the roles of the two players (as defined by the rules) are interchanged.

With such rules, one can define truth and falsity according to GTS:

M + GTS ϕ (ϕ is GTS-true in M) iff there is a winning strategy for the initial verifier (∃loise) in G(ϕ, M).

M -

GTS ϕ (ϕ is GTS-false in M) iff there is a winning strategy for the initial falsifier (∀belard) in G(ϕ, M).

Skolemization Assertion of the GTS truth-conditions for a sentence, i.e. of the existence of a winning strategy for ∃loise in the associated game, is expressible in the Σ 1 1 fragment of second-order logic. Each strategy can be represented by a finite sequence of Skolem functions corresponding to the moves made by the verifier (rules (R.∃) and (R.∨)) relative to those played by the falsifier. This will yield e.g.:

M + GTS ∀x∃y R(x, y) ⇐⇒ M ∃ f ∀x R(x, f (x)) M + GTS ∀x (ϕ 1 ∨ ϕ 2 ) ⇐⇒ M ∃ f ∀x (( f (x) = 0 ∧ ϕ 1 ) ∨ ( f (x) 0 ∧ ϕ 2 )) (1)
2 See [START_REF] Hintikka | Game-Theoretical Semantics[END_REF] for an overview. (In the second example one assumes that the model contains at least two elements, and that one of them is denoted by '0'.)

Skolemization is in fact a well-known transformation of FO formulas: In a formula in prenex normal form, replace each existential quantifier ∃x i by a (new) function symbol f i whose variables are those bound by the universal quantifiers of which ∃x i is within the scope. Following Hintikka, extend the introduction of function symbols to disjunctions (for models with at least two elements.) In what follows, Sk[ϕ] will denote a formula resulting from ϕ through such a transformation:

3 Sk[∀x∃y R(x, y)] = ∀x R(x, f(x)) Sk[∀x∃y∀z∃u ϕ(x, y, z, u)] = ∀x∀z ϕ[x, f 1 (x), z, f 2 (x, z)] Sk[∀x (ϕ 1 ∨ ϕ 2 )] = ∀x ((f(x) = 0 ∧ ϕ 1 ) ∨ (f(x) 0 ∧ ϕ 2 )) (2)
A second-order Skolem form of a given formula ϕ, hereafter symbolized by 2Sk[ϕ], obtains from a (first-order) Skolem form of ϕ in which each Skolem function symbol is replaced by an existentially quantified functional variable:

2Sk[∀x∃y R(x, y)] = ∃ f ∀x R(x, f (x)) (3)
Assuming the Axiom of Choice and the standard "full" semantics of secondorder logic, ϕ and Sk[ϕ] are equisatisfiable, and ϕ and 2Sk[ϕ] are equivalent.

Truth-Conditions

Assuming the Axiom of choice and the standard interpretation of second-order logic, the GTS truth-definition is equivalent to the standard one:

M + GTS ϕ ⇐⇒ M ϕ. (4)
The equivalence between GTS and Tarski-like semantics leads to the inescapable fact that for any FO sentence there is always a winning strategy for one of the players: bivalence corresponds to the determination of the semantic games.

GTS provides a nice and intuitive interpretation of Skolemization: the Skolem functions occurring in Sk[ϕ] are conceived of as the components of ∃loise's winning strategies in G(ϕ, M). For example in M = D, I , where D = N and "<" gets its usual interpretation, the formula ϕ = ∀x∃y (x < y) is obviously true. It admits of one skolemization, Sk[ϕ] = ∀x (x < f(x)), where the newly introduced symbol f can receive several values, each of which corresponds to a winning strategy available to ∃loise:

f 1 (x) = x + 1, f 2 (x) = 2x + 1, etc. The GTS-truth-conditions of ϕ are given by 2Sk[ϕ] = ∃ f ∀x (x < f (x)).

Extending GTS to non-logical constants

In standard GTS, Skolem functions replace existential quantifiers and disjunctions. From a meta-semantic point of view, they correspond to what is taken into account by the assignments in Tarski-like semantics. What I will put forward now is extending such a role of Skolem functions to what is dealt with by the interpretation function I of the model-theoretic structure M = D, I . To put it in another perspective: whereas GTS game rules are associated with logical constants, extended GTS (eGTS hereafter) will associate new rules with the non-logical vocabulary. 4 The notion of semantic game is thus extended to atomic sentences (and identities).

Atomic games

In eGTS, every sentence ϕ evaluated relative to a structure M is associated to a game eG(ϕ, M). This new game is identical to the game G(ϕ, M) played according to the standard GTS rules when it is a molecular game, i.e. when ϕ is a complex formula. If ϕ is an atomic formula or an identity, one reaches an atomic game. The original game rule for atomic sentences (R.At) must then be replaced by four new rules (see Appendix A.) First of all, if either ∃loise is the current verifier and the atomic sentence is false, or she is the current falsifier and the sentence is true, then ∀belard wins and ∃loise loses. If it is not the case, then ∀belard chooses one of its non-logical constants, an individual constant a i , a function symbol f j or a relation symbol R k , and the game goes on. 5 When ∀belard chooses an individual constant a i , ∃loise has to pick out an object in the domain; if she has selected the right value, i.e. the very extension of a i , then she wins the play and ∀belard loses. When ∀belard chooses a n-ary function symbol f j , he furthermore picks out a n-tuple of objects in the domain and ∃loise must select an object in the domain: if it is identical to the value of f j for the given tuple then ∃loise wins and ∀belard loses. When ∀belard chooses a n-ary relation symbol R k , he furthermore picks out a n-tuple of objects in the domain and ∃loise must check whether R k applies to this tuple; if ∃loise succeeds, i.e. if she answers "yes" when R k applies to the tuple and "no" when it doesn't, then she wins the play and ∀belard loses.

In eGTS, we thus have new truth and falsity definitions relative to a structure M = D, I :

M + eGTS ϕ (ϕ is eGTS-true in M)
iff there is a winning strategy for the initial verifier (∃loise) in eG(ϕ, M) played according to the eGTS-rules.

M -

eGTS ϕ (ϕ is eGTS-false in M) iff there is a winning strategy for the initial falsifier (∀belard) in eG(ϕ, M) played according to the eGTS-rules.

It is worth noticing that according to the eGTS game rules, only individual objects are handled by the players -i.e., no higher-order entity is involved.

Extending Skolemization to non-logical constants An extended version of skolemization which matches eGTS is straightforwardly definable: not only existentially quantified variables and disjunctions, but now individual constants a i as well as relation symbols R j can be replaced by existentially quantified functions (for simplification I will no longer consider function symbols at the object language level.) In what follows we will consider a simple example -a precise definition is given in an appendix. Let us recall what are the first-and second-order Skolem forms Sk[ϕ] and 2Sk[ϕ]:

ϕ = ∀x∃y R 4 (x, y, a 2 ) Sk[ϕ] = ∀x R 4 (x, f(x), a 2 ) 2Sk[ϕ] = ∃ f ∀x R 4 (x, f (x), a 2 ) (5)
Let's now introduce some new notations. In eSk[ϕ] the non-logical constants are replaced by function symbols: one corresponding to a choice function g for the individual constant a 2 , and another, h, for the indicator function 6 of the relation symbol R 4 ; since we want eSk[ϕ] to be equivalent to Sk[ϕ], the newly introduced symbols are equated with their intended values:

7 eSk[ϕ] = ∀x [h(x, f(x), g) = 1] ∧ [g = a 2 ] ∧ [h = 1 R 4 ] (6)
Then in 2eSk[ϕ] the new function symbols are existentially quantified:

2eSk[ϕ] = ∃g ∃h ∃ f [∀x [h(x, f (x), g) = 1] ∧ [g = a 2 ] ∧ [h = 1 R 4 ]] (7)
6 Here again, one has to assume that the domain contains at least two elements, one of which is denoted by 1. As was suggested by a referee, using relations symbols and predicate variables rather than indicator functions and function symbols would provide much more readable Skolem forms. However, the uniform use of (Skolem-like) functions at a metalinguistic level appears to be consistent with the fact that games are played with no higher-order entities. Incidentally, this uniform treatment would allow us to translate the resulting Σ 1 1 formulas into IF logic in the usual way. 7 Both kinds of functions are linked to choice functions in the strict sense: the individual constant functions g a i could be defined relative to a domain D s.t. g a i (D) ∈ D; the indicator functions for relations h R j completely determine functions h

R j s.t. h R j (D n ) ∈ D n .
Assuming the standard semantics for second-order logic any first-order formula ϕ = Φ(R 1 , . . . , R k , a 1 , . . . , a l , x 1 , . . . , x m ) is equivalent to 2eSk[ϕ]. (For more details, see Appendix B.)

Truth-conditions Prima facie the new game rules do not add any interesting moves to the plays since they say that a play should end in the same manner as was indicated in the original rule (R.At): the verifier wins if the atom is true, while the falsifier wins if it is false. And in fact the following equivalence is trivially inferred from the truth-definitions:

M + eGTS ϕ ⇐⇒ M + GTS ϕ. (8)
However the specific benefits of GTS were not obvious either since it was shown to be equivalent to Tarski-like semantics. Regarding eGTS, relevant differences will appear at the level of the initial verifier's power, since mastering a winning strategy is now a more complex task than it was in standard GTS. The underlying intuition of atomic games is an extra requirement for ∃loise: she must be able to determinate the semantic values of the expressions involved in the assertions she argues for. This is made clear if we are to describe her winning strategies:

A winning strategy for ∃loise in some (unextended) GTS game G(ϕ) is an array of Skolem functions related to each choice to be made by her through the game f ϕ = f 1 ϕ , f 2 ϕ , ...f n ϕ ; correspondingly, a winning strategy for ∃loise in the eGTS game eG(ϕ) is an array

ef ϕ = f 1 ϕ , f 2 ϕ , ...f n ϕ , [f atom ] where [f atom ]
is the set of Skolem functions correlated with the individual constants and relation symbols occurring in ϕ:

[f atom ] = {g a 1 , . . . , g a k , h R 1 , . . . , h R l }.
Considering formula ϕ of example [START_REF] Hintikka | Semantics for Propositional Attitudes[END_REF], its eGTS truth-conditions are given by ( 7) whereas the winning strategies for ∃loise are provided by each interpretation of the function variables f, g and h in [START_REF] Hintikka | Language Understanding and Strategic Meaning[END_REF]. Of course, as long as the players of semantic games are ideal, infinitary and omniscient agents the requirement cannot trigger any fatal issue: the extensional constraint occurring onto the functions of [f atom ] is that their values coincide with those of the interpretation function I of the structure. More accurately, each function h R i ∈ [f atom ] must be extensionally equivalent to 1 R i , so h R i is completely determined by I| {R i } ; and similarly each (constant) function g a j ∈ [f atom ] must be completely determined by I| {a j } . The union of the elements of [f atom ] thus gives exactly the same values as the restriction of the interpretation function I to the non-logical constants involved in ϕ.

The particular insight offered by Skolem functions will then be to provide a new point of view on the interpretation of a language. Whereas I is a static mapping given once and for all, the Skolem functions of [f atom ] are expected to encode the devices used by the initial verifier to reach the semantic values of the language constants. The specific contribution of eGTS will thus be made apparent when some restrictions on the agents' powers are introduced. The situation is analogous to that of (unextended) GTS, which gives rise to a genuine account when imperfect information comes into play. 8,9 3 An Account of Meaning and Interpretation Based on Game Strategies

Meaning: Implemented Skolem functions

Using strategies to refine meaning It has been suggested by van Benthem [START_REF] Van Benthem | The Epistemic Logic of IF Games[END_REF] to use game-semantics in order to account for (hyper)fine-grained meanings: two logically equivalent sentences in FOL can diverge in their syntactic structure so that the corresponding evaluation games require different strategies. It would thus be possible to define the meaning of a sentence ϕ not only as the set of possible worlds where ϕ is true, but as the set of pairs M, ws such that M is a possible world where ϕ is true, and ws is the set of winning strategies for ∃loise in G(ϕ, M).

However, whereas the situation is fine with logical constants and unextended GTS, it is different with non-logical constants and eGTS atomic games: now, every component of the winning strategies should coincide with the interpretation function. Then if two predicates (or individual constants) are coextensive in every possible world, adding their eGTS correlated winning strategies cannot add any distinctive information. So no straightforward refinement of meanings can be expected from these strategies.

How to individuate Skolem functions?

What is required is an intensional characterization of functions. This is the first issue eGTS has to face in order to avoid collapsing into standard GTS. Coextensive functions will be considered distinct whenever they are associated with different processes to determine their values. Of course, the identity conditions of 8 Imperfect information semantic games provide a new logic which has been developed by Hintikka and Sandu since the 1980s, independence-friendly logic (IF logic for short). It is a slight extension of first-order logic equivalent to the Σ 1 1 fragment of second-order logic. 9 Jackson [START_REF] Jackson | On Game-Theoretic Interactions with First-Order Knowledge Bases[END_REF] provides another extension of GTS to atomic formulas in the context of knowledge-base management: new game rules are introduced to check whether the atom in question is a proof-theoretic consequence of the knowledge base under consideration. The theory departs from the model-theoretic ground and admits of indeterminate formulas. Such an account can be seen as an implementation of non-omniscient players, where the initial verifier's knowledge is restricted to the content of the knowledge base.

processes are worth defining, 10 but what is required here is only the possibility of an intensional characterization of functions based on the idea of process, whatever it is.

The idea meets Moschovakis' [START_REF] Moschovakis | Sense and Denotation as Algorithm and Value[END_REF] conception of Fregean sense as an algorithm, which is also elaborated by Muskens in [START_REF] Muskens | Sense and the Computation of Reference[END_REF]. What is specific here is the nature of the functions, which are winning strategies in games. However, we are not committed to sticking to the algorithm or program approach. Skolem functions are what is expected to be at least partially mastered by competent speakers and they can be realized by many distinct devices. We will be concerned with implemented Skolem functions in general -even though I might speak of 'algorithms' in a loose way.

Let us introduce a new symbol for extensional identity -f ≡ g for ∀ x f ( x) = g( x) -and retain the identity symbol for intensional identity between functions, i.e. for identity between implemented functions.The truthconditions of a sentence ϕ would be now expressed by the formula coming from 2eSk[ϕ] after a shift of the identity statements into coextensivity statements, for the Skolem functions correlated with constants ([g i ≡ a i ]) as well as for those linked to relations ([h i ≡ 1 R i ]). Such a requirement is weaker than that of identity of implemented functions. eGTS Meaning Why not simply endorse Musken's theory and get rid of atomic games? But we would then lose the unifying framework of semantic games and of Skolem functions. Several NL semantic theories employ choice and Skolem functions to account for indefinites or anaphoric pronouns ( [START_REF] Reinhart | Quantifier Scope. How labor is Divided Between QR and Choice Functions[END_REF], [START_REF] Winter | Functional Quantification[END_REF]). Schlenker [START_REF] Schlenker | Scopal Independence: A Note on Branching & Island-Escaping Readings of Indefinites & Disjunctions[END_REF] and Clark [START_REF] Clark | Games, Quantifiers and Pronouns[END_REF] even provide explicit connections between choice or Skolem functions uses in NL semantics and GTS. In fact the very idea was already developed by Hintikka with branching quantifiers. The proposal in this paper is then to extend the use of Skolem functions to NL semantics -and of the correlative GTS games -to the vocabulary, i.e. to names and predicates. It entails that Musken's intensionally characterized functions correlated with names and predicates are naturally interpreted as implemented strategies or Skolem functions.

Since in general linguistic expressions E are correlated with many such implemented functions, I will denote by ||E|| the set of implemented Skolem functions associated with E, and I will call it the eGTS meaning of E. For example, if there were two mechanisms (i.e., concrete devices) to identify dogs, the corresponding functions h 1 and h 2 would be elements of ||Dog||. The concept of eGTS meaning so defined is model relative, and it will be used as implicitly relative to the actual world.

Interpretation: Implemented Dig functions

"Strategic Meaning" As was said above, for any FO formula ϕ there is an equivalence between 2eSk[ϕ] and 2Sk[ϕ] and this implies that no specific insight on the truth-conditions can be given by our new (atomic) games. A new perspective obtains if we examine closer what is expected from the initial verifier. Her winning strategies for molecular games are now enriched with functions for the atomic games involved. As was already noticed, there is no change of the conditions for her to have such strategies: there is a winning strategy for ∃loise in the molecular game iff there is a winning strategy for her in the whole (including the atomic) game.

Atomic games are relevant insofar as one wants to know which particular functions are involved in a winning strategy. This is the case when bounded players are assumed to play the semantic games or, better, when some (human, concrete) agent is expected to know something about, or to use part of the winning strategy of one (abstract) player. Roughly said the issue is then no longer to know de dicto whether there is a winning strategy but to know de re which strategy will be a winning one.

Such knowledge is that of what Hintikka [START_REF] Hintikka | Language Understanding and Strategic Meaning[END_REF] labelled 'strategic meaning.' It is involved in semantic analysis when the 'abstract meaning' (i.e., the truth-condition) is no longer enough, such as in cases of ambiguity resolution, or in anaphora resolution. According to Hintikka, many features can play a role in the determination of the winning strategies: contextual data, background knowledge, syntactical clues, etc. Strategic meaning is a free extra offered by GTS, beyond the more usual truth-conditional content. It can sometimes be handled by speakers for the interpretation of particular occurrences of sentences in discourse or conversation. Hence strategic meaning can be considered as belonging to the pragmatic side of language. However, as Hintikka deservedly insists, strategic meaning is just a by-product of a semantic theory and must be considered as such.

Adding one dimension: interpretation

The idea of strategic meaning suggests making a move from meaning constitution to linguistic interpretation (or understanding), not only at the level of complex sentences but also at the level of atomic ones. Meaning constitution is accounted for by semantic games played by the abstract players in a model-theoretic structure. Linguistic interpretation is another type of game: it is concerned with real, limited speakers in concrete contexts. This will lead us to a relativization of the notions of eGTS to contexts and to approximations of Skolem functions. As requiring a total grasp of meaning (hence of extensions) by competent speakers is not realistic, it is necessary to modify the theory developed up to now, and regiment the following three ideas about linguistic knowledge: (i) It is contextual knowledge: there is an elimination of algorithms in the general case; (ii) It is partial knowledge: there is a specific elimination of algorithms relatively to the agent; (iii) It is approximate knowledge: linguistic knowledge might involve functions which are not always winning strategies, i.e. not always Skolem functions.

(i) Contextual knowledge. The ability to determine the extension of expressions in order to understand an utterance is relative to its context. Both the way the context is modeled, and the question why what in the context that counts as important does the job in the interpretation process, are issues that go beyond the purpose of this section. I will rather claim in a very general manner that contexts are expected to play a specific role regarding Skolem functions: contexts should restrict the class of the relevant, hence available, Skolem functions.

Indeed, my claim highlights a role of contexts which is very often emphasized in the literature, namely quantifier domain restriction (see [START_REF] Stanley | On Quantifier Domain Restriction[END_REF] for a general overview.) Semantic theories more specifically employing Skolem functions usually also take contextual restrictions into account. This is the case of Hintikka's [START_REF] Hintikka | Language Understanding and Strategic Meaning[END_REF] conception of strategic meaning according to which the context restricts the set of available winning strategies. Von Heusinger [START_REF] Von Heusinger | Reference and Representation of Pronouns[END_REF] provides a uniform semantic representation for pronouns: "Pronouns are understood as referring to the most salient individual in the context so far, and are represented as indexed epsilon terms that are interpreted by a choice function [which] reconstructs the salience structure of the context." Therefore, the role played by the context in the setting of the relevant choice functions appears to be a pervarsive feature of NL semantic theories involving such functions.

(ii) Partial knowledge. There are in general connections linking the speaker to the individuals and properties she refers to in her utterance. In eGTS, these connections correspond to the Skolem functions of [f atom ]. If such connections are individuated at the level of their implementations, they may become dependent of the context: some algorithm or other is available in such or such a context, but not in another. For instance, as the speaker is an element of the context, complexity considerations can occur and imply some restriction on the available devices. More generally speaking the location of the utterance can play an important role on the selection of a device to determine the extension of an expression. One can ponder over the calculation of the extension of "Water " in a desert h c 1 water which may diverge from the corresponding calculation in a kitchen h c 2 water . For the framework of eGTS, what all this means is that relative to a given context c, there are contextual restrictions ||E|| c on the set of (implemented) winning strategies of the initial verifier ||E|| generally available for a given concrete speaker. Some of these restrictions are due to the location of the speaker, but not necessarily all of them. For some utterances of a sentence, there might be no available Skolem function at all even though the sentence is true in the model -i.e. even though there actually are such functions for the initial verifier of the corresponding semantic game.

(iii) Approximate knowledge. Speakers are far from omniscient. In his wellknown paper [START_REF] Putnam | The Meaning of 'Meaning[END_REF] Putnam argued that a speaker who could not discriminate between "Elms" and "Beeches" might nonetheless be considered a competent English speaker. A fixed amount of approximation is indeed acceptable according to the linguistic community -the exact amount being of course conventionally determined. For instance, a speaker who could not discriminate between "Snowball" and "Tiger " would not be considered competent.

So competent speakers can employ implemented functions (i.e., concrete devices) to determine the extension of predicates that do not necessarily coincide with the interpretation function of the underlying model. Consequently such functions are not necessarily Skolem functions of eGTS, even though some of them can be. I will call these functions Dig functions. They are those strategies used by concrete speakers if they were to calculate the extensions of the predicates and names they employ, sometimes winning, sometimes losing.

eGTS stereotype

The set of Dig functions eventually associated with an expression E by a competent speaker i can thus strongly diverge from the eGTS meaning ||E||: it can come from both a contraction of the set of Skolem functions, and an enlargement to many losing strategies. Following Putnam's ideas let us call this set the stereotype of E for i and denote it by †E † i . As for the corresponding set of Skolem functions, we must use the restriction †E † c i to model the stereotype of an agent i in a context c. Stereotypes are specific to the agents' idiolects. Some of them are acceptable, others not, depending on social conventions. What counts as a socially acceptable stereotype is a matter of empirical research.

We finally reached a two-dimensional account of "meaning" (in a broad sense), eGTS meaning and eGTS stereotype, with no resort to possibleworld semantics. Intensionality intervenes at the level of the individuation of functions, and a second refinement comes from the interpretation level. In the next section, I will give a few applications of the two notions.

Application and Philosophical Consequences

Contrasting meaning and interpretation

Meaning It is now time to consider how eGTS handles concrete cases. Let us consider a simple discourse: A man walks. He kicks Nicolas Its analysis according to GTS is quite standard (see [START_REF] Hintikka | Anaphora and Definite Descriptions: Two Applications of Game-Theoretical Semantics[END_REF], [START_REF] Sandu | On the Theory of Anaphora: Dynamic Predicate Logic vs. Game-Theoretical Semantics[END_REF], [START_REF] Clark | Games, Quantifiers and Pronouns[END_REF]); according to eGTS, the game should go deeper. It is roughly played as follows:

The whole game eG is played relative to a given model M = D, I . It is cut into two subgames, one for each sentence -i.e., eG = eG(S 1 , M); eG(S 2 , M), where S 1 stands for "A man walks", and S 2 for "He kicks Nicolas." In eG(S 1 , M) ∃loise chooses an individual in D for the initial indefinite "A", say b, and puts it in the choice set CS; then the game goes on as eG(b is a man and b walks, M). ∀belard chooses a conjunct, say b is a man, and the game continues as eG(b is a man, M). We have now reached an atomic formula: if it is true, i.e., if ∃loise actually chose a man with b, then ∀belard cannot do anything clever11 but choose the predicate "man", and pick out an arbitrary individual, say b , from the domain D; ∃loise answers yes if b is a man, and no if it isn'ta task she can successfully achieve since she is omniscient. Moving to eG(S 2 , M), ∃loise chooses an individual in the choice set CS to process the anaphoric pronoun "He". So she picks out b, and the game goes on as eG(b kicks Nicolas, M). This is an atomic formula. If it is true, i.e. if the individual chosen by ∃loise in the previous subgame actually kicks Nicolas, then ∀belard chooses one of its two non-logical constants, say Nicolas. ∃loise must then find the bearer of the proper name in D, a job she easily does as an omniscient player.

Assuming that the above discourse is true, there is a winning strategy for ∃loise in eG. What would such a strategy look like? It is a sequence of (sets of) implemented Skolem functions:

f 1 , {h 1 , h 2 }, f 2 , {h 3 , g 1 }
where: f 1 ≡ f 2 pick out a man walking and kicking Nicolas, h 1 ∈ ||Man||, h 2 ∈ ||Walk||, h 3 ∈ ||Kick||, and g 1 ∈ ||Nicolas||. Hence, ∃loise's winning strategies directly rely on the eGTS-meanings of the predicates and proper name. The target array for ∃loise actually is

f 1 , {||Man||, ||Walk||}, f 2 , {||Kick||, ||Nicolas||} .
This array provides a basis to construe the eGTS-meaning of the whole discourse. Such an analysis requires adding specific rules to combine elementary meanings (those occurring in the array) in a more subtle, syntax-sentitive way than it is in a mere sequence. But that would lead us beyond the scope of the present paper.

Interpretation While shifting from meaning to interpretation, contexts of utterance, limitations of the agents and approximation enter the scene. As an immediate consequence, one has to address the issue of what minimal amount of linguistic knowledge is expected to be mastered by any competent speaker.

Let us consider the interpretation of the above discourse by an agent i hearing it: differently from ∃loise, i need not master any winning strategy of the corresponding eGTS game. Her target array looks like

f i 1 , { †Man † i , †Walk † i }, f i 2 , { †Kick † i , †Nicolas † i } .
where ∃loise's implemented functions f 1 and f 2 have been replaced by a couple of others, f i 1 and f i 2 respectively, and the elementary meanings have been changed into the corresponding stereotypes for agent i. Roughly said, i must know that the value produced by f i 2 should be the same as that selected by f i 1 , i.e f i 2 ≡ f i 1 , which corresponds to the understanding of the anaphoric pronoun -but she need not know anything about the function f i 1 itself, except that it should take its values among male human beings. Furthermore, a competent hearer must have some socially acceptable stereotype †Man † i , but nothing is required about "Nicolas", i.e. †Nicolas † i can be empty.

It means that the minimal knowledge required of a competent speaker can vary between logical categories. Of course, an agent can have more than such a minimal knowledge and use strategic meaning to interpret a discourse. In the example, the agent can know the functions' value (i.e., who the man kicking Nicolas is), and her stereotype †Nicolas † i can be a proper part of the corresponding GTS-meaning (i.e., it can involve implemented functions that actually pick out the bearer of the name.)

In the remainder of the subsection I will check three categories, namely proper names, relations, and definite descriptions, and examine what corresponding knowledge competent speakers are supposed to possess.

Names An implemented Skolem function correlated to a name a is a mechanism g a which produces the referent of the name. It represents any mode of identification of its bearer. However, an assertion making use of a proper name can refer to the bearer of the name even though the speaker who utters it does not master any of the corresponding Skolem functions in ||a||. For a competent speaker i to successfully assert: "He kicks Nicolas" -and to successfully refer to Nicolas -it is only required that the truth condition of the statement be realized, namely that the ordered pair made of the individual picked out by he, and of the bearer of the name I(Nicolas), whoever they are, be in the extension I(Kick) of the kicking relation, whatever this extension is. If the speaker has no idea who is the bearer of the name, †Nicolas † i is simply empty. 12 Of course, the knowledge of the bearer of a name would increase one's understanding of the sentence where the name occurs, but it is not required.

The semantics based on Skolem and Dig functions is perfectly compatible with the Kripkean theory of direct reference for proper names -as well as for natural kind predicates and other relation symbols. Whereas the interpretation function I intervenes at the level of meaning constitution, implemented Skolem and Dig functions play an epistemic role: they encode the mode of recognition of the independently given extension of expressions. Hence different speakers knowing the individual that is the bearer of a proper name usually do not share the same Dig functions. The contrast is exactly the one which holds between abstract meaning and strategic meaning.

Predicates (and other relation symbols)

In the actual world, one can have two or more functions to determine the extension of "Elm". This is the main reason why stereotypes were defined as sets of Dig functions. For instance one function will be based on the agent's knowledge and educated ability to recognize species of trees; another one will consist in asking to an expert what this extension is. For sure, these functions are distinct at an implementation level even though they provide the same values.

The functions involved in the stereotype are clearly distinct from intensions. The latter are usually modelled as functions from possible worlds to extensions. By contrast, Dig functions are defined in one (actual) world, with no a priori idea about their applicability in other possible worlds. Nevertheless, Dig functions can model concepts expressed by predicates. Coextensive predicates, such as Creature owning a heart (Hx) and Creature owning a kidney (Kx), will obviously give rise to two distinct sets of implemented Skolem functions (or eGTS meanings) ||H|| and ||K||. Each function is then expected to encode an operating way to produce the extension, i.e. to determine whether any given object belongs to it or not. They can naturally be conceived of as encoding the correlated concepts of Owning a heart and Owning a kidney, which play an essential role in the speaker's ability to produce the extension of the predicates. And of course, this distinction between two coextensive predicates is made with no resort to any possible-world based device.

As was said before, a competent speaker is expected to possess a stereotype composed of Dig functions which yield a socially acceptable approximation of the extension. For instance a speaker i who cannot discriminate between "Elms" and "Beeches", i.e. such that †Elm † i = †Beech † i can nonetheless be considered a competent English speaker although of course, †Elm † Expert ∩ †Beech † Expert = ∅. By contrast, a speaker j who could not discriminate between "Elms" and "Tigers", would not be considered a competent speaker, a minimal requirement being that: †Elm † j ∩ †Tiger † j = ∅. 13 Beyond the minimal requirement of the possession of at least one Dig function, the understanding of a predicate will be more accute if the speaker has several Dig functions, if many of them are Skolem functions, if she can use them successfully in many counterfactual sitations, and so forth.

Definite descriptions

With definite descriptions we are led back to a case similar to non-extended GTS since quantifiers occur in their formalization. However, the interaction between quantifiers and atomic games deserves careful examination.

Considering a sentence such as "The 2009 French president is bald", the description ıxPx ("The 2009 French president") is paraphrased by an existential statement and the whole sentence is formalized as follows:

ϕ : ∃x(Px ∧ ∀y(Py → y = x) ∧ Bx) (9)
Here the GTS truth-conditions rely on the existence of a winning strategy for the initial verifier, i.e. of a constant Skolem function f x = a such that ∃loise yields a winning strategy in any of the three games correlated to the conjuncts:

Pa ∧ ∀y(Py → y = a) ∧ Ba ( 10
)
∃loise has thus to hold two Skolem functions associated with the predicates and coinciding with the interpretation function, h P and h B , so that she is able to win the atomic games Pa and Ba, as well as the game associated with ∀y(Py → y = a). 14 Once again, the existence of a winning strategy for the initial verifier of a semantic game -abstract meaning -is independent from the knowledge of any strategy by the speaker -strategic meaning.

A complete knowledge of the strategy corresponding to the definite description in the aforementioned example involves knowledge of the two functions f x (= a) and h P . However a competent speaker is not expected to master both functions: having a function that enables one to approximately 13 To be more precise in the writing down of the constraints, we should relativize the stereotypes to usual contexts, in order to avoid situations where, e.g., an elm and a tiger were both boiled, ground, then mixed with flour and black ink, so that the agent can no longer distinguish them. This relativization is here left implicit. 14 This subformula is equivalent to ∀y(¬Py∨ y = a), so that ∃loise has a winning strategy if, for any value chosen for y by ∀belard, she can select one of the disjuncts, i.e. either deny P of this value or identify it to a; it is of course assumed that the function h P does not change during the game. Finally, a winning strategy for the initial verifier in the whole game associated with ϕ is a tuple where h P occurs twice -one time for each occurrence of P in ϕ:

f ϕ = f x , {h P }, f ∨ , {h P } , {h B } .
determine the denotation of the description (h P ) -i.e. possessing an acceptable stereotype †P † i -is enough; knowing who the individual fitting the description (f x ) is increases the understanding of the sentence, although not absolutely essential. The case is partly similar to that of proper names. As a definite description involves a combination of predicates and quantified variables, the minimal requirements for a competent speaker follow those of its components: no strategic meaning is required regarding quantifiers, whereas a conventionally determined stereotype is expected to be used in the case of predicates.

Philosophical puzzles

With eGTS meanings and stereotypes, we possess two levers to get solutions to the classical semantic puzzles about informative identities, conceivability of impossibilities, and so forth. In this last subsection, I will briefly survey some of these puzzles.

Informative identities They can be carried using eGTS meanings. For instance, ||Hesperus|| ||Phosphorus|| since the implemented Skolem functions corresponding to each proper name are not the same, even though they are extensionally equivalent: if g H ∈ ||Hesperus|| and g P ∈ ||Phosphorus||, then g H ≡ g P but g H g P .

Skolem and Dig functions can be understood as carrying a part of the Fregean notion of sense: they represent the devices employed respectively by ∃loise and by ordinary speakers to find the extension. Of course, Dig functions are not Frege's senses: they do not determine the extension per se, at the semantic or constitutive level.

The informativeness of the identity is due to the fact that speakers are not expected to know anything about the bearers of the names they employ. Learning an identity is consequently learning a fact about Dig functions and, more basically, about the bearers of the names: learning that Hesperus is identical with Phosphorus leads an agent i to correlate functions g ∈ †Hesperus † i to functions g ∈ †Phosphorus † i : g ≡ g . By contrast, stating that Hesperus is identical with Hesperus doesn't supply any new information.

Rigid designation Going into modal matters and following Kripke, we can consider the proper names "Hesperus" and "Phosphorus" as rigid designators, i.e. as names referring to the same entity in every possible world. How are we then to account for the conceivability of impossible situations where the two names do not refer to the same entity? This puzzle gave rise to several strategies, like two-dimensional semantics or rescourse to impossible worlds. On the present account, the structure of possible worlds itself is left intact with no ad hoc supplementary component, and Skolem (or dig) functions suffice to account for conceivable impossible situations.

Let us consider the two implemented functions mentioned above, g H and g P . As Skolem functions, they can occur in winning strategies for ∃loise in semantic games G(ϕ, M), where ϕ is replaced by sentences involving the proper names "Hesperus" and "Phosphorus", and M is a first-order model corresponding to the actual world. Recall that such functions can diverge in another model N corresponding to another possible world, i.e. g H g P in N, even though the proper names still refer to the same individual in N.

In this respect, Skolem functions behave like Hintikka's world-lines [START_REF] Hintikka | Semantics for Propositional Attitudes[END_REF] or like individual concepts: they link individuals from world to world according to specific viewpoints, and independently from the very nature of the individuals at stake. 15 This is made possible by the general fact that a winning strategy in a game G(ψ, M) need not be winning in the game G(ψ, M ), i.e. in the game correlated to the same sentence but played in another model.

Empty names

Stereotypes and Dig functions provide a nice solution to the usual puzzles since there is now a way to make a difference between two empty names (e.g. Shrek and Pinocchio), and a means to designate entities in other possible worlds. What is required is only to allow Dig functions to be partial, i.e. to be possibly undefined in some possible worlds. Alternatively, it can be postulated that the gaps are filled in with a null individual. There is no prima facie objection to the consideration of two distinct Dig functions, g p for Pinocchio and g s for Shrek, such that they be empty in some worlds and their values coincide in no world in which they are defined: such functions thus account for the meaningfulness of fictional discourse in a natural way.

Synonymy cases

The well-known cases of the ignorance of synonymous predicates and, as a consequence, of the equivalence of sentences involving them, are handled in the present framework in a way similar to that of coreferent proper names: even though their extensions coincide in every possible world, the eGTS meanings for e.g. "Ophthalmologist" (O) and "Eye doctor " (E), which are sets of implemented Skolem functions, do not: ||O|| ||E||; and the corresponding stereotypes of course do not either: †O † †E †. This is enough to account for possible distinctive attitudes towards sentences whose equivalence is due to synonymy. Ralph can believe that George is an eye doctor and simultaneously believe that George is not an ophthalmologist, without being inconsistent: Ralph's first belief involves a device -i.e., an implemented function -from †E † R , whilst the second one involves one from †O † R . Hence the contents of the attitudes are not the same.

Twin-Earth

The present conception enables one to deal with cases like Putnam's Twin-Earth [START_REF] Putnam | The Meaning of 'Meaning[END_REF]. E-Oscar and TE-Oscar, the microphysical twins living on Earth and Twin-Earth, are supposed to share the same (narrow) mental state as they think about "Water ", even though E-Oscar refers to H 2 O whereas TE-Oscar refers to XYZ. It can be assumed that the twins share their stereotypes: †water † E-Oscar = †water † TE-Oscar .

The Dig functions of E-Oscar enable him to determine the extension of "Water " on Earth. They are not necessarily Skolem functions, i.e. functions picking out water in every context, but they do so in terrestrial contexts: it is only their restriction to terrestrial contexts which coincides with that of Skolem functions, i.e. †water † Earth E-Oscar ⊆ ||water|| Earth . Using the same stereotype on Twin-Earth, TE-Oscar will select another type of extension, namely XYZ. So the extensions depend on the environment -it is the assumption -whereas the stereotype is shared by the twins.

Conclusion

I have shown that a slight extension of GTS could yield interesting results for the theory of meaning. This can be done provided that one does not stick to the usual static and extensional conception of functions as mappings but adopts some fine-grained criterion of individuation of functions -namely, one must move at the implementation level. Here, concrete devices must be introduced in order to account for interpretation by limited agents to be contrasted with the semantic games played by unlimited players. Hence after meaning constitution through eGTS comes the step of linguistic understanding, where context, approximation, and other epistemic issues enter the stage.

The conception put forward in this paper can be viewed as an elaboration on Putnam's ideas about meaning. The key is in the strict separation between meaning constitution and language understanding. Putnam appended the notion of stereotype to that of meaning. In our framework, there is a shift from sets of Skolem functions to sets of Dig functions: limited agents are fallible -as they interpret language, they do not automatically grasp functions that yield the appropriate extensions. This is why the devices are not Fregean senses, but rather make up Putnamian stereotypes.

The resulting conception is a non-modal account of meaning and interpretation: Skolem and Dig functions are defined in one single world. The fine-grained individuation of such functions certainly require intensionality, but it is limited to the metalinguistic level. Moreover, the whole conception is based on an informal interpretation of functions as concrete devices which is a long shot from usual possible-world semantics: here competent speakers are not expected to grasp functions defined on sets of possible worlds, let alone two-dimensional functions.

Appendices

A eGTS rules

In eGTS, every FO sentence ϕ evaluated relative to a structure M = D, I is associated to a game eG(ϕ, M). This new game is identical to the game G(ϕ, M) played according to the standard GTS rules when it is a molecular game, i.e. when ϕ is a complex formula. If ϕ is an atomic formula or an identity, one reaches an atomic game. The original game rule for atomic sentences in GTS, (R.At), is replaced by the following specific four rules:

• (R.At * ). In the atomic game eG(α, M), if either ∃loise is the current verifier and α is false in M, or she is the current falsifier and α is true, then ∀belard wins and ∃loise loses; else there are two cases: (i) α is of the form Rt 1 . . . t n , R being a n-ary relation symbol and the t i s being terms: ∀belard picks out an index i ∈ {0, 1, . . . , n}; if i = 0 then the rest of the game is as in eG(R, M), else it is as in eG(t i , M). (ii) α is of the form (t 1 = t 2 ), the t i s being terms: ∀belard picks out an index i ∈ {1, 2}; the rest of the game is as in eG(t i , M). • (R.Term). In the term game eG(t, M), where t is a term, one of the following three cases occurs:

• (R.Rel

(i) t is a new constant previously introduced through the play i.e. not occurring in the original formula; then ∃loise wins and ∀belard loses;

(ii) t is an individual constant; then ∃loise chooses an object d ∈ D; if d = I(t) then ∃loise wins and ∀belard loses; if d I(t) vice versa;

(iii) t is a complex term involving a n-ary function symbol: t = f (t 1 , . . . , t n ); then ∀belard picks out an index i ∈ {0, 1, . . . , n}. If i > 0 then then rest of the game is as in eG(t i , M), and if i = 0 it is as in eG( f, M).

• (R.Fun). In

B Second-order Skolem forms

There is a simple device to yield a result equivalent to extended GTS with no resort to (sub)atomic games, but only to skolemization. In what follows we will assume that the models under consideration contain at least two distinct elements, and that second-order formulas get a standard (full) semantic interpretation. Let:

Φ(a 1 , . . . , a k , R 1 , . . . , R l , x 1 , . . . , x m )

be a first-order sentence, where a 1 , . . . , a k are the k individual constant symbols, R 1 , . . . , R l the l relation symbols, and x 1 , . . . , x m the m variables occurring inside Φ.

Being first-order Φ can be put into prenex normal form:

Q 1 x 1 . . . Q m x m Φ ⊗ (
where {t 1 , . . . , t p } ⊆ {x 1 , . . . , x m } is the subset of the universally quantified variables of Φ ⊗ , t i ⊆ {t 1 , . . . , t p } is the set of the universally quantified variables of Φ ⊗ on which the existentially quantified variable replaced by f i depends, and Φ • results from Φ ⊗ by a mere permutation of its arguments so that the Skolem functions appear first. Now we can replace the relation and individual constant symbols in Φ by secondorder quantified variables. So Φ is equivalent to the following formula: ∃g 1 . . . ∃g k ∃X 1 . . . ∃X l [Φ(g 1 , . . . , g k , X 1 , . . . , X l , x 1 , . . . , x m )

∧[g 1 = a 1 ] ∧ . . . ∧ [g k = a k ] ∧ [X 1 = R 1 ] ∧ . . . ∧ [X l = R l ]] (14)
The same existential generalization can be done within 2Sk[Φ], reaching the following formula: ∃g 1 . . . ∃g k ∃X 1 . . . ∃X l ∃ f 1 . . . ∃ f n ∀t 1 . . . ∀t p [Φ • (g 1 , . . . , g k , X 1 , . . . , X l , f 1 ( t 1 ), . . . , f n ( t n ), t 1 , . . . , t p )

∧[g 1 = a 1 ] ∧ . . . ∧ [g k = a k ] ∧ [X 1 = R 1 ] ∧ . . . ∧ [X l = R l ]] (15)
∧[g 1 = a 1 ] ∧ . . . ∧ [g k = a k ] ∧ [h 1 = 1 R 1 ] ∧ . . . ∧ [h l = 1 R l ]] (16)
A similar first-order skolemization is then given by: eSk[Φ] = ∀t 1 . . . ∀t p [Φ (g 1 , . . . , g k , h 1 , . . . , h l , f 1 ( t 1 ), . . . , f n ( t n ), t 1 , . . . , t p )

∧[g 1 = a 1 ] ∧ . . . ∧ [g k = a k ] ∧ [h 1 = 1 R 1 ] ∧ . . . ∧ [h l = 1 R l ]] (17)

  ). In the relation game eG(R, M), where R is a n-ary relation symbol, ∀belard chooses a n-tuple d 1 , . . . , d n ∈ D n , and ∃loise answers yes or no. If she answers yes and d 1 , . . . , d n ∈ I(R), or she answers no and d 1 , . . . , d n I(R) then ∃loise wins and ∀belard loses; else ∀belard wins and ∃loise loses.

  the function game eG( f, M), f being a n-ary function symbol, ∀belard chooses a n-tuple d 1 , . . . , d n ∈ D n , then ∃loise chooses an object d ∈ D. If d = I( f )(d 1 , . . . , d n ) then ∃loise wins and ∀belard loses; else vice versa.

  a 1 , . . . , a k , R 1 , . . . , R l , x 1 , . . . , x m )[START_REF] Muskens | Sense and the Computation of Reference[END_REF] with Q i ∈ {∃, ∀}. Φ can also be skolemized, and is equivalent to:2Sk[Φ] = ∃ f 1 . . . ∃ f n ∀t 1 . . . ∀t p Φ • (a 1 , . . . , a k , R 1 , . . . , R l , f 1 ( t 1 ), . . . , f n ( t n ),t 1 , . . . , t p )

  Furthermore, let us change each relation variable X i into a corresponding (indicator) function variable h i and correlatively modify Φ • into Φ -so that each token of X i t 1 . . . t n i be replaced by one of h i (t 1 . . .t n i ) = 1.Hence Φ is equivalent to its extended second-order Skolem form:2eSk[Φ] 1 = ∃g 1 . . . ∃g k ∃h 1 . . . ∃h l ∃ f 1 . . . ∃ f n ∀t 1 . . . ∀t p [Φ (g 1 , . . . , g k , h 1 , . . . , h l , f 1 (t1 ), . . . , f n ( t n ), t 1 , . . . , t p )

Like Fodor's [4] narrow content. See[START_REF] Rebuschi | Contenu étroit, mécanisme et fonctions de choix[END_REF] for an elaboration of the connexion between narrow content and the conception developed in the present paper.

Of course, starting with a given FO formula there is no unicity in the upshot in the general case since several prenex normal forms can sometimes be available. This is the case with ∃xAx → ∃yBy which leads us to two prenex forms, ∀x∃y(Ax → By) and ∃y∀x(Ax → By), thus to two distinct skolemizations: respectively ∀x(¬Ax ∨ Bf(x)) and ∀x(¬Ax ∨ Ba), where a is a constant (function) symbol.

Such an extension is actually suggested by Hintikka himself, see[7, p.

51]. However, this suggestion is essentially connected with applications in first-order epistemic logic, and no extended version of GTS is provided. Already in 1985 Hintikka and Kulas[START_REF] Hintikka | Anaphora and Definite Descriptions: Two Applications of Game-Theoretical Semantics[END_REF] argued that game rules must be associated with NL individual constants.[START_REF] Hintikka | Semantics for Propositional Attitudes[END_REF] When an atomic game is reached there is no residual individual variable in the formula: as eGTS games are played for sentences only, every variable is bound and next replaced by a new constant during the molecular game. GTS could of course be defined for open formulas with a slight complication -games relative to a formula, a model and an assignement. However it is not necessary for the objectives of this paper.

And this is not an easy task, see[START_REF] Blass | When Are Two Algorithms the Same?[END_REF].

Strictly speaking, ∀belard could also choose the individual constant b and lose immediately.

If the reader doesn't share my intuition, successful reference is more obvious in cases such as the speaker's assertion: "I do not know who Nicolas is".

This means that in a standard Kripkean structure, the accessibility relation between possible worlds is doubled over by world-lines between entities. However, Hintikka does not agree with such a combination of his own ideas with that of rigid designation.

Acknowledgements. Previous and partial versions of this work were presented on several occasions during the past years -notably at APLI 2006 (Rijeka, Croatia), at JSM 2007 (Paris, France), and at the Universidade Nova de Lisboa (2008). I wish to thank Denis Bonnay, Paul Egré, Bertram Kienzle, Paul Gochet, Helge Rückert, Anna Sierszulska, and Tero Tulenheimo for their comments on earlier versions of this paper and for many fruitful discussions. All errors remain mine.


Jan Gorisch

Laurent Prévot

AUDIO SYNCHRONISATION WITH A TUNNEL MATRIX FOR TIME SERIES AND DYNAMIC PROGRAMMING

Keywords: Audio-video Synchronisation, Imageloss Compensation, Tunnel Matrix, Tunnel DP-algorithm, Storage Requirements

. However, the overall space of the distance matrix remains identical. Here, a tunnel matrix and its according DP-algorithm are presented. The matrix contains merely the computed distance of two signals to a pre-specified bandwidth and the computational cost is equally reduced. An example implementation demonstrates the functionality on artificial data and on data from real audio and video recordings.

INTRODUCTION

The number of studies that analyse audio and video signals has increased with the attempt to account for the multimodality of social interaction involving amongst others speech and gestures [START_REF] Stivers | Stance, alignment, and affiliation during storytelling: When nodding is a token of affiliation[END_REF][START_REF] Norris | Analyzing Multimodal Interaction: A Methodological Framework[END_REF] and investigations into the natural habitat of speech: face-to-face interaction. Although conversation analysts often have to restrain themselves to low quality audio and video recordings in order to preserve the naturaleness of talk-in-interaction [START_REF] Hutchby | Conversation Analysis[END_REF], studies in interactional phonetics [START_REF] Local | Phonetic detail and the organisation of talk-in-interaction[END_REF] that combine qualitative and quantitative methods by applying computation techniques on automatically extracted features, e.g. Kurtic et al. [START_REF] Kurtic | Resources for turn competition in overlapping talk[END_REF] Gorisch et al. [START_REF] Gorisch | Pitch contour matching and interactional alignment across turns: an acoustic investigation[END_REF] and Bertrand et al. [START_REF] Bertrand | Backchannels revisited from a multimodal perspective[END_REF], require high quality audio recordings from closespeaking microphones. The audio has to be synchronised Thanks to the ANR funding the project "Conversational Feedback" (grant number ANR-12-JCJC-JSH2-006-01). This research was supported in part by the Erasmus Mundus Action 2 program MULTI of the European Union, grant agreement number 2010-5094-7. Comments from Stéphane Rauzy were very much appreciated.

with the video recordings, if the multimodality of talk should be analysed for the same data. Usually, precautions are taken to ensure high standards for audio-video synchronisation, such as by Edlund et al. [START_REF] Edlund | Spontal: A Swedish spontaneous dialogue corpus[END_REF] who enhanced their recording setup and included a rotating turntable with an LP-disk that was scratched at a certain place and a visible marker. Audio and video signals were then synchronised in subsequent steps in order to render the data analysable. The analysis of desynchronised audio and video signals, however, is almost impossible. One source of error can be a clocking difference of two recording devices that capture the same scene. Another source of error can be the hardware equipment itself. For example, video recordings or capturing systems that imply MiniDV technology regularly introduce errors, i.e. a loss or surplus of image frames. Both problems were encountered with recordings of a multimodal speech corpus [START_REF] Gorisch | Aix Map Task corpus: the French multimodal corpus of task-oriented dialogue[END_REF]. Previously, such problems have been tackled by inserting or deleting frames at specific places by hand, as was performed for the CID corpus [START_REF] Bertrand | Le CID -Corpus of Interactional Data -Annotation et exploitation multimodale de parole conversationnelle[END_REF]. A more efficient and re-usable solution that does not have to involve additional equipment, such as turntables, was envisaged for the alignment of the signals, as e.g. of the audiovisual MapTask corpus [START_REF] Gorisch | Aix Map Task corpus: the French multimodal corpus of task-oriented dialogue[END_REF].

APPROACH

The advantage of video recordings is that the camera usually includes an audio channel that captures the same scene as the separate audio recordings do. It means that two similar signals of the same quality, i.e. acoustics, exist for the computation of their alignment. Thus, the aim for synchronising audio and video is to insert or delete images from the video according to the alignment of the audio signals that stem from two different devices.

Dynamic Programming (DP) and Dynamic Time Warping (DTW) are methods that can be applied here, as they are used to align time series in an optimal way. They allow to determine where one signal has to be stretched in time or shrunk in time in order to match the other signal [START_REF] Rabiner | Fundamentals of Speech Recognition[END_REF]. These methods had their revival in speech processing in recent years, e.g. with algorithms that search for re-occurring acoustic patterns for modelling infant speech acquisition [START_REF] Aimetti | A Computational Model of Early Language Acquisition: A Data-driven Approach Inspired by the Empiricist View of Cognitive Development[END_REF] and algorithms that evaluate the similarity in prosodic patterns of conversa-tional participants performing basic social actions [START_REF] Gorisch | Matching across Turns in Talk-in-Interaction: The Role of Prosody and Gesture[END_REF]. Developments have been performed by Salvador and Chan [START_REF] Salvador | FastDTW: Toward accurate dynamic time warping in linear time and space[END_REF] who increased the time efficiency of DTW algorithms. They solved a similar problem by matching two acoustic signals in order to synchronise them with a video signal. However, a problem of limited space and computational cost remains unsolved.

Space and computational cost problem of DP

Many DP problems today take large time series as underlying data. For example, an attempt to align audio recordings of the length of half an hour (1,800s), even using a relatively sparse sampling rate of 25 samples/s (as standard video frames), results in a distance-or similarity matrix of (25 × 1, 800) 2 , that are 2,025,000,000 value pairs. Additional to the space requirements of this matrix comes the computational cost of dynamic programming to evaluate the best alignment path of the two underlying vectors. The Sakoe Chiba Band [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF] or the Itakura Parallelogram [START_REF] Itakura | Minimum prediction residual principle applied to speech recognition[END_REF] are techniques that can help to reduce that computation by limiting the search space to a band around the diagonal of that matrix from the start point to the end point of the underlying vectors.

One problem of current matrix processing is the limited storage space that is available on e.g. personal computers. Sometimes, it is physically not possible to create the distance matrix for two time series. Fortunately, this is even not necessary because the majority of values are not required in the case for the audio-out-of-sync problem. If the DP algorithm that is supposed to be applied to such data is not required to look at the edges of the distance matrix, that space is used without need. A sparse matrix, as introduced by Gilbert et al. (1992) [START_REF] Gilbert | Sparse matrices in matlab: Design and implementation[END_REF], could be used in order to implement such a band. However, DP has not been demonstrated on sparse matrices, yet. In order to save space and computation power to solve the desynchronisation problem at hand, a new structure for the values of the distance matrix is suggested in section 3.

Conceptual and aesthetic problem

A more conceptual and probably aesthetic problem of a rectangular distance matrix (1) is the distribution of the axes. (1) While one time series evolves along the x-axis and the other time series evolves along the y-axis, the overall time evolves along the diagonal. This is traditionally visualised with two vectors, e.g. a = a 1 a 2 . . . a 7 and b = b 1 b 2 . . . b 9 that combine in a distance matrix as shown in [START_REF] Stivers | Stance, alignment, and affiliation during storytelling: When nodding is a token of affiliation[END_REF] with time elapsing for a top-down, for b left-right and for overall time from topleft to bottom-right. From a conceptual point of view where time elapses from left to right, or from top to bottom, the traditional matrices, as they are produced by Matlab R or R, are not optimal in this sense. Both, the reduction of the search space and the orientation of the time axis can be realised by introducing a tunnel matrix that represents the Sakoe Chiba Band (shaded area in (1)) rotated by 45 degrees to the left for horizontal or to the right for vertical propagation of time. This paper proposes an implementation of such a distance matrix in tunnel form at the initialisation stage, i.e. already before the calculation of the alignment path.

a 1 b 1 a 1 b 2 a 1 b 3 a 1 b 4 a 1 b 5 a 1 b 6 a 1 b 7 a 1 b 8 a 1 b 9 a 2 b 1 a 2 b 2 a 2 b 3 a 2 b 4 a 2 b 5 a 2 b 6 a 2 b 7 a 2 b 8 a 2 b 9 a 3 b 1 a 3 b 2 a 3 b 3 a 3 b 4 a 3 b 5 a 3 b 6 a 3 b 7 a 3 b 8 a 3 b 9 a 4 b 1 a 4 b

IMPLEMENTATION OF A TUNNEL MATRIX

The aim is to rotate the Sakoe Chiba Band from a traditional distance matrix around the diagonal by -45 degrees in order to let time elapse from left to right. As can be seen in ( 1), the diagonal contains the isochronous pairs a 1 b 1 , a 2 b 2 , ... a 7 b 7 . This should be the mid row of the new matrix. It can also be seen that the values of a are constant for each column of and increase from row to row. For b it is the inverse: the values are constant for each row and increase from column to column. In order to illustrate the new tunnel arrangement, two intermediate matrices are prepared. For all values of a and b that fall into the bandwidth of the Sakoe Chiba Band, a 'tunnel A' (2) and a 'tunnel B' (3) is created.

NA NA a 1 a 2 a 3 a 4 a 5 a 6 a 7 NA a 1 a 2 a 3 a 4 a 5 a 6 a 7 NA a 1 a 2 a 3 a 4 a 5 a 6 a 7 NA NA a 1 a 2 a 3 a 4 a 5 a 6 a 7 NA NA a 1 a 2 a 3 a 4 a 5 a 6 a 7 NA NA This translates into the new tunnel matrix, however it has to be adapted depending where in the matrix the algorithm is currently working. The principle is the same: it is merely possible to continue in both vectors or to stay at the same value in one vector while proceeding in the other. In the mid row of the tunnel matrix, imagine to start at a 1 b 1 in (5), the steps indicated by arrows are possible. In the top half of the matrix (imagine the prior step went from a 1 b 1 to a 1 b 2 ), one arrow points into a different direction. That means the possible steps are different. In the bottom half of the matrix (imagine the prior step went from a 1 b 1 to a 2 b 1 ), again, arrows point in different directions.

NA

NA

a 1 b 3 a 2 b 4 a 3 b 5 • • • NA a 1 b 2 a 2 b 3 a 3 b 4 a 4 b 5 • • • a 1 b 1 a 2 b 2 a 3 b 3 a 4 b 4 a 5 b 5 • • • NA a 2 b 1 a 3 b 2 a 4 b 3 a 5 b 4 • • • NA NA a 3 b 1 a 4 b 2 a 5 b 3 • • • (5)
In order to find the path through the whole Similarity Matrix with the highest quality (inverse of cost), DP accumulates for each point of the matrix the maximum quality path up to that point in a Quality Matrix. Therefore, at each point of that matrix, the previously accumulated quality is added to the current similarity. The direction from where the lowest cost path came from is memorised in order to find the way back, once the whole matrix has been passed. The algorithm for filling the Quality Matrix according to the similarity matrix is again different from the traditional procedure. It is not possible to proceed row wise and column wise from one corner of the matrix (formerly the start point) to the opposite corner (formerly the end point), even if the step-patterns are clear for each point. Because the DP algorithm always looks backwards from the current point in order to evaluate the highest quality path and accumulates in the current point the new quality-to-this-point, all possible points from where the path can come from need already be evaluated. If they are not, the new evaluation would be based on both, points that include the accumulated similarities (the quality) and points that have stored the mere individual similarity. This would bias the de-cision in favour of the latter. A solution is suggested in the following section.

Quality Tunnel Matrix and Backtrack Matrix

A Quality Matrix Q stores the accumulated similarities. A Backtrack Matrix φ stores at each point the direction from where the path with the highest quality came from. In a first step, Q is filled with the values of the similarity matrix SM and surrounded on top, bottom and left column, by a line of NAs (Not Applicable). This border is necessary in order to have initial values to be compared with. Once the DP algorithm has finished, the end point of that matrix contains the overall quality for the alignment of the two vectors a and b.

The algorithm iterates over the columns via j and over the rows via i. Q(i, j) is the point in the Quality Matrix for which the accumulated quality is to be calculated, i.e. the maximum quality that accumulates until that point. As mentioned above, it is important that each time a potentially proceeding path is evaluated for the maximum quality, the values are either part of the border, or already filled. Therefore, a specific evaluation pattern is established.

An overall trend from left to right is used in order to reach from the start in the first column to the end in the last column. The rows are divided into three parts. The first part is the top half of the matrix, the second part is the bottom part of the matrix and the third part is the mid row. The rows of the top and bottom part are evaluated from the outside to the middle. For the top part [START_REF] Gorisch | Pitch contour matching and interactional alignment across turns: an acoustic investigation[END_REF], it means that i increases from 2 to the middle -1 (row above the mid). For the bottom part [START_REF] Bertrand | Backchannels revisited from a multimodal perspective[END_REF], it means that i decreases from the end -1 (previous last row) to the middle + 1 (row below the mid). At the last iteration per column, the value of the mid row is evaluated [START_REF] Edlund | Spontal: A Swedish spontaneous dialogue corpus[END_REF].

The following comparisons are performed for the three parts at each point Q(i, j). NAs (Not Appliccable) are inserted in the diagrams in order to keep the indexing function for the backtrack path constant: The horizontal step is always 1, the vertical steps are always 3 (top) and 5 (down), and the diagonal steps are always 2 and 4. The lowest value is added to the current point Q(i, j). The direction from where this highest quality path came from is added to the Backtrack Matrix at point φ(i, j). Arrows with solid lines indicate valid steps; arrows with dashed lines indicate invalid steps. The top half of the matrix (row 2 to mid -1) evaluates

Q(i, j) = max(Q(i, j -1) + 2 × SM (i, j), NA, Q(i -1, j) + SM (i, j), Q(i + 1, j -1) + SM (i, j), NA). NA Q(i -1, j) + SM (i, j) Q(i, j -1) + 2 × SM (i, j) Q(i, j) Q(i + 1, j -1) + SM (i, j) NA 1 2 3 4 5 (6)
The bottom half of the matrix (row end -1 to mid + 1): Q(i, j) = max(Q(i, j -1) + 2 × SM (i, j), Q(i -1, j -1) + SM (i, j), NA, NA, Q(i + 1, j) + SM (i, j)).

Q(i -1, j -1) + SM (i, j) NA

Q(i, j -1) + 2 × SM (i, j) Q(i, j) NA Q(i + 1, j) + SM (i, j) 1 2 3 4 5 (7)
The mid row of the matrix is analysed last per column iteration and evaluates:

Q(i, j) = max(Q(i, j -1) + 2 × SM (i, j), NA, Q(i -1, j) + SM (i, j), NA, Q(i + 1, j) + SM (i, j)). NA Q(i -1, j) + SM (i, j) Q(i, j -1) + 2 × SM (i, j) Q(i, j) NA Q(i + 1, j) + SM (i, j) 1 2 3 4 5 (8)

EVALUATION

The new tunnel DP-algorithm applied to the tunnel matrix structure is evaluated on both artificial data and real data from recordings. The artificial data (invented for demonstration purposes) contains a matrix of values between 0.1 and 0.9 that are represented on a grey scale (left of Figure 1). The DP-algorithm found an optimal alignment path (white line) by accumulating similarity scores in a quality matrix (right of Figure 1). The path through the regions of relatively high similarity demonstrates that the algorithm works well on artificial data. Similar results are achieved on real data from the MapTask corpus [START_REF] Gorisch | Aix Map Task corpus: the French multimodal corpus of task-oriented dialogue[END_REF] (using spectral information) from recordings from devices with clock differences and random image loss (Figure 2). It can be seen that after approximately 4000 frames (25/s), one signal is approximately 27 frames behind, or the other ahead respectively. The Tunnel Matrix and the Tunnel DP-algorithm achieve alignment paths (as output) that follow high similarity regions as expected. The path can be used in order to align faulty video streams to intact audio because the areas of image loss or surplus are well indicated. This method was successfully used to synchronise 90% of the recordings. The remaining 10% could not be recovered yet, as entire minutes of the video are lacking.

DISCUSSION

Matlab allows to indicate which parts of a matrix do not need to be stored in a "sparse" matrix [START_REF] Gilbert | Sparse matrices in matlab: Design and implementation[END_REF], i.e. areas of numbers that are zero. However, DP on such sparse matrices has not been demonstrated yet. It means that the proposed architecture for optimised use of space is still lacking in programming languages such as Matlab. Even the function spdiags() does not achieve this. A functioning workaround is demonstrated here that applies a tunnel matrix with the according DP algorithm for synchronising audio signals. There are limitations, as for example gaps of the video spanning several minutes, that increase again the space requirements drastically. But as long as the errors in the signal remain within reasonable limits (the range of several seconds), the algorithm can calculate an output (an alignment path) that can be used subsequently to align the video, e.g. by calling FFmpeg (http://ffmpeg.org) to copy or delete frames.

IMPLICATIONS AND APPLICATIONS

Hardware failure of recording equipment is besides human failure a source for frustration and cost explosion for data repair. Previous work with the aim to prevent this has introduced even more hardware [START_REF] Edlund | Spontal: A Swedish spontaneous dialogue corpus[END_REF] that can also fail and that decreases the naturalness of social interaction additionally to the recording situation itself. Data that was recorded with less precautions should still be made available at a maximum possible quality. One further step into this direction is achieved with the technique suggested in this paper. This DP-technique can also be applied in fundamental research that investigates the similarity of interacting participants on multiple parameters: acoustic-prosodic features investigating social alignment on a turn-by-turn basis [START_REF] Gorisch | Pitch contour matching and interactional alignment across turns: an acoustic investigation[END_REF] or on a larger time-scale as in entrainment [START_REF] Heldner | Pitch similarity in the vecinity of backchannels[END_REF] or convergence [START_REF] Kousidis | Towards measuring continuous acoustic feature convergence in unconstrained spoken dialogues[END_REF], EEG and EMA signals or simple re-occurring patterns in the acoustics [START_REF] Aimetti | Discovering an optimal set of minimally contrasting acoustic speech units: a point of focus for whole-word pattern matching[END_REF].

2 a 4

 4 b 3 a 4 b 4 a 4 b 5 a 4 b 6 a 4 b 7 a 4 b 8 a 4 b 9 a 5 b 1 a 5 b 2 a 5 b 3 a 5 b 4 a 5 b 5 a 5 b 6 a 5 b 7 a 5 b 8 a 5 b 9 a 6 b 1 a 6 b 2 a 6 b 3 a 6 b 4 a 6 b 5 a 6 b 6 a 6 b 7 a 6 b 8 a 6 b 9 a 7 b 1 a 7 b 2 a 7 b 3 a 7 b 4 a 7 b 5 a 7 b 6 a 7 b 7 a 7 b 8 a 7 b 9

( 2 ) 9 ( 3 )

 293 b 1 b 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 NA NA b 1 b 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 NA NA b 1 b 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 NA NA NA b 1 b 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 NA NA NA b 1 b 2 b 3 b 4 b 5 b 6 b 7 b 8 b For illustration purposes, a width of three values in each dimension was chosen. Both intermediate matrices are then merged in order to create the final AB Tunnel Matrix by crossmultiplying 'tunnel A' and 'tunnel B', as shown in (4). Note that these values represent here similarity instead of distance. NA NA a 1 b 3 a 2 b 4 a 3 b 5 a 4 b 6 a 5 b 7 a 6 b 8 a 7 b 9 NA a 1 b 2 a 2 b 3 a 3 b 4 a 4 b 5 a 5 b 6 a 6 b 7 a 7 b 8 NA a 1 b 1 a 2 b 2 a 3 b 3 a 4 b 4 a 5 b 5 a 6 b 6 a 7 b 7 NA NA NA a 2 b 1 a 3 b 2 a 4 b 3 a 5 b 4 a 6 b 5 a 7 b 6 NA NA NA NA a 3 b 1 a 4 b 2 a 5 b 3 a 6 b 4 a 7 b 5 NA NA (4) 4. THE TUNNEL DP-ALGORITHM For the newly created similarity matrix, the traditional DP algorithms are inappropriate. The start point (a 1 b 1 ) and the end point (a 7 b 9 ) are no more at the same location. And therefore, the possible directions that an alignment path might take are also different. For a traditional similarity matrix, the most common step-pattern is from a 1 b 1 to a 2 b 2 without insertion or deletion, to a 1 b 2 by insertion in a or to a 2 b 1 by insertion in b (or deletion from a).

Fig. 1 .

 1 Fig. 1. Evaluation of the new DP algorithm on artificial data. Similarity Tunnel Matrix left, Quality Tunnel Matrix right.

Fig. 2 .

 2 Fig. 2. Evaluation of the new DP algorithm on real data. Similarity Tunnel Matrix left, Quality Tunnel Matrix right.


Laurent Prévot
email: laurent.prevot@lpl-aix.fr

Roxane Bertrand
email: roxane.bertrand@lpl-aix.fr

CoFee -Toward a multidimensional analysis of conversational feedback, the case of French language

Keywords: Feedback, Backchannel, Semantics, Pragmatics, French Language

Conversational feedback is mostly performed through short utterances such as yeah, mhmm, okay not produced by the main speaker but by one of the other participants of a conversation. Such utterances are among the most frequent in conversational data. They also have been described in psycho-linguistic models of communication as a crucial communicative tool for achieving coordination or alignment in dialogue. The newly funded project described in this paper addresses this issue from a linguistic viewpoint by combining fine-grained corpus linguistic analyses of semi-controlled data with formal and statistical modeling. The impoverished aspect of the linguistic material present in these utterances allows for a truly multidimensional analysis that can explain how different linguistic domains combine to convey meaning and achieve communicative goals.

Objectives

The general objective of the CoFee1 project is to propose a fine grained model of the form/function relationship concerning feedback behaviors in conversation. To succeed, we need to achieve:

• a fine-grained analysis of the different dimensions involved (prosody, lexical markers, acoustic nonverbal signals, facial expressions, head movements, gaze) ;

• a fine-grained analysis of the communicative functions related to feedback ;

• a rich characterization of two crucial contextual parameters: discourse context and production context ;

• the integration of these ingredients into a general model. We consider that the truly multi-dimensional nature of the analysis proposed is an important and ambitious step for linguistic studies. Most of existing related work either focus on one domain and marginally integrates the other dimensions or constitutes a very shallow surfacebased analysis grounded on a few features. Moreover, the integration of different situations of communication in such a precise study is also new and will allow to account for communicative situation variability from a more theoretical and experimental approach than what is done usually.

The present paper is structured as follow. We will start by better defining the object of our study feedback items in section 2. Then we will discuss some related work (Section 3) before presenting with some details of the data (Section 4) as well as the analysis and the modeling planned (Section 5). Finally we will briefly describe the current work and what will be presented at the workshop.

Definitions

CoFee is a study of the positive feedback items. This section is a clarification attempt, at least for the sake of the project.

• Feedback: In dialogue or conversation context, it can be associated with any evaluative communicative action about previously introduced material.

• Backchannel: Intuitively, backchannels are productions made by the participant holding the listener role.

• Acknowledgment: A positive feedback. Polarity is functional here since negative items can have a positive evaluation function.

Backchannels vs. acknowledgments

Acknowledgements and backchannels have sometimes been used as synonyms. Although these phenomena are frequently co-occurring, they constitute different aspects of verbal interaction. The term back-channel was introduced by [START_REF] Yngve | On getting a word in edgewise[END_REF] and included a broad range of linguistic phenomena such as questions and short comments. The notion was broaden later to include other items such as verbalized signals, sentence completions, brief restatements, clarification requests,... Almost any communicative event can be a backchannel. Indeed, backchannels are sometimes described as production by the listener moving the definition issue to the speaker / listener definitions. This is however not as straightforward as it seems to be since listeners are commonly said to produce signals in the course of the communication. While [START_REF] Sacks | A simplest systematics for the organisation of turn-taking for conversation[END_REF] argues that participants tend to not overlap the production of their interlocutors thanks to an efficient turn-taking rule system, [START_REF] Ward | Prosodic features which cue back-channel responses in english and japanese[END_REF] shows that even if the turn-taking system is efficient it is not rare that participants speech overlaps.

Speaker/Listener distinction, and therefore backchannel definition combine both form and content issues. A participant that is not willing to take the turn should not produce utterances signaling his willingness to do so. Backchannels are typically briefs, low in intensity and may exhibit specific prosodic contours. Moreover, even if the listener desires to take the initiative, social rules (politeness) are forcing him to conform to turn-taking rules and therefore remain more or less in his listener role until the speaker yields the turn. At the content level, many productions can be back-channeled and only a few communicative acts (such as questions) tend to switch systematically the speaker/listener role.

Traditionally backchannels are divided between continuers and assessments [START_REF] Schegloff | Discourse as an interactional achievement: Some use of" uh-huh" and other things that come between sentences[END_REF]. Tottie [START_REF] Tottie | Conversational style in british and american english: The case of backchannels[END_REF] gives continuers a regulative function and assessments a supportive function. The former regulates the coming contribution of the interlocutor while the later bring a supportive reaction to a previous contribution. Feedback is more clearly associated with the later but it is difficult to systematically distinguish them and therefore most of the empirical studies are proposing to work on the phenomena as a whole.

Backchannels feedback

The difficulties mentioned above lead [START_REF] Ward | Prosodic features which cue back-channel responses in english and japanese[END_REF] to propose a back-channel feedback notion. Back-channel feedback:

• (i) respond directly to the content of an utterance of the other participant

• (ii) is optional • (iii)
does not require acknowledgment by the other participant.

However, these criteria concern only back-channelled feedback, not those occurring as part of a turn. Such feedback is rather common, specifically in task-oriented dialogues that require a detailed grounding of the information transmitted.

Sum-up

To sum-up, in COFEE we are examining positive feedback behaviors (mainly verbal behavior but also laughter and other communicative grunts [START_REF] Ward | Non-lexical conversational sounds in American English[END_REF]). Most of them are also back-channels but we do not exclude feedback items that are not back-channeled. The later may be taken as an answer to a question but it is still optional, contrarily to answers. Based on earlier studies on French feedback [START_REF] Muller | An empirical study of acknowledgement structures[END_REF][START_REF] Bertrand | Backchannels revisited from a multimodal perspective[END_REF], the list of lexical items we are including in our study is : oui (yes), ouais (yeah), mhmm, ok, d'accord (right), voilà (that's it), c'est c ¸a (that's it), ah, bon (well).

Related work

Among the more recent works, [START_REF] Gravano | Affirmative cue words in task-oriented dialogue[END_REF] proposed a broad study of the form/function relation for feedback. They use various features including acoustic and discourse ones. However "discourse" features are more shallow than the one we are planning to use (basically based on size of Inter Pausal Units -IPU-and of position of the item in the IPU). Moreover, we are also planning a more linguistic way for extracting the speech parameters than purely acoustic measurements. However, we will attempt to replicate many aspects of their study on our French corpora. [START_REF] Bunt | Multifunctionality in dialogue[END_REF][START_REF] Petukhova | Towards an integrated scheme for semantic annotation of multimodal dialogue data[END_REF] have a multi-dimensional model of communicative functions dealing with feedback behaviors. Here the modeling framework is very rich but as in Gravano and colleagues study the discourse and linguistic features used are very shallow since the goal was not to focus on feedback but on the identification of all communicative functions.

Formal semantics and pragmatics until recently remained away from feedback behaviors. Fortunately, in the recent years this field started to look more carefully at this issue. This movement can be traced back to [START_REF] Allwood | On the semantics and pragmatics of linguistic feedback[END_REF] for at least a plea for a move in this direction. More complete framework allowing to work on feedback mechanisms in formal pragmatics are presented in [START_REF] Lascarides | Grounding and correcting commitments in dialogue[END_REF] or [START_REF] Ginzburg | The Interactive Stance: Meaning for Conversation[END_REF].

Data and annotations

Corpora

Three corpora will be used in the course of the project:

• The Corpus of Interactional Data (CID) recorded by Roxane Bertrand and Béatrice Priego-Valverde [START_REF] Blache | Creating and exploiting multimodal annotated corpora: the toma project[END_REF] is a 8 hours (110K tokens) corpus composed of 8 conversations of 1 hour. It features a nearly free conversational style with only a single theme proposed to the participants at the beginning of the experiment. This corpus is fully transcribed and forced-aligned at phone level with signal. Moreover, it has been annotated with various linguistic information (Prosodic Phrasing, Discourse units, Syntactic tags,...) during the OTIM project [START_REF] Blache | Creating and exploiting multimodal annotated corpora: the toma project[END_REF]. (Visible at sldr.org/sldr000720/en)

• A 3h30 French MapTask created by Corine Astésano and Ellen Bard [START_REF] Astésano | Structural influences on initial accent placement in french[END_REF]. It has been recorded according to the original MapTask methodology. This corpus has been transcribed and aligned manually at utterance level. We are now planning an automatic phone alignment with the same methodology used in the previous project. (Visible at Visible at sldr.org/sldr000732/en)

• A French Negotiation Game Corpus that is currently under construction and that consist in negotiations games played by four participants. We are targeting a bigger corpus than the two others but not fully transcribed. We plan to transcribe only speech neighbouring feedback items which are less frequent in this setting than in the two previous ones.

(Preview visible at sldr.org/sldr000773/en) These three corpora constitute very different communicative situations and therefore cover an interesting range of functions feedback can play in dialogue.

Feedback Annotations

There are some rich annotation frameworks including feedback aspects such as [START_REF] Allwood | The MUMIN coding scheme for the annotation of feedback, turn management and sequencing phenomena[END_REF][START_REF] Petukhova | Towards an integrated scheme for semantic annotation of multimodal dialogue data[END_REF]. However given our focus on a few restricted forms we will only use part of these comprehensive frameworks. Moreover we inherit from previous annotations efforts. Namely for the CID corpus we already have some back-channels annotations performed. The categories annotated were: continuer (minimally takes note), understanding (understands), assessment (agrees with what has been said), and evaluation (evaluate and display an attitude about what has been said). Orthogonally turn-initiating and turn-ending features have been added. From another study, [START_REF] Muller | An empirical study of acknowledgement structures[END_REF] we wanted to include (i) aspects related to the confirmation nature 2 of some feedback items and (ii) their discourse 2 Related to allo-feedback in DIT scheme [START_REF] Petukhova | Towards an integrated scheme for semantic annotation of multimodal dialogue data[END_REF] for example.

structuring functions such as closing current discourse topic.

Perhaps the most original part of our annotation scheme is the annotation of the feedback scope. In [START_REF] Muller | An empirical study of acknowledgement structures[END_REF], we identified 3 relevant scopes: last utterance, last pair or wide scope. In the corpus we used, this scope annotation was reasonably well annotated (κ = 0.6) and allowed us to specify the functions of some of the lexical items studied without having to rely on finer-grained functions.

Analysis and Modeling

The model we are aiming at combines a detailed multidimensional analysis of the forms involved, a deep modeling of the meaning of these forms and how these meanings are used to reach the communicative goals.

Analysis of the forms

About the first aspect we will perform both linguistic analysis (including in particular systematic prosodic analysis) and more acoustic measurements. About the prosodic aspects, a track we will follow is the Functional Data Analysis (FDA) such as proposed in [START_REF] Gubian | Joint analysis of f0 and speech rate with functional data analysis[END_REF]. We therefore adopt a really data-driven approach but guided by the linguistic analysis. FDA requires indeed to have some minimal hypotheses about the shapes of the contours before starting the purely statistical analysis that will distinguish several clusters of instances of contours. Concerning this level the goal is to delineate as precisely as possible the formal categories in all the dimensions considered (at least lexical item, prosodic contour, acoustic parameters).

Model of the functions

Concerning the functions, we consider that simply having a list of categories is not enough. To have a function one should be able to model the effects on context. Moreover, we are also interested into the meaning (if any) of the forms considered and how it is exploited by the participants to perform communicative actions. The set of communicative actions comes from the literature on these issues, in particular from the DIT+ framework [START_REF] Bunt | Multifunctionality in dialogue[END_REF]. However we would like to go step deeper by looking at how formal theory of dialogue [START_REF] Lascarides | Grounding and correcting commitments in dialogue[END_REF][START_REF] Bunt | Multifunctionality in dialogue[END_REF][START_REF] Ginzburg | The Interactive Stance: Meaning for Conversation[END_REF] are handling these phenomena.

Despite differences with regard to the primitives and to representation tools, it is possible to list a few properties any semantic/pragmatic theory should feature for being able to deal with feedback items:

• Radical context dependence: Given the range of communication functions a simple word as 'yeah' can rich in a conversation, it is clear that the theory has to be a theory of how the meaning of a new utterance is interpreted (and resolved) in a given context ;

• Rich ontology of communication objects, the context in which utterances are resolved cannot simply be a flat representation of the actual world. Feedback has a meta-level nature, it is information about the information exchange, not about the content exchanged directly. Moreover feedback is also about processing of information by the speaker (cognitive realm) and about conventional rules of the exchange (social realm).

Dynamic semantics and further work grounded in this paradigm all feature the first point while the second one is present in most of the works that have looked seriously at dialogue. For the formal modeling aspect of our work, we will focus on two semantic theories that have put dialogue on their agenda: SDRT (Segmented Discourse Representation Theory) from [START_REF] Lascarides | Grounding and correcting commitments in dialogue[END_REF] and KOS from [START_REF] Ginzburg | The Interactive Stance: Meaning for Conversation[END_REF].

Current work

Our current work consist in building the data sets from the corpora and in finishing recording the third corpus. By the time of the workshop, we will have conduced some preliminary studies on a data subset. The study will include a FDA data analysis for at least two French lexical items in the CID corpus: ouais (yeah) and voilà (that's it). For this data subset, we will complete the annotations of the functions in order to have as small scale picture of our project to present during the workshop.

Figure 1 :

 1 Figure 1: Sketch of the CoFee model

CoFee -Conversational Feedback: Multi-dimensional Analysis and Modeling-is a newly funded ANR (Agence Nationale pour la Recherche) 3-year project [2012-2015].


Portes

Basic prosodic transcription of short French feedback utterances

Basic prosodic transcription of short

French feedback utterances Laurent Prévot, Mariapaola D'Imperio, Caterina Petrone http://lpl-aix.fr/person/lastname Laboratoire Parole et Langage, Aix-en-Provence, France

Context

• Feedback as a testcase for studying interfaces between linguistic domains

• Feedback extremely frequent in conversation

• Feedback crucial for communicative activities

Form-Function relationship

• Early work on Italian [START_REF] Cerrato | Duration and tonal characteristics of short expressions in italian[END_REF] • More systematic quantitative approach on English [START_REF] Gravano | Turn-Taking and Affirmative Cue Words in Task-Oriented Dialogue[END_REF] • For these languages, transcription system do exist, not the case for French

; Need a sound and reliable prosodic transcription

Objectives

• Pilot study on very simple categories

• How far can we get with a quick and dirty manual approach

• Compare with an automatic tool

• Evaluate against an expert evaluation

• Test out transcription and evaluation methodologies

Automatic baseline for tones • For these items, it seems easier to train for transcribing phrasing than contours

• Expert reports than contours on these items are much richer than tripartite classification proposed

• Other crucial ingredients for characterizing these forms: registers, voice quality

Acknowledgements