Jean-Éric Pin

Theme and variations on the concatenation product

The concatenation product is one of the most important operations on regular languages. Its study requires sophisticated tools from algebra, finite model theory and profinite topology. This paper surveys research advances on this topic over the last fifty years.

.

This survey article surveys the most important results and tools related to the concatenation product, including connections with algebra, profinite topology and finite model theory. The paper is organised as follows: Section 1 presents some useful algebraic tools for the study of the concatenation product. Section 2 introduces the main definitions on the product and its variants. The classical results are summarized in Section 3. Sections 4 and 5 are devoted to the study of two algebraic tools: Schützenberger products and relational morphisms. Closure properties form the topic of Section 6. Hierarchies and their connection with finite model theory are presented in Sections 7 and 8. Finally, new directions are suggested in Section 9.

The instruments

This section is a brief reminder on the algebraic notions needed to study the concatenation product: semigroups and semirings, syntactic ordered monoids, free profinite monoids, equations and identities, varieties and relational morphisms. More information can be found in [1-3, 18, 35, 42, 45].

Semigroups and semirings

If S is a semigroup, the set P(S) of subsets of S is also a semiring, with union as addition and multiplication defined, for every X, Y ∈ P(S), by

In this semiring, the empty set is the zero and for this reason, is denoted by 0. It is also convenient to denote simply by x a singleton {x}.

If k is a semiring, we denote by M n (k) be the semiring of square matrices of size n with entries in k.

Syntactic ordered monoid

Let L be a language of A * . The syntactic preorder of L is the relation L defined on A * by u L v if and only if, for every x, y ∈ A * ,

xvy ∈ L ⇒ xuy ∈ L
The syntactic congruence of L is the relation ∼ L defined by u ∼ L v if and only if u L v and v L u.

The syntactic monoid of L is the quotient M (L) of A * by ∼ L and the natural morphism η : A * → A * /∼ L is called the syntactic morphism of L. The syntactic preorder L induces an order on the quotient monoid M (L). The resulting ordered monoid is called the syntactic ordered monoid of L.

The syntactic ordered monoid can be computed from the minimal automaton as follows. First observe that if A = (Q, A, • , q -, F ) is a minimal deterministic automaton, the relation defined on Q by p q if for all u ∈ A * , q• u ∈ F ⇒ p• u ∈ F is an order relation, called the syntactic order of the automaton. Then the syntactic ordered monoid of a language is the transition monoid of its ordered minimal automaton. The order is defined by u v if and only if, for all q ∈ Q, q• u q• v.

For instance, let L be the language {a, aba}. Its minimal deterministic automaton is represented below: The order on the set of states is 2 4, 1 3 and 1, 2, 3, 4 0. Indeed, one has 0• u = 0 for all u ∈ A * and thus, the formal implication 0• u ∈ F ⇒ q• u ∈ F holds for any state q. Similarly, 1 3 since a is the only word such that 3• a ∈ F and one also has 1• a ∈ F . The syntactic monoid of L is the monoid M = {1, a, b, ab, ba, aba, 0} presented by the relations a 2 = b 2 = bab = 0. Its syntactic order is 1 < ab < 0, 1 < ba < 0, a < aba < 0, b < 0.

Free profinite monoids

We briefly recall the definition of a free profinite monoid. More details can be found in [START_REF] Almeida | Finite semigroups and universal algebra[END_REF][START_REF] Pin | Profinite methods in automata theory[END_REF]. A finite monoid M separates two words u and v of A * if there is a morphism ϕ : A * → M such that ϕ(u) = ϕ(v). We set r(u, v) = min |M | | M is a finite monoid that separates u and v } and d(u, v) = 2 -r(u,v) , with the usual conventions min ∅ = +∞ and 2 -∞ = 0. Then d is a metric on A * and the completion of A * for this metric is denoted by A * . The product on A * can be extended by continuity to A * . This extended product makes A * a compact topological monoid, called the free profinite monoid. Its elements are called profinite words.

In a compact monoid, the smallest closed subsemigroup containing a given element s has a unique idempotent, denoted s ω . This is true in particular in a finite monoid and in the free profinite monoid.

One can show that every morphism ϕ from A * into a (discrete) finite monoid M extends uniquely to a a uniformly continuous morphism ϕ from A * to M . It follows that if x is a profinite word, then ϕ(x ω ) = ϕ(x) ω .

Equations and identities

Let ϕ be a morphism from A * into a finite [ordered] monoid M and let x, y be two profinite words of A * . We say that ϕ satisfies the profinite equation

x = y [x y] if ϕ(x) = ϕ(y) [ ϕ(x) ϕ(y)].
A regular language of A * satisfies a profinite equation if its syntactic morphism satisfies this equation. More generally, we say that a set of regular languages L is defined a set of profinite equations E if L is the set of all regular languages satisfying every equation of E.

A lattice of languages is a set L of languages of A * containing ∅ and A * and closed under finite union and finite intersection. It is closed under quotients if, for each L ∈ L and u ∈ A * , the languages u -1 L and Lu -1 are also in L. It is proved in [START_REF] Gehrke | Duality and equational theory of regular languages[END_REF] that a set of regular languages is a lattice [Boolean algebra] closed under quotient if and only if it can be defined by a set of profinite equations of the form u v [u = v].

A finite [ordered] monoid M satisfies the identity x = y [x y] if every morphism from A * into M satisfies this equation. These notions can be extended to semigroups by considering morphisms from the free semigroup A + to a finite semigroup.

Varieties of monoids

In this paper, we will only consider varieties in Eilenberg's sense. Thus, for us, a variety of semigroups is a class of finite semigroups closed under taking subsemigroups, quotients and finite direct products [START_REF] Eilenberg | Automata, Languages and Machines[END_REF]. Varieties of ordered semigroups, monoids and ordered monoids are defined analogously [START_REF] Pin | A variety theorem without complementation[END_REF].

Given a set E of identities, we denote by E the class of all finite [ordered] monoids which satisfy all the identities of E. Reiterman's theorem [START_REF] Reiterman | The Birkhoff theorem for finite algebras[END_REF] and its extension to ordered structures [START_REF] Pin | A Reiterman theorem for pseudovarieties of finite firstorder structures[END_REF] states that every variety of [ordered] monoids [semigroups] can be defined by a set of identities. For instance, the variety of ordered semigroups x ω yx ω

x ω is the variety of ordered semigroups S such that, for each idempotent e ∈ S and for each s ∈ S, ese e.

The following varieties will be used in this paper: the variety A of aperiodic monoids, defined by the identity x ω+1 = x ω , the variety R [L] of R-trivial [Ltrivial ] monoids, defined by the identity (xy) ω x = x ω [y(xy) ω = x ω ] and the variety DA, which consists of the aperiodic monoids whose regular J -classes are idempotent semigroups. This variety is defined by the identities x ω = x ω+1 and (xy) ω (yx) ω (xy) ω = (xy) ω .

We will also consider two group varieties: the variety G p of p-groups (for a prime p) and the variety Gsol of soluble groups.

Finally, if V is a variety of monoids, the class of all semigroups S such that, for each idempotent e ∈ S, the "local" monoid eSe belongs to V, form a variety of semigroups, denoted LV. In particular, the variety LI is the variety of locally trivial semigroups, defined by the identity x ω yx ω = x ω .

Varieties of languages

A class of languages C associates with each alphabet A a set C(A * ) of regular languages of A * . A positive variety of languages is a class of languages V such that, for all alphabets A and B,

(

1) V(A * ) is a lattice of languages closed under quotients, ( 2
) if ϕ : A * → B * is a morphism, then L ∈ V(B * ) implies ϕ -1 (L) ∈ V(A * ).
A variety of languages is a positive variety V such that, for each alphabet A, V(A * ) is closed under complement. We can now state Eilenberg's variety theorem [START_REF] Eilenberg | Automata, Languages and Machines[END_REF] and its counterpart for ordered monoids [START_REF] Pin | A variety theorem without complementation[END_REF].

Theorem 1.1. Let V be a variety of monoids. For each alphabet A, let V(A * ) be the set of all languages of A * whose syntactic monoid is in V. Then V is a variety of languages. Further, the correspondence V → V is a bijection between varieties of monoids and varieties of languages.

Theorem 1.2. Let V be a variety of ordered monoids. For each alphabet A, let V(A * ) be the set of all languages of A * whose syntactic ordered monoid is in V. Then V is a positive variety of languages. Further, the correspondence V → V is a bijection between varieties of ordered monoids and positive varieties of languages.

A slightly more general definition was introduced by Straubing [START_REF] Straubing | On logical descriptions of regular languages[END_REF]. Let C be a class of morphisms between free monoids, closed under composition and containing all length-preserving morphisms. Examples include the classes of all length-preserving morphisms, of all length-multiplying morphisms (morphisms such that, for some integer k, the image of any letter is a word of length k), all non-erasing morphisms (morphisms for which the image of each letter is a nonempty word), all length-decreasing morphisms (morphisms for which the image of each letter is either a letter or the empty word) and all morphisms.

A positive C-variety of languages is a class V of recognisable languages satisfying the first condition defining a positive variety of languages and a second condition

(2 ′ ) if ϕ : A * → B * is a morphism in C, L ∈ V(B * ) implies ϕ -1 (L) ∈ V(A * ).
A C-variety of languages is a positive C-variety of languages closed under complement. When C is the class of non-erasing morphisms (for which the image of a letter is a nonempty word), we use the term ne-variety. These ne-varieties are essentially the same thing as Eilenberg's +-varieties (see [49, p. 260-261] for a detailed discussion) and they correspond to varieties of semigroups.

Relational morphisms

A relational morphism between two monoids M and N is a function τ from M into P(N ) such that:

(1) for all

M ∈ M , τ (m) = ∅, (2) 1 ∈ τ (1), ( 3
) for all m, n ∈ M , τ (m)τ (n) ⊆ τ (mn) Let V be a variety of [ordered] semigroups. A [relational] morphism τ : M → N is said to be a [relational] V-morphism if for every [ordered] semigroup R of N belonging to V, the [ordered] semigroup τ -1 (R) also belongs to V.
Let me point out an important subtlety. The definition of a [relational] Vmorphism adopted in this paper is taken from [START_REF] Pin | Algebraic tools for the concatenation product[END_REF] and differs from the original definition given for instance in [START_REF] Straubing | Relational morphisms and operations on recognizable sets[END_REF][START_REF] Pin | Syntactic semigroups[END_REF]. The original definition only requires that, for each idempotent e, the [ordered] semigroup τ -1 (e) also belongs to V. In many cases the two definitions are equivalent: for instance, when V is one of the varieties A, x ω yx ω = x ω , x ω y = x ω , yx ω = x ω or LH where H is a variety of groups. However, the two definitions are not equivalent for the variety x ω yx ω x ω .

Theme and variations: the concatenation product

We now come to the main topic of this article. Just like a piece of classical music, the concatenation product includes theme and variations.

Main theme

The product (or concatenation product ) of the languages L 0 , L 1 , . . . , L n of A * is the language

L 0 L 1 • • • L n = {u 0 u 1 • • • u n | u 0 ∈ L 0 , u 1 ∈ L 1 , • • • , u n ∈ L n } A language L of A * is a marked product of the languages L 0 , L 1 , . . . , L n if L = L 0 a 1 L 1 • • • a n L n
for some letters a 1 , . . . , a n of A.

Three variations

Variations include the unambiguous, deterministic, bideterministic and modular products, that are defined below.

Unambiguous product. A marked product L = L 0 a 1 L 1 • • • a n L n is said to be unambiguous if every word of L admits a unique decomposition of the form u = u 0 a 1 u 1 • • • a n u n with u 0 ∈ L 0 , . . . , u n ∈ L n . For instance, the marked product {a, c} * a{1}b{b, c} * is unambiguous. Deterministic product. A word x is a prefix [suffix ] of a word u if there is a word v such that u = xv [u = vx]. It is a proper prefix [suffix] if x = u. A subset C of A + is a prefix [suffix ] code if if no element of C is a proper prefix [suffix] of another element of C. A marked product L = L 0 a 1 L 1 • • • a n L n of n nonempty languages L 0 , L 1 , . . . , L n of A * is left [right ] deterministic if, for 1 i n, the set L 0 a 1 L 1 • • • L i-1 a i [a i L i • • • a n L n ] is a prefix [suffix] code. This means that every word of L has a unique prefix [suffix] in L 0 a 1 L 1 • • • L i-1 a i [a i L i • • • a n L n ]. It is observed in [9, p. 495] that the marked product L 0 a 1 L 1 • • • a n L n is deterministic if and only if, for 1 i n, the language L i-1 a i is a prefix code.

Since the product of two prefix codes is a prefix code, any left [right ] deterministic product of left [right ] deterministic products is left [right ] deterministic.

A marked product is said to be bideterministic if it is both left and right deterministic.

Modular product of languages.

Let L 0 , . . . , L n be languages of A * , let a 1 , . . . , a n be letters of A and let r and p be integers such that 0 r < p. We define the modular product of the languages L 0 , . . . , L n with respect to r and p, denoted (L

0 a 1 L 1 • • • a n L n ) r,p , as the set of all words u in A * such that the number of factorizations of u in the form u = u 0 a 1 u 1 • • • a n u n , with u i ∈ L i for 0 i n, is congruent to r modulo p.
A language is a p-modular product of the languages L

0 , . . . , L n if it is of the form (L 0 a 1 L 1 • • • a n L n ) r,p for some r.
Recall that the set of star-free languages is the smallest Boolean algebra of languages of A * which is closed under marked product. Theorem 3.1 (Schützenberger [60]). A regular language is star-free if and only if its syntactic monoid is aperiodic.

There are essentially two proofs of this result. Schützenberger's original proof [START_REF] Schützenberger | On finite monoids having only trivial subgroups[END_REF][START_REF] Pin | Varieties of formal languages[END_REF], slightly simplified in [START_REF] Perrin | Finite automata[END_REF], works by induction on the J -depth of the syntactic semigroup. Schützenberger's proof actually gives a stronger result since it shows that the star-free languages form the smallest Boolean algebra of languages of A * which is closed under marked products of the form L → LaA * and A * aL. In other words, marked products with A * suffice to generate all star-free languages.

The other proof [START_REF] Cohen | On Star-Free Events[END_REF][START_REF] Meyer | A note on star-free events[END_REF] makes use of a weak form of the Krohn-Rhodes theorem: every aperiodic semigroup divides a wreath product of copies of the monoid U 2 = {1, a, b}, given by the multiplication table aa = a, ab = b, ba = b and bb = b.

Theorem 3.1 provides an algorithm to decide whether a given regular language is star-free. The complexity of this algorithm is analysed in [START_REF] Cho | Finite-automaton aperiodicity is PSPACE-complete[END_REF][START_REF] Stern | Characterizations of some classes of regular events[END_REF].

Let us define in the same way the set of unambiguous [right deterministic, left deterministic] star-free languages as the smallest Boolean algebra of languages of A * containing the languages of the form B * , for B ⊆ A, which is closed under unambiguous [left deterministic, right deterministic] marked product. The algebraic characterizations of these classes are also known. Theorem 3.2 (Schützenberger [START_REF] Schützenberger | Sur le produit de concaténation non ambigu[END_REF]). A regular language is unambiguous star-free if and only if its syntactic monoid belongs to DA.

One can show that the set of unambiguous star-free languages of A * is the smallest set of languages of A * containing the languages of the form B * , for B ⊆ A, which is closed under finite disjoint union and unambiguous marked product. The languages corresponding to DA admit several other nice characterizations: see [START_REF] Tesson | Diamonds Are Forever: The Variety DA, in Semigroups, Algorithms, Automata and Languages[END_REF] for a survey.

Deterministic products were also studied in [START_REF] Schützenberger | Sur le produit de concaténation non ambigu[END_REF]. Alternative descriptions of these languages can be found in [START_REF] Eilenberg | Automata, Languages and Machines[END_REF][START_REF] Brzozowski | Languages of R-trivial monoids[END_REF].

Theorem 3.3 ([18]). A regular language is left [right ] deterministic star-free if and only if its syntactic monoid is R-trivial [L-trivial ].
Similar results are known for the p-modular product [START_REF] Eilenberg | Automata, Languages and Machines[END_REF][START_REF] Straubing | Families of recognizable sets corresponding to certain varieties of finite monoids[END_REF][START_REF] Thérien | Languages of Nilpotent and Solvable Groups (Extended Abstract)[END_REF][START_REF] Thérien | A language theoretic interpretation of the Schützenberger representations with applications to certain varieties of languages[END_REF][START_REF] Péladeau | Sur le produit avec compteur modulo un nombre premier[END_REF][START_REF] Weil | An extension of the Schützenberger product[END_REF][START_REF] Weil | Products of languages with counter[END_REF][START_REF] Weil | Closure of varieties of languages under products with counter[END_REF].

Theorem 3.4. Let p be a prime. A language of A * belongs to the smallest Boolean closed under p-modular product if and only if its syntactic monoid is a p-group. Theorem 3.5. A language of A * belongs to the smallest Boolean closed under p-modular product for all prime p if and only if its syntactic monoid is a soluble group.

Finally, one may consider the product and the p-modular products simultaneously.

Theorem 3.6. A language of A * belongs to the smallest Boolean closed under product and under p-modular product for all prime p if and only if all the groups in its syntactic monoid are soluble.

See also [START_REF] Thérien | Sur les monoïdes dont tous les groupes sont résolubles[END_REF] for another description of this variety of languages.

The ground bass: Schützenberger products

The Schützenberger product is the first algebraic tool used to study the concatenation product. It was first defined by Schützenberger [START_REF] Schützenberger | On finite monoids having only trivial subgroups[END_REF] and later generalized by Straubing [START_REF] Straubing | A generalization of the Schützenberger product of finite monoids[END_REF]. An intuitive construction, related to the linear representation of a suitable transducer, was given in [START_REF] Pin | Some operations and transductions that preserve rationality[END_REF][START_REF] Pin | Une application de la représentation matricielle des transductions[END_REF] and is briefly sketched below. More information on transducers and their linear representations can be found in Sakarovitch's book [START_REF] Sakarovitch | Elements of automata theory[END_REF].

Transducers for the product

The construction given in [START_REF] Pin | Some operations and transductions that preserve rationality[END_REF][START_REF] Pin | Une application de la représentation matricielle des transductions[END_REF] relies on the following observation. Let τ and τ a be the transductions from A * to A * × A * defined by

τ (u) = {(u 1 , u 2 ) | u 1 u 2 = u} τ a (u) = {(u 1 , u 2 ) | u 1 au 2 = u}
It is easy to see that the two transducers pictured below realise these transductions. In these figures, c is a generic letter and the symbol | is a separator between the input letter and the output.

1 2 1 2 c | (c, 1) 1 | (1, 1) c | (1, c) c | (c, 1) a | (1, 1) c | (1, c)
The transducer on the left

[right] realizes τ [τ a ]. Now L 0 L 1 = τ -1 (L 0 × L 1 ) and L 0 aL 1 = τ -1 a (L 0 × L 1 )
and this equality allows one to compute a monoid recognising L 0 L 1 and L 0 aL 1 , given monoids recognising L 0 and L 1 .

This construction can be readily extended to (marked) products of several languages. For instance, given a 1 , . . . , a n ∈ A, the transduction σ defined by

σ(u) = {(u 0 , • • • , u n ) ∈ (A * ) n+1 | u 0 a 1 u 1 • • • a n u n = u} is realised by the trans- ducer 8 1 2 . . . n -1 n c | (c, 1
)

a 1 | (1, 1) c | (1, c) c | (1, c) a n | (1, 1) c | (1, c)
and the marked product

L 0 a 1 L 1 • • • a n L n is equal to σ -1 (L 0 × L 1 × • • • × L n ).
A bit of algebra is now required to make full use of this transduction.

Linear representations

The R be the semiring P(A * × A * ). Then for each word u in A * , τ a (u) = µ(u) 1,2 , where µ :

A * → M 2 (R) is defined by µ(a) = (c, 1) (1, 1) 0 (1, c) and µ(c) = (c, 1) 0 0 (1, c) if c = a
Indeed, for each u ∈ A * , one gets

µ(u) = (u, 1) {(u 0 , u 1 ) | u 0 au 1 = u} 0 (1, u)
which gives the result. Let now π 0 :

A * → M 0 [π 1 : A * → M 1 ] be a monoid morphism recognising the language L 0 [L 1 ] and let M = M 0 × M 1 . Let π = π 0 × π 1 .
Then π is a monoid morphism from A * × A * into M , which can be first extended to a semiring morphism from A * × A * to P(M ) and then to a semiring morphism from M 2 (A * × A * ) to M 2 (P(M )), also denoted by π. It follows that π • µ is a morphism from A * into M 2 (P(M )) and it is not difficult to see that this morphism recognises the language τ -1 a (L 0 × L 1 ), that is, L 0 aL 1 . Further, if u is a word of A * , the matrix π • µ(u) has the form

(m 0 , 1) P 0 (1, m 1 )
for some m 0 ∈ M 0 , m 1 ∈ M 1 and P ⊆ M 0 × M 1 . In particular, L 0 aL 1 is recognised by the monoid of matrices of this form. This monoid is the Schützenberger product of the monoids M 0 and M 1 .

A similar representation can be given for the transducer σ and this leads to the definition of the Schützenberger product of n + 1 monoids M 0 , . . . , M n . In fact, one can give a slightly more general definition. Let M = M 0 × • • • × M n , let k be a semiring and let k[M ] be the monoid algebra of M over k. The Schützenberger product over k of the monoids M 0 , . . . , M n , is the submonoid of

M n+1 (k[M ]) made up of matrices m = (m i,j ) such that (1) m i,j = 0, for i > j, ( 2
) m i,i = (1, . . . , 1, m i , 1, . . . , 1) for some m i ∈ M i , ( 3
) m i,j ∈ k[1 × • • • × 1 × M i × • • • × M j × 1 × • • • × 1], for i < j.
This monoid is denoted k♦(M 0 , . . . , M n ). The first condition means that the matrices are uppertriangular, the second one that the entry m i,i can be identified with an element of M i . When k is the Boolean semiring, then k[M ] is isomorphic to P(M ) and the Schützenberger product is simply denoted ♦(M 0 , . . . , M n ). For instance, a matrix of ♦ 3 (M 1 , M 2 , M 3 ) will have the form

  s 1 P 1,2 P 1,3 0 s 2 P 2,3 0 0 s 3   with s i ∈ M i , P 1,2 ⊆ M 1 × M 2 , P 1,3 ⊆ M 1 × M 2 × M 3 and P 2,3 ⊆ M 2 × M 3 .
The first part of the next proposition is due to Schützenberger [START_REF] Schützenberger | On finite monoids having only trivial subgroups[END_REF] for n = 1 and to Straubing [START_REF] Straubing | A generalization of the Schützenberger product of finite monoids[END_REF] for the general case.

Proposition 4.1. Let L = L 0 a 1 L 1 • • • a n
L n be a marked product and let M i be the syntactic monoid of L i , for 0 i n. Then the Schützenberger product ♦ n (M 0 , . . . , M n ) recognises L.

A similar result holds for the p-modular product, for a prime p, by taking k = F p , the field with p elements [START_REF] Pin | Finite group topology and p-adic topology for free monoids[END_REF][START_REF] Pin | Topologies for the free monoid[END_REF][START_REF] Weil | Products of languages with counter[END_REF].

Proposition 4.2. Let L = (L 0 a 1 L 1 • • • a n L n ) r,
p be a p-modular product and let M i be the syntactic monoid of L i , for 0 i n. Then the Schützenberger product F p ♦ n (M 0 , . . . , M n ) recognises L.

In view of Proposition 4.1, a natural question arises: what are the languages recognised by a Schützenberger product? In the Boolean case, the answer was first given by Reutenauer [START_REF] Reutenauer | Sur les variétés de langages et de monoïdes[END_REF] for n = 2 and by the author [START_REF] Pin | Hiérarchies de concaténation[END_REF] in the general case (see also [START_REF] Weil | Closure of varieties of languages under products with counter[END_REF][START_REF] Simon | The product of rational languages[END_REF]). The case k = F p was treated by Weil [79, Theorem 2.2]. Theorem 4.3. A language is recognised by the Schützenberger product of M 0 , . . . , M n if and only if it belongs to the Boolean algebra generated by the marked products of the form

L i0 a 1 L i1 • • • a s L is where 0 i 0 < i 1 < • • • < i s n and L ij is recognised by M ij for 0 j s.
Theorem 4.4. A language is recognised by the monoid F p ♦(M 0 , . . . , M n ) if and only if it belongs to the Boolean algebra generated by the p-modular products of the form

(L i0 a 1 L i1 • • • a s L is ) r,p where 0 i 0 < i 1 < • • • < i s n and L ij is recognised by M ij for 0 j s.
In the Boolean case, it is possible to give an ordered version of Theorem 4.3 [START_REF] Pin | Polynomial closure and unambiguous product[END_REF][START_REF] Pin | Algebraic tools for the concatenation product[END_REF]. Indeed, the (Boolean) Schützenberger product can be ordered by reverse inclusion: P P ′ if and only if for 1 i j n, P i,j ⊇ P ′ i,j . The corresponding ordered monoid is denoted ♦ + n (M 0 , . . . , M n ) and is called the ordered Schützenberger product of M 1 , . . . , M n . Theorem 4.5. A language is recognised by the ordered Schützenberger product of M 0 , . . . , M n if and only if it belongs to the lattice generated by the marked products of the form

L i0 a 1 L i1 • • • a s L is where 0 i 0 < i 1 < • • • < i s n and L ij is recognised by M ij for 0 j s.

Algebraic properties of the Schützenberger product

It follows from the definition of the Schützenberger product that the map sending a matrix to its diagonal is a morphism π from k♦(M 0 , . . . , M n ) to M . The properties of this morphism were first analysed by Straubing [START_REF] Straubing | A generalization of the Schützenberger product of finite monoids[END_REF] and by the author [START_REF] Pin | A property of the Schützenberger product[END_REF][START_REF] Pin | Polynomial closure and unambiguous product[END_REF][START_REF] Pin | Algebraic tools for the concatenation product[END_REF] in the Boolean case and by Weil [80, Corollary 3.6] when k = F p . See also [START_REF] Almeida | Representation theory of finite semigroups, semigroup radicals and formal language theory[END_REF].

Proposition 4.6. The morphism π : ♦(M 0 , . . . , M n ) → M is a x ω yx ω x ωmorphism.

Proposition 4.7. The morphism π :

F p ♦(M 0 , . . . , M n ) → M is a LG p -morphism.

Passacaglia: pumping properties

The second method to study the product is to use relational morphisms. This technique was initiated by Straubing [START_REF] Straubing | Relational morphisms and operations on recognizable sets[END_REF] and later refined in [START_REF] Branco | Two algebraic approaches to variants of the concatenation product[END_REF][START_REF] Branco | Equations for the polynomial closure[END_REF][START_REF] Pin | A property of the Schützenberger product[END_REF][START_REF] Pin | Algebraic tools for the concatenation product[END_REF][START_REF] Pin | Locally trivial categories and unambiguous concatenation[END_REF][START_REF] Pin | Polynomial closure and unambiguous product[END_REF]. We first state the main result under the form of a pumping lemma before turning to a more algebraic formulation.

Let L = L 0 a 1 L 1 • • • a n L n be a marked product of regular languages.

Theorem 5.1. Let u and v be words of A * satisfying the following properties:

(1) u 2 ∼ L u and (2) for each i ∈ {0, . . . , n}, u 2 ∼ Li u and uvu Li u. Then for all x, y ∈ A * , the condition xuy ∈ L implies xuvuy ∈ L.

Another possible formulation of the theorem is to say that, under the assumptions (1) and (2), L is closed under the rewriting system u → uvu.

We now turn to the algebraic version of this statement. For each i, let L i be a language of A * , let η i : A * → M (L i ) be its syntactic morphism and let

η : A * → M (L 0 ) × M (L 1 ) × • • • × M (L n )
be the morphism defined by η(u) = (η 0 (u), η 1 (u), . . . , η n (u)). Finally, let µ : A * → M (L) be the syntactic morphism of L. Theorem 5.1 can be reformulated as a property of the relational morphism (see picture below)

τ = η • µ -1 : M (L) → M (L 0 ) × M (L 1 ) × • • • × M (L n ) M (L) M (L 0 ) × M (L 1 ) × • • • × M (L n ) A * µ τ = η • µ -1 η Theorem 5.2.
(1) The relational morphism τ is a relational x ω yx ω x ω -morphism.

(2) If the product is unambiguous, it is a relational x ω yx ω = x ω -morphism.

(3) If the product is left deterministic, it is a relational x ω y = x ω -morphism.

(4) If the product is right deterministic, it is a relational yx ω = x ω -morphism.

A similar result holds for the p-modular product.

Proposition 5.3. Let L = (L 0 a 1 L 1 • • • a n L n ) r,p be a p-modular product. The relational morphism τ : M (L) → M (L 0 ) × • • • × M (L n ) is a relational LG p - morphism.
Theorem 5.2 is often used in the following weaker form.

Corollary 5.4. The relational morphism τ :

M (L) → M (L 0 ) × M (L 1 ) × • • • × M (L n ) is an aperiodic relational morphism.
6 Chaconne: Closure properties

The results of Section 3 give a description of the smallest Boolean algebra closed under marked product and its variants. The next step would be to characterize all Boolean algebras closed under marked product and its variants. A related problem is to describe the classes of regular languages closed under union and marked product. Both problems have been solved in the case of a variety of languages, but the description of these results requires an algebraic definition. Let V be a variety of [ordered] monoids and let W be a variety of ordered semigroups. The class of all [ordered] monoids M such that there exists a V-relational morphism from M into a monoid of V is a variety of [ordered] monoids, denoted W -1 V.

Varieties closed under product

Varieties closed under marked products were described by Straubing [START_REF] Straubing | Families of recognizable sets corresponding to certain varieties of finite monoids[END_REF]. Theorem 6.1. Let V be a variety of monoids and let V be the associated variety of languages. For each alphabet A, let W(A * ) be the smallest Boolean algebra containing V(A * ) and closed under product. Then W is a variety and the associated variety of monoids is A -1 V.

This important result contains Theorem 3.1 as a particular case, when V is the trivial variety of monoids. Examples of varieties V satisfying the equality A -1 V = V also include the variety of monoids whose groups belong to a given variety of groups. Theorem 6.1 has been extended to C-varieties in [15, Theorem 4.1].

Varieties closed under modular product

Finally, let us mention the results of Weil [START_REF] Weil | Closure of varieties of languages under products with counter[END_REF]. A set of languages L of A * is closed under p-modular product if, for any language L 0 , . . . , L n ∈ L, for any letter a 1 , . . . , a n ∈ A and for any integer r such that 0 r < p,

(L 0 a 1 L 1 • • • a n L n ) r,p ∈ L.
A set of languages L of A * is closed under modular product if it is closed under p-modular product, for each prime p.

Theorem 6.2. Let p be a prime number, let V be a variety of monoids and let V be the associated variety of languages. For each alphabet A, let W(A * ) be the smallest Boolean algebra containing V(A * ) and closed under p-modular product. Then W is a variety of languages and the associated variety of monoids is

LG -1 p V.
Given a variety of groups H, let H be the variety of all monoids whose groups belong to H. Theorem 6.3. Let p be a prime number, let V be a variety of monoids and let V be the associated variety of languages. For each alphabet A, let W(A * ) be the smallest Boolean algebra containing V(A * ) and closed under product and pmodular product. Then W is a variety of languages and the associated variety of monoids is LG -1 p V. Theorem 6.4. Let V be a variety of monoids and let V be the associated variety of languages. For each alphabet A, let W(A * ) be the Boolean algebra containing V(A * ) and closed under modular product. Then W is a variety of languages and the associated variety of monoids is LGsol -1 V.

Polynomial closure

Let L be a lattice of languages. The polynomial closure of L is the set of languages that are finite unions of marked products of languages of L. It is denoted Pol(L). Similarly, the unambiguous polynomial closure of L is the set of languages that are finite unions of unambiguous marked products of languages of L. It is denoted UPol(L). The left and right deterministic polynomial closure are defined analogously, by replacing "unambiguous" by "left [right] deterministic".

They are denoted D l Pol(V) [D r Pol(V)].
An algebraic characterization of the polynomial closure of a variety of languages was first given in [START_REF] Pin | Polynomial closure and unambiguous product[END_REF][START_REF] Pin | Polynomial closure and unambiguous product[END_REF]. It was extended to positive varieties in [START_REF] Pin | Algebraic tools for the concatenation product[END_REF]. Theorem 6.5. Let V be a variety of [ordered ] monoids and let V be the associated [positive ] variety of languages. Then Pol(V) is a positive variety of languages and the associated variety of ordered monoids is x ω yx ω x ω -1 V. Theorem 6.5 has been extended to C-varieties in [START_REF] Pin | Some results on C-varieties[END_REF]Theorem 7.2]. For the unambiguous product, one has the following result [START_REF] Pin | Propriétés syntactiques du produit non ambigu[END_REF][START_REF] Pin | Locally trivial categories and unambiguous concatenation[END_REF][START_REF] Almeida | Representation theory of finite semigroups, semigroup radicals and formal language theory[END_REF]. Theorem 6.6. Let V be a variety of monoids and let V be the associated variety of languages. Then UPol(V) is a variety of languages and the associated variety of ordered monoids is x ω yx ω = x ω -1 V.

For the left (resp. right) deterministic product, similar results hold [START_REF] Pin | Propriétés syntactiques du produit non ambigu[END_REF][START_REF] Pin | Locally trivial categories and unambiguous concatenation[END_REF]. Theorem 6.7. Let V be a variety of monoids and let V be the associated variety of languages. Then D l Pol(V) (resp. D r Pol(V)) is a variety of languages, and the associated variety of monoids is

x ω y = x ω -1 V (resp. yx ω = x ω -1 V).
It is known that the smallest nontrivial variety of aperiodic monoids is the variety J 1 = xy = yx, x = x 2 . One can show that x ω y = x ω -1 J 1 is equal to the variety R of all R-trivial monoids, which is also defined by the identity (xy) ω x = (xy) ω . This leads to the following characterization [START_REF] Eilenberg | Automata, Languages and Machines[END_REF][START_REF] Brzozowski | Languages of R-trivial monoids[END_REF]. Corollary 6.8. For each alphabet A, R(A * ) consists of the languages which are disjoint unions of languages of the form

A * 0 a 1 A * 1 a 2 • • • a n A * n ,
where n 0, a 1 , . . . a n ∈ A and the A i 's are subsets of A such that a i / ∈ A i-1 , for 1 i n.

A dual result holds for L-trivial monoids. Finally, x ω yx ω = x ω -1 J 1 = DA, which leads to the description of the languages of DA given hereinabove.

Back to identities

A general result of [START_REF] Pin | Profinite semigroups, Mal'cev products and identities[END_REF] permits to give identities defining the varieties of the form V -1 W. In particular, we get the following results. Theorem 6.9. Let V be a variety of monoids. Then

(1) A -1 V is defined by the identities of the form x ω+1 = x ω , where x is a profinite word such that V satisfies the identity x = x 2 . (2) x ω yx ω = x ω -1 V is defined by the identities of the form x ω yx ω = x ω , where x, y are profinite words such that V satisfies the identity x = y = x 2 . (3) x ω yx ω

x ω -1 V is defined by the identities of the form x ω yx ω x ω , where x, y are profinite words such that V satisfies the identity x = y = x 2 .

Hierarchies and bridges

The Boolean algebra BL generated by a lattice L is called its Boolean closure. In particular, BPol(L) denotes the Boolean closure of Pol(L).

Concatenation hierarchies are defined by alternating Boolean operations and polynomial operations (union and marked product). More precisely, let L be a set of regular languages (or more generally, a class of languages). The concatenation hierarchy built on L is the sequence L n defined inductively as follows 1 : L 0 = L and, for each n 0:

(1) L 2n+1 is the polynomial closure of the level 2n, (2) L 2n+2 is the Boolean closure of the level 2n + 1. The next results summarize the results of [START_REF] Arfi | Polynomial operations on rational languages[END_REF][START_REF] Arfi | Opérations polynomiales et hiérarchies de concaténation[END_REF][START_REF] Pin | Polynomial closure and unambiguous product[END_REF]. Proposition 7.1. If L is a lattice of regular languages, then each even level is a lattice of regular languages and each odd level is a Boolean algebra. Further, if L is closed under quotients, then every level is closed under quotients.

Since the polynomial closure of a C-variety of languages is a positive C-variety of languages [49, Theorem 6.2], a similar result holds for C-varieties. Proposition 7.2. If L is a C-variety of languages, then each even level is a positive C-variety of languages and each odd level is a C-variety of languages.

For instance, the Straubing-Thérien' hierarchy V n [START_REF] Thérien | Classification of finite monoids: the language approach[END_REF][START_REF] Straubing | A generalization of the Schützenberger product of finite monoids[END_REF][START_REF] Straubing | Finite semigroup varieties of the form V * D[END_REF] is built on the trivial Boolean algebra V 0 = {∅, A * }. The starting point of Brzozowski's "dotdepth" hierarchy B n [START_REF] Brzozowski | Hierarchies of aperiodic languages[END_REF] was originally defined as the Boolean algebra of finite and cofinite languages but it was later suggested to start with the Boolean algebra

B 0 (A * ) = {F A * G ∪ H | F , G, H are finite languages}
This suggestion was motivated by Theorem 7.4 below. Another series of concatenation hierarchies is obtained as follows. Let H be a variety of groups and let H be the associated variety of languages. The concatenation hierarchy built on H is denoted by H n and these hierarchies are called group hierarchies.

It is not immediate to see that all these hierarchies do not collapse. This was first proved by Brzozowski and Knast [START_REF] Brzozowski | The dot-depth hierarchy of star-free languages is infinite[END_REF] for the dot-depth hierarchy, but the result also holds for the other hierarchies [START_REF] Margolis | Products of group languages[END_REF].

Theorem 7.3. The Straubing-Thérien' hierarchy, the dot-depth hierarchy and the group hierarchies are infinite.

Let V n be the variety of monoids corresponding to V n and let B n be the variety of semigroups corresponding to B n . There is a nice algebraic connection between V n and B n , discovered by Straubing [START_REF] Straubing | Finite semigroup varieties of the form V * D[END_REF]. Given a variety of [ordered] monoids V and a variety of monoids [semigroups] W, let V * W be the variety of [ordered] monoids generated by the semidirect products M * N with M ∈ V and N ∈ W. Theorem 7.4. The equality B n = V n * LI holds for each n 0.

There is a similar bridge between V n and H n for each variety of groups H [START_REF] Pin | Bridges for concatenation hierarchies[END_REF][START_REF] Pin | Algebraic tools for the concatenation product[END_REF].

Theorem 7.5. The equality H n = V n * H holds for each n 0.

It is still an outstanding open problem to know whether there is an algorithm to compute the concatenation level of a given regular language. Here is a brief summary of the known results. Let us start with the level 1 [START_REF] Margolis | Products of group languages[END_REF][START_REF] Pin | A variety theorem without complementation[END_REF][START_REF] Pin | Polynomial closure of group languages and open sets of the Hall topology[END_REF][START_REF] Pin | The wreath product principle for ordered semigroups[END_REF]. Let G be the variety of all groups.

Theorem 7.6. The following relations hold:

V 1 = x 1 , B 1 = x ω yx ω
x ω and G 1 = x ω 1 . In particular, these varieties are decidable.

The languages of G 1 are also known to be the open regular sets for the progroup topology [START_REF] Margolis | Products of group languages[END_REF]. Extensions of this result to the varieties H 1 where H is a variety of groups is the topic of intensive research. See in particular Steinberg' article [START_REF] Steinberg | Polynomial closure and topology[END_REF].

The first decidability result for the level 2 was obtained by Simon [START_REF] Simon | Piecewise testable events[END_REF].

Theorem 7.7. A language belongs to V 2 if and only if its syntactic monoid is J -trivial.

The corresponding result for B 2 is due to Knast [START_REF] Knast | A semigroup characterization of dot-depth one languages[END_REF][START_REF] Knast | Some theorems on graph congruences[END_REF] Theorem 7.8. A language belongs to B 2 if and only if its syntactic semigroup satisfies the identity (x ω py ω qx ω ) ω x ω py ω sx ω (x ω ry ω sx ω ) ω = (x ω py ω qx ω ) ω (x ω ry ω sx ω ) ω .

The corresponding result for G 2 has a long story, related in detail in [START_REF] Pin | a success story[END_REF], where several other characterizations can be found. Theorem 7.9. A language belongs to G 2 if and only if in its syntactic monoid, the submonoid generated by the idempotents is J -trivial. Theorem 7.9 shows that G 2 is decidable. Again, there is a lot of ongoing work to try to extend this result to varieties of the form H 2 . See in particular [START_REF] Auinger | Varieties of finite supersolvable groups with the M. Hall property[END_REF].

Since level 3 is the polynomial closure of level 2, Theorem 6.5 can be applied. One gets in particular the following decidability result [START_REF] Pin | Polynomial closure and unambiguous product[END_REF]. Recall that the content of a word is the set of letters occurring in this word.

Theorem 7.10. A language belongs to V 3 if and only if its syntactic ordered monoid satisfies the identities x ω yx ω

x ω for all profinite words x, y with the same content.

The corresponding problem for B 3 is studied in [START_REF] Glaßer | Languages of dot-depth 3/2[END_REF][START_REF] Glaßer | Languages of dot-depth 3/2[END_REF][START_REF] Pin | The wreath product principle for ordered semigroups[END_REF]. In fact, Theorem 7.4 can be used to prove the following more general decidability result [START_REF] Pin | The wreath product principle for ordered semigroups[END_REF][START_REF] Straubing | Finite semigroup varieties of the form V * D[END_REF].

Theorem 7.11. For every integer n, the variety B n is decidable if and only if V n is decidable.

It is still an open problem to know whether a similar reduction exists for the hierarchy G n .

For the level 4, several partial results are known [START_REF] Pin | Monoids of upper triangular boolean matrices[END_REF][START_REF] Straubing | Semigroups and languages of dot-depth two[END_REF] and several conjectures have been formulated and then disproved [START_REF] Pin | Polynomial closure and unambiguous product[END_REF][START_REF] Steinberg | Polynomial closure and topology[END_REF][START_REF] Pin | A conjecture on the concatenation product[END_REF]. Due to the lack of space, we will not detail these results here. Some partial results are also known for the level 5 [START_REF] Glaßer | Level 5/2 of the Straubing-Thérien hierarchy for two-letter alphabets[END_REF].

Harmony with logic

One of the reasons why the decidability problem is particularly appealing is its close connection with finite model theory, first explored by Büchi in the early sixties. Büchi's logic comprises a relation symbol < and, for each letter a ∈ A, a unary predicate symbol a. The set FO[<] of first order formulas is built in the usual way by using these symbols, the equality symbol, first order variables, Boolean connectives and quantifiers.

A word u is represented as a structure (Dom(u), (a) a∈A , <) where Dom(u) = {1, . . . , |u|} and a = {i ∈ Dom(u) | u(i) = a}. The binary relation symbol < is interpreted as the usual order. Thus, if u = abbaab, Dom(u) = {1, . . . , 6}, a = {1, 4, 5} and b = {2, 4, 6}. Formulas can now be interpreted on words. For instance, the sentence ϕ = ∃x ∃y (x < y) ∧ (ax) ∧ (by) means "there exist two integers x < y such that, in u, the letter in position x is an a and the letter in position y is a b". Therefore, the set of words satisfying ϕ is A * aA * bA * . More generally, the language defined by a sentence ϕ is the set of words u such that ϕ satisfies u. The connection with star-free languages was established by McNaughton and Papert [START_REF] Mcnaughton | Counter-free automata[END_REF].

Theorem 8.1. A language is FO[<]-definable if and only if it is star-free.

Thomas [START_REF] Thomas | Classifying regular events in symbolic logic[END_REF] (see also [START_REF] Perrin | First order logic and star-free sets[END_REF]) refined this result by showing that the concatenation hierarchy of star-free languages corresponds, level by level, to the Σ nhierarchy, defined inductively as follows:

(1) Σ 0 consists of the quantifier-free formulas.

(2) Σ n consists of the formulas of the form ∃ * ∀ * ∃ * • • • ϕ with n alternating blocks of quantifiers and ϕ quantifier-free. (3) BΣ n denotes the class of formulas that are Boolean combinations of Σ nformulas. For instance, ∃x 1 ∃x 2 ∀x 3 ∀x 4 ∀x 5 ∃x 6 ϕ, where ϕ is quantifier free, is in Σ 3 . The next theorem is due to Thomas [START_REF] Thomas | Classifying regular events in symbolic logic[END_REF] (see also [START_REF] Perrin | First order logic and star-free sets[END_REF][START_REF] Pin | Logic, Semigroups and Automata on Words[END_REF]). Theorem 8.2.

(1) A language is Σ n [<]-definable if and only if it belongs to V 2n-1 .

(2) A language is BΣ n [<]-definable if and only if it belongs to V 2n .

A slightly expanded logic is required for the dot-depth hierarchy. Let min [max] be a predicate symbol interpreted as the minimum [maximum] of the domain and let P [S] be a relation symbol interpreted as the predecessor [successor] relation. Let Loc be the signature {min, max, S, P } ∪ {(a) a∈A }. Theorem 8.3.

(1) A language is Σ n [Loc]-definable if and only if it belongs to B 2n-1 .

(2) A language is BΣ n [Loc]-definable if and only if it belongs to B 2n .

Thus deciding whether a language has level n is equivalent to a very natural problem in finite model theory.

9 Other variations, recent advances Some specialized topics require even more sophisticated algebraic tools, like the kernel category of a morphism. This is the case for instance for the bideterministic product [START_REF] Branco | The kernel category and variants of the concatenation product[END_REF][START_REF] Branco | Two algebraic approaches to variants of the concatenation product[END_REF][START_REF] Branco | Deterministic concatenation product of languages recognized by finite idempotent monoids[END_REF] or for the marked product of two languages [START_REF] Almeida | Representation theory of finite semigroups, semigroup radicals and formal language theory[END_REF].

Another topic that we did not mention at all, but which is highly interesting, is the extension of these results to infinite words or even to words over ordinals or linear orders.

I would like to conclude with a recent result, which opens a new research direction. We have given in Section 6 various closure properties for varieties or even for C-varieties. The next result of Branco and the author [START_REF] Branco | Equations for the polynomial closure[END_REF] is much more general.

Theorem 9.1. If L is a lattice of languages closed under quotients, then Pol(L) is defined by the set of equations of the form x ω yx ω x ω , where x, y are profinite words such that the equations x = x 2 and y x are satisfied by L.

Work is in progress to extend the other results of Section 6 to this more general setting. The difficulty stems from the fact that definitions like V -1 W are no longer available in this context and one has to work directly on profinite identities.

Classical areaThe most important results on the concatenation product are due to Schützenberger. They concern the smallest Boolean algebra of languages closed under marked product or one of its variants.

In the literature, concatenation hierarchies are usually indexed by half integers, but it seems simpler to use integers.

support from the project ANR 2010 BLAN 0202 02 FREC.


Edy Veneziano
email: edy.veneziano@parisdescartes.fr

Unique properties and effects of conversation in acquisition Conversation and language acquisition: Unique properties and effects

We argue that conversational exchanges are a special case of input where converge unique properties that have a great potential for language acquisition, such as the motivation to communicate, the information about language meanings and structures, and the construction of new ways of expression. Results from the literature and from new data analyses, show that conversational exchanges have both immediate and long-term effects. Two properties are considered here to have a particularly great potential for learning. One is the facilitated access to unities of meaning underlying the successive transformations in utterance shapes, cognitively analogous to the discovery of physical and logico-mathematical invariances under the transformations of shape and configuration. The other is the co-construction of sequences that foreshadow behaviors still beyond the individual child's present capacities.

Conversation provides the primary setting for language acquisition, and it is in conversational settings that children display their emerging knowledge together with their skill in using a language Eve V. Clark (2009, p. 41) (1) Camille (1;10.12) and her mother 'have given bread swans'

Mother 8 : oui on a donné du pain aux cygnes nous hier 'yes, we have given bread to the swans yesterday'

Learning a language is a multitask activity that requires the mastery of many different strands, concomitantly and in a very quick manner. Children need to grasp the conventional sounds of the language as well as the meanings attributed to words and to larger constructions.

At the same time, they need to keep track of context, shared knowledge, prosodic hints, and past discourse in order to infer their partner's intentions and goals, and to produce utterances that effectively allow the partner to retrieve the child's own intentions and aims.

Conversations with knowledgeable and cooperative partners are very privileged settings where these acquisitions can take place. In (1) above, mother and child start having different aims and interests but after a few skillful turns by the mother, and the cooperative participation of the child, the partners' interests and focus of attention begin to converge, eventually reaching out into the shared recall of past experience.

Eve Clark has been a leading researcher in showing that the construction of common ground is essential to successful communication and can itself be built through conversation. In contrast to innate accounts of language acquisition that, at best, see the latter simply "triggered" by the input they hear, Eve Clark assumes that conversational exchanges offer children adequate information to learn the language. Through detailed analyses of naturalistic observations and ingenious experimental settings that keep the flavor of everyday experience, Eve Clark and her collaborators have shown how caregivers allow children to focus on the relevant information and get hold of the intricacies of the language, both as a system of meanings and rules, and as a means for communication (e.g., Chouinard & Clark, 2009;[START_REF] Clark | Acquisition in the course of conversation[END_REF]2010;Clark & deMarneffe, 2012).

This doesn't mean that children cannot simply learn from speech directed to them, or even from general input, just by overhearing language spoken around them (e.g., [START_REF] Akhtar | Learning words through overhearing[END_REF][START_REF] Gampe | Eighteen-month-olds learn novel words through overhearing[END_REF]. However, conversational exchanges are special experiences as they present several unique and facilitating properties concurrently.

In this chapter we will review the different properties that are specific to conversational exchanges: the motivation to communicate, the reciprocal information that partners can retrieve about each other and that can be updated in real time, the information about language and its use in real settings, as well as the co-construction inherent to their realization. We argue that the convergence of these properties confers to conversational exchanges a privileged status compared to other language experiences that children are exposed to. During the early stages of acquisition, conversations have a great potential to get the process of acquisition going and to facilitate children's first steps into the language system. Empirical evidence, based on results from the literature and from new data analyses, will be provided in support of this position.

The unique properties of conversational exchanges

Conversation is the natural site of communication. Hence, children are highly motivated to make themselves understood and to understand their partners. Since they have intentions and meanings to exchange with their partners, in conversation children are particularly likely to attend to their interlocutors' utterances, as well as to the effect that their own interventions have on them. This property fits well with the requirements of functional use approaches that consider language to be best learned in settings where children are motivated to use it and where adults talk about objects and events that are of interest to the children [START_REF] Tomasello | Constructing a Language: A Usage-Based Theory of Language Acquisition[END_REF].

Information about partners

Conversation is also the setting where caregivers and children get information about each other in real time, and where the two intertwined components of communication-production and comprehension-are alternatively solicited about the same topics. Caregivers can monitor children's understanding and production abilities, adjust their language to the way children talk, and respond to them. Children have the opportunity to see the effects that their utterances have on their caregivers, and to modify their way of talking as a function of this effect (e.g., [START_REF] Clark | First Language Acquisition. 2nd Edition[END_REF]Gallaway & Richards 1994, Snow & Ferguson 1977;[START_REF] Wales Shugar | Early child discourse analyzed in the dyadic interaction unit[END_REF].

Information about language meaning and structure

Within this optimal motivational and communicational context, children receive well-timed interpretations of their utterances in the form of expansions, reformulations and corrections, that provide information on vocabulary (phonological shape and semantics) and on morphosyntax, while creating opportunities to produce new, better-adjusted, utterances and to consolidate emerging expressions (e.g., [START_REF] Cazden | Child Language and Education[END_REF][START_REF] Chouinard | Adult reformulations of child errors as negative evidence[END_REF][START_REF] Clark | Constructing verb paradigms in French: Adult construals and emerging grammatical contrasts[END_REF][START_REF] Saxton | Negative evidence and negative feedback: Immediate effects on the grammaticality of child speech[END_REF][START_REF] Veneziano | Effects of conversational functioning on early language acquisition: When both caregivers and children matter[END_REF], 2009). In the course of conversation, adults also correct children's grammatical errors. Corrections can be explicit, but more commonly they are implicit, as in the case of reformulations (e.g., [START_REF] Chouinard | Adult reformulations of child errors as negative evidence[END_REF][START_REF] Farrar | Negative evidence and grammatical morpheme acquisition[END_REF][START_REF] Moerk | Positive evidence for negative evidence[END_REF][START_REF] Saxton | The contrast theory of negative input[END_REF][START_REF] Saxton | Negative evidence and negative feedback: Immediate effects on the grammaticality of child speech[END_REF][START_REF] Strapp | Mothers', fathers', and siblings' responses to children's language errors: Comparing sources of negative evidence[END_REF][START_REF] Veneziano | Effects of conversational functioning on early language acquisition: When both caregivers and children matter[END_REF]. Reformulations can be considered error detectors (e.g., [START_REF] Chouinard | Adult reformulations of child errors as negative evidence[END_REF]. Indeed, contingent corrections are likely to reveal the difference between children's and adults' productions and to offer children ideal opportunities for changing errors into more conventional forms (e.g., [START_REF] Saxton | Negative evidence and negative feedback: Immediate effects on the grammaticality of child speech[END_REF].

All conversationally contingent responses share the property that changes in form occur while meaning remains invariant. As [START_REF] Brown | The development of WH questions in child speech[END_REF] and [START_REF] Brown | The child's grammar from I to II[END_REF] put it, the transformations that utterances undergo "as they shuttle between persons in conversation" may ultimately be one of the most crucial features of conversations, providing the "richest data available to the child" for acquiring language (1969:72).

Information about language use

In conversation, children do not only learn about the language system, its lexicon and morphosyntactic rules, but also how to use linguistic resources to accomplish communicative acts in socially and culturally appropriate ways (e.g., [START_REF] Clark | First Language Acquisition. 2nd Edition[END_REF][START_REF] Veneziano | Conversation in language development and use: An introduction[END_REF]. They can learn that requests are made on the assumption that the speaker cannot carry out the object of the demand himself, that refusals should be justified (e.g., [START_REF] Dunn | Understanding others: evidence from naturalistic studies of children[END_REF][START_REF] Dunn | Development of justification in disputes with mother and sibling[END_REF][START_REF] Goetz | The development of verbal justifications in the conversations of preschool children and adults[END_REF][START_REF] Veneziano | Interactional processes in the origins of the explaining capacity[END_REF][START_REF] Veneziano | Functional changes in early child language: The appearance of references to the past and of explanations[END_REF], or that the speaker's utterances should take into account the degree of shared knowledge and "common ground" among the interlocutors (e.g., [START_REF] Clark | Pragmatics and language acquisition[END_REF][START_REF] Clark | Repetition as ratification: How parents and children place information in common ground[END_REF][START_REF] Gundel | Cognitive status and the form of referring expressions in discourse[END_REF][START_REF] Matthews | The effect of perceptual availability and prior discourse on young children's use of referring expressions[END_REF].

The emergence of new joint events

Compared to both CDS or input in general, conversations have another

unique property that has great potential for the acquisition of new language knowledge. As H. H. Clark puts it, "though conversations are created from individual utterances, they are more than the sum of their parts" (Clark, 1996:318). They are 'participatory acts' whose individual meaning derives from them being part of a joint action (ibid.). As a consequence, events that were not foreseen by the participants at the time they entered the conversation emerge from their joint interactional functioning. This property fits well with a psychogenetic constructivist account of language acquisition based on Piaget's epistemology. One of its central tenets is that the acquisition of new knowledge results from a progressive construction growing out of the possibilities opened up by the functioning of earlier adapted behaviors [START_REF] Piaget | L'évolution des Possibles chez l'Enfant[END_REF][START_REF] Piaget | L'évolution des Possibles chez l'Enfant[END_REF].

Accordingly, behaviors of level n+1 are considered to build upon behaviors typical of level n, the current level of functioning (e.g., [START_REF] Piaget | Psychogenèse et histoire des sciences[END_REF][START_REF] Piaget | Psychogenèse et histoire des sciences[END_REF], in such a way that the apparent discontinuities of structures result from underlying continuities in the processes of development [START_REF] Piaget | Genèse et structure en psychologie de l'intelligence[END_REF][START_REF] Piaget | Genèse et structure en psychologie de l'intelligence[END_REF]).

In early language acquisition, the realization of successive single-word utterances, a transitional phenomenon between single-word and two-word utterances, illustrates this property particularly well [START_REF] Bloom | One Word at a Time[END_REF][START_REF] Greenfield | The structural and functional status of single-word utterances and their relationship to early multi-word speech[END_REF][START_REF] Scollon | A real early stage: An unzippered condensation of a dissertation on child language[END_REF][START_REF] Veneziano | From one word to two words: Repetition patterns on the way to structured speech[END_REF]Veneziano, 1999, in press):

(2) Gael (1;10.17) holds a plastic chip that he places in front of a toy cow.

Child 1 : /su/ 'coin' (money)

Mother 1 : tu le donnes à qui le sou?

'to whom do you give the coin?'

Child 2 : /vaS/ 'cow' [START_REF] Veneziano | A cognitive-pragmatic model for the change from single-word to multiword speech: A constructivist approach[END_REF] In this particular kind of sequence, the child produces two single word utterances ('coin' and 'cow') that refer to different aspects of one event within a short period of time. The conversational framework within which these two utterances occur allows children to talk about two different aspects of the situation without planning their production beforehand, since the second single-word utterance in the sequence ('cow') is uttered answering a question asked by the mother. In this way, by simply following the turns of the conversation, children enrich their initial focus of attention and pave the way towards the production of multiword utterances [START_REF] Caron-Pargue | Early lexical, morphological and syntactic development in French: Some complex relations[END_REF][START_REF] Veneziano | A cognitive-pragmatic model for the change from single-word to multiword speech: A constructivist approach[END_REF].

The effects of conversational exchanges

Immediate effects: Continuing the topic of the conversation Does the conversational response of one partner produce further responding on the same topic by the other? This effect was found in some earlier studies (e.g., [START_REF] Folger | A pragmatic analysis of spontaneous imitations[END_REF][START_REF] Tomasello | Joint attention and lexical acquisition style[END_REF]. In new analysis of prior longitudinal recordings, I found additional support for this immediate effect of conversations. The longitudinal recordings came from six Hebrew-acquiring children, followed from the age of 11 to 20 months, recorded once a month in everyday interaction with their mothers [START_REF] Veneziano | Structural and formal precursors of language: an interactional approach[END_REF][START_REF] Veneziano | Vocal-verbal interaction and the construction of early lexical knowledge[END_REF].

Results show that children are three times more likely to stay on topic after their mother's responses to their previous interventions than after the mother's utterances that initiated a topic (see χ 2 (1,N=1285)=114.38, p<.001). The higher response of children to mothers' turns that are themselves a response to the child, may also be related to the fact that these responses place the word (or word approximation) uttered by the child in a focalized position in the turn.

The mother's response may contain only that word, or emphasize it by separating it from the rest of the utterance. In (3) below, the mother's turn contains only the repeated interpretation of the child's word approximation:

(3) Yuval (1;3) is trying to pull apart a toy drum. 'it sting(s)' [START_REF] Veneziano | From one word to two words: Repetition patterns on the way to structured speech[END_REF] In both examples, the child's utterance in the third turn not only remains on topic but is also more adequate than the initial production.

In the Hebrew study mentioned above, focalization was present in 39% of all mothers' turns, but in as many as 76% of the mother's responses that related to the child's previous production (Veneziano, 1988: 136). Children were also more likely to relate to focalized than to non-focalized words: 26.5% of focalized words and only 14.7% of nonfocalized ones were picked up by the children, a statistically significant difference (p<.05 ;Veneziano, 1988: 138-139). Repetition of a lexical item didn't have the same effect, as children were just as likely to pick up words that were repeated in the mother's turn than words that were not repeated (19.7 vs. 19.1%, respectively) (Veneziano, 1988: 139).

These results suggest that focalization is a particularly effective property In other words, partners influence each other mutually. When either the mother or the child takes the first step in topic-related responding, joint conversational activity is enhanced, resulting in sequences of topic-related turns. Such extended on-topic conversations provide children with the opportunity to compare their own productions to their mother's, and to then modify their utterances towards a better match to targets (e.g., [START_REF] Chouinard | Adult reformulations of child errors as negative evidence[END_REF][START_REF] Otomo | Maternal responses to word approximations in Japanese children's transition to language[END_REF].

Immediate effects: Increased matching

During extended conversational exchanges children modify their verbal productions (e.g., [START_REF] Chouinard | Adult reformulations of child errors as negative evidence[END_REF][START_REF] Bertin | Rôle des reprises dans l'acquisition de la morphosyntaxe chez des enfants francophones âgés de 2-3 ans. 12e Colloque de Logopédie[END_REF].

Modifications can occur in the phonological shape (as in (3) above) and/or in the semantics of target words, as well as in the grammatical structure of the utterance, as in (4) above and (5) below:

(5) Sophie ( 2 [e]want play outside [START_REF] Bertin | Rôle des reprises dans l'acquisition de la morphosyntaxe chez des enfants francophones âgés de 2-3 ans. 12e Colloque de Logopédie[END_REF] In the longitudinal data of six Hebrew-acquiring children mentioned above, Veneziano (2005) analyzed children's consecutive productions to see whether utterances occurring later in the exchange were more ontarget than initial utterances. Excluding sequences where the child's initial production was already on target, it was found that before 14 months children very rarely modified their productions. In contrast, between 14 and 17 months, they improved their utterances on average in 34% of the conversational exchanges that contained two or more child turns (individual children's values ranged between 21% and 50%).

Modifications also occur when the mother doesn't understand the child's utterance and demands to clarify it with a repair-initiating sequence [START_REF] Schegloff | Repair after next turn: The last structurally provided defence of intersubjectivity in conversation[END_REF]. By requesting clarification, caretakers let children know that they need to revise their initial utterance (e.g., [START_REF] Saxton | Negative evidence and negative feedback: Immediate effects on the grammaticality of child speech[END_REF] and children, not yet 2;0, respond to these requests by changing it or offering the required additional information [START_REF] Anselmi | Young children's responses to neutral and specific contingent queries[END_REF]Golinkoff, 1993;[START_REF] Marcos | Reformulating requests at 18 months: Gestures, vocalisations and words[END_REF][START_REF] Saxton | Negative evidence and negative feedback: Immediate effects on the grammaticality of child speech[END_REF][START_REF] Chouinard | Adult reformulations of child errors as negative evidence[END_REF]. Modifications occur also when caregivers misinterpret children's intentions [START_REF] Chouinard | Adult reformulations of child errors as negative evidence[END_REF][START_REF] Golinkoff | I beg your pardon?': The preverbal negotiation of failed messages[END_REF][START_REF] Marcos | Reformulating requests at 18 months: Gestures, vocalisations and words[END_REF]. In the longitudinal study of one child between 1;6 and 2;3, [START_REF] Saxton | Negative evidence and negative feedback: Immediate effects on the grammaticality of child speech[END_REF] noted that, after reformulations and clarification requests, the child corrected the morphological form of verbs more often once the knowledge of that form was emerging, producing it correctly 50% of the time.

Conversational exchanges and, in particular, reformulations and clarification requests, thus have the effect of stimulating more conventional productions from the children. The extent of the modifications is limited, however, by the children's developmental level and by their language knowledge [START_REF] Saxton | Negative evidence and negative feedback: Immediate effects on the grammaticality of child speech[END_REF].

Long-term effects of conversational exchanges

Conversational exchanges also have long term effects. Several studies reported positive correlations between reformulations and recasts by caregivers, and MLU, noun phrase elaboration, grammatical morphemes and number of verb phrases and auxiliaries per utterance [START_REF] Barnes | Characteristics of adult speech which predict children's language development[END_REF][START_REF] Farrar | Negative evidence and grammatical morpheme acquisition[END_REF]Gleitman, Newport & Gletiman, 1984;[START_REF] Hoff-Ginsberg | Some contributions of mothers' speech to their children's syntactic growth[END_REF]. In training studies, reformulations and recasts have been found to have a positive effect on children's acquisition of the grammatical structures that were recasts, particularly on verbal constructions [START_REF] Nelson | Syntax acquisition: Impact of experimental variation in adult verbal interaction with the child[END_REF][START_REF] Nelson | Facilitating children's syntax acquisition[END_REF] and on passive structures [START_REF] Baker | Recasting and related conversational techniques for triggering syntactic advances in young children[END_REF]. [START_REF] Saxton | The contrast theory of negative input[END_REF] found that 20 exposures to corrective reformulations were enough for 5-yearolds to learn the past irregular tense of unfamiliar verbs. However not all studies were able to confirm the positive effect of reformulations on later language acquisition [START_REF] Cazden | Child Language and Education[END_REF][START_REF] Ellis | Enabling factors in child-adult discourse[END_REF].

As discussed earlier, conversations do not only involve the caregiver's responses to the child-they also involve the active participation of the children. Their responses to caregivers are part and parcel of language acquisition while providing, at the same time, information about and evidence of children's attention to caregivers' turns. In the early stages of acquisition, children's imitative uptakes of words produced by mothers are positively correlated with their lexical acquisition [START_REF] Nelson | Cookie versus do-it-again: Imitativereferential and personal-social syntactic-initiating language styles in young children[END_REF][START_REF] Rodgon | Vocal and gestural imitation in children under 2 years old[END_REF][START_REF] Snow | Imitativeness: A trait or a skill? In The Many Faces of Imitation In Language Learning[END_REF]. [START_REF] Bloom | Imitation in language development: If, when and why[END_REF] and [START_REF] Ramer | The function of imitation in child language[END_REF] showed that children differ in the extent to which they imitate; however, for all children, the majority of imitations involved words they didn't use spontaneously. In a study of the longitudinal data of the six Hebrew-acquiring children mentioned above, [START_REF] Veneziano | Echanges conversationnels et acquisition première du langage[END_REF][START_REF] Veneziano | Effects of conversational functioning on early language acquisition: When both caregivers and children matter[END_REF] showed that words imitated by the children, repeated or reformulated by their mother, or both, were produced as conventional word forms at later sessions. Moreover, at later sessions, these productions were recognized as meaningful words by the mother, and solicited comments that advanced the theme two to three times more often than words appearing in that session for the first time.

Slobin (1968) stated that sequences in which children imitate mothers' expansions and reformulations have great relevance for early language acquisition, and [START_REF] Chouinard | Adult reformulations of child errors as negative evidence[END_REF] have shown that children's responses to mothers' reformulations are an extremely valuable source of information on the attention that children bring to bear on mothers' reformulations. However little work has been done to assess the specific impact of extended discourse of this kind compared to discourse where mothers' expansions and reformulations are not followed by children's response to them. In another study of the Hebrew data mentioned above [START_REF] Veneziano | Echanges conversationnels et acquisition première du langage[END_REF], sequences in which mothers' reformulations (including repeats and expansions) were followed by the children's repetition of the word focused upon by mothers were distinguished from mothers' reformulations that were not followed by children's repeats. For each mother-child dyad, these sequences were identified and measured at 14 months, when the six children had a similar number of words in their repertoire. Three months later, the number of words in the children's repertoire varied, with gains ranging from 11 to 48 words. Results showed that sequences in which children responded imitatively to their mother's reformulations at 14 months correlated positively and significantly with gains in vocabulary measured at 17 months; in contrast, mothers' reformulations that were not followed by children's responses didn't correlate with those gains (Table 3).

Overall mothers' reformulations 0.794 n.s. [START_REF] Veneziano | The acquisition of early verbs in French: Assessing the role of conversation and of childdirected speech[END_REF]. The study was meant to investigate whether caregivers' talk could explain the verb forms children use during the period in which they produce verbs in one form only, a phenomenon found for languages with limited inflectional morphology like English, but also for languages with rich inflectional morphology, such as Hebrew, Turkish and Spanish, as well as moderate inflectional morphology like French [START_REF] Bassano | Early development of nouns and verbs in French: exploring the interface between lexicon and grammar[END_REF][START_REF] Armon-Lotem | The emergence of grammar: Early verbs and beyond[END_REF][START_REF] Aksu-Koç | The role of input vs. universal predispositions in the emergence of tense-aspect morphology: Evidence from Turkish[END_REF][START_REF] Gathercole | The early acquisition of Spanish verbal morphology: Across-the-board or piecemeal knowledge?[END_REF][START_REF] Laaha | Typological Perspectives on the Acquisition of Noun and Verb Morphology[END_REF]Tomasello, 1992;[START_REF] Veneziano | From one word to two words: Repetition patterns on the way to structured speech[END_REF][START_REF] Veneziano | The changing status of "filler syllables" on the way to grammatical morphemes[END_REF]. The two children of the study were acquiring Swiss French and were in the single-form period until 1;11 for the girl and 2;3 for the boy. For example, they used /ka'se/ (to break/broken) for the verb casser 'to break' and /tuRn/ (turn/turns) for the verb tourner 'to turn'. Authors first analyzed CDS and showed that verb forms that mothers used most frequently explained 64% and 80% of the verb forms used by the two children, respectively. Then, they analyzed the degree of correspondence between the forms used by mothers and children when they were talking about jointly attended events. For about half of the This study shows that information present in conversational exchanges can be more powerful than information provided by CDS alone. Moreover, the residue of unexplained verb forms reminds us that children have their own ideas and individual preferences (Shirai, 1998) that can override information contained in both CDS and conversational exchanges.

Concluding remarks

Conversational exchanges are a particular kind of child-directed speech and a special case of input where various unique properties that have a great potential for language acquisition converge. Children are active participants, motivated to understand and to make themselves (Piaget & Inhelder, 1941[START_REF] Bloom | Imitation in language development: If, when and why[END_REF], transformations that utterances undergo 'as they shuttle between persons in conversation' can help children acquire grammar (Brown et al., 1969: 72).

The other important property of conversational exchanges is that they are co-constructed through the turns contributed by each What is accomplished in conversations is thus "more than the sum of the parts" (Clark, 1996: 318). It is a new event that was neither planned beforehand nor foreseen by the participants at the time they entered the conversation. This property allows, for example, the production of successive single-word utterances, where utterances containing only one word are meaningfully related to each other through the unfolding of the conversation [START_REF] Veneziano | A cognitive-pragmatic model for the change from single-word to multiword speech: A constructivist approach[END_REF]. Successive single-word utterances foreshadow the advent of a new behavior-multiword speech-by practicing well-mastered behaviors typical to the present level of knowledge-single-word speech. This process corresponds to a constructivist principle contained in Piaget's epistemological theory of developmental change (see, e.g., [START_REF] Piaget | Psychogenèse et histoire des sciences[END_REF], according to which discontinuities in the content of knowledge result from underlying continuities in the processes of acquisition: a progressive construction in which earlier acquisitions provide essential releasing steps (see also [START_REF] Gréco | Réduction et construction[END_REF].

Another central tenet of Piaget's psychogenetic constructivism is that the acquisition of knowledge depends, on the one hand, from cognitive mechanisms of acquisition at the subject's disposal, and on the other hand, from the way the object is presented to the subject. Society cannot operate on the former but can modify the latter, and in particular the relation between the subject and the object to be known (e.g., Piaget & Garcia, 1983: 295). Child-directed speech, and language not addressed to children, both contain relevant information for language learning and children can learn from them. However, conversational exchanges, where many different facilitating properties converge, may be the optimal way in which language can be presented to the learning child, as well as the most powerful resource in the early stages of language acquisition and at all those critical points where new knowledge is being acquired.

  Mother 1 : c'est quoi ces oiseaux là? [pointing at image of swans on book] 'what are these birds there?' Child 1 : les oiseaux ils volent 'the birds they fly' Mother 2 : comment ils s'appellent ces oiseaux là? 'how are they called these birds there?' Child 2 : regarde les oiseaux ils volent 'look the birds they fly' Mother 3 : oui les oiseaux ils volent mais ceux-là ils volent pas ils nagent là [pointing at image of swans on book] 'yes the birds they fly, but these do not fly, they swim there' Child 3 : hein? Mother 4 : ils nagent ceux-là, ils volent pas # hein? ## ils sont dans l'eau [CHI looks at image and MOT alternatively]## c'est des cygnes? 'those swim, they don't fly # hein? ##they are in the water, they are swans?' Child 4 : nh [confirmation] [%act: looking at image on the book] Mother 5 : t'en a déjà vu toi des cygnes #1.6 où c'est que t'as vu des cygnes toi? 'you have seen already swans you #1.6 where have you seen swans you?' Child 5 : dans l'eau 'in the water' Mother 6 : oui ils nagent dans l'eau les cygnes ## on en a vu au bord du lac nous? ## on avait donné du pain 'yes they swim in the water ## we have seen them on the lake?## we had given them bread?' Child 6 : oui %tra: yes Mother 7 : nh? tu te rappelles? 'nh? do you remember?' Child 7 : edonné pain cygnes [turning towards OBS]

  of mothers' responses to children's utterances, and is quite likely involved in the topic-continuation effect of the conversations discussed above. Are mothers affected by the responses of their children? The Hebrew data of the longitudinal study mentioned above were reanalyzed to address this question more precisely. Results show that mothers were also more likely to stay on topic after children's responses to their previous interventions than after children's utterances that initiated a topic (

  children's verb forms, the information from CDS and conversational exchanges converged: the verb forms used by the children corresponded to the dominant forms used in CDS and were also used by both mothers and children in joint conversational exchanges. Among the remaining children's verb forms, three quarters corresponded exclusively to those used jointly by mothers and children in conversations. Fewer than 15% of these verbs corresponded exclusively to the dominant forms in CDS. The residue was neither explained by CDS nor by conversation.

  understood, and very likely to attend to what is being said to them. Moreover, Western middle class caregivers tune their conversation to the interests of their children, and often relate to what children say and are attending to. At the early stages of language acquisition, conversational exchanges offer children many facilitating features for learning language while they keep pursuing desired activities and goals. Results discussed above show that conversational exchanges have both immediate and long-term effects. They have the effect of stimulating further on-topic conversation by mothers and by children, to solicit modifications of the children's production, and to widen the number of aspects of a situation or intention that can be talked about. They also highlight the importance of joint co-constructed activity: what matters is not so much what each partner does individually but what mothers and children do together, the activity of one boosting that of the other, and vice versa. This conclusion is supported by findings concerning the specific effect of children's response to mothers' reformulations for word learning and for the transition to articulated speech. Two properties of conversational exchanges stand out as having a particularly great potential for learning. One is the fact that, in conversational exchanges, caregivers interpret, reformulate or expand their children's productions, and children are likely to continue relating to these interpretations and reformulations. In such conversations, meanings are the invariants of transformations in utterance forms, like physical matter, weight or number are the invariants of the transformations in shape. As transformations of shape help children discover physical invariances and the concept of conservation

  participant. Although participants are in control of their contributions, each turn opens up new possibilities to the speakers, depending on what was said earlier and on the expectations of what the partner may do next.

Table 1

 1

	).

Table 1 .

 1 Mean percentage of on topic response by children at

	three age periods, according to the type of mother's intervention
	(number of responded interventions in parentheses)
	At each developmental period, 2x2 contingency tables were
	constructed for children's on-topic and not-on-topic responses to the two
	types of turns (mother's initiations and mother's responses to the child),
	for the six children together. At each of the three age periods, children's
	on-topic responses were significantly related to mothers' responses to

the child (at 11-13 months: χ 2 (1,N=1478)=57.51, p<.001; at 14-15 months: χ 2 (1,N=1970)=222.48, p<.001; at 16-17 months:

Table 2

 2

	).
		Mean % of Mothers response to
		Child's interventions
	Age periods	Child's topic initiation	Child's response to Mother
	11-13 months	10.8% (108)	44.7% (93)
	14-15 months	14.7% (194)	53.8% (194)
	16-17 months	19.4% (205)	48.8% (173)

Table 2 .

 2 Mean percentage of on topic response by mothers at three age periods of their children according to the type of child's intervention (number of responded interventions in parentheses).

	Also here the relation was tested at each developmental period
	with 2x2 contingency tables presenting mothers' on-topic and not on-
	topic responding to the two types of children's turns (children's
	initiations and children's responses to the mother), for the six children
	together. At each of the three age periods, mothers' on-topic responses
	were significantly related to children's responses to the mother (at 11-13

months: χ 2 (1,N=1194)=154.38, p<.001; at 14-15 months: χ 2 (1,N=1671)=250.61, p<.001; at 16-17 months : χ 2 (1,N=1392)=134.42, p<.001).

Table 3 .

 3 Correlations between mothers' reformulations at 14 months and children's gains in vocabulary occurring between 14 and 17 months, for

	three types of mothers' reformulations: (1) total reformulations, (2)
	reformulations followed by children's response, and (3) reformulations not
	followed by children's response.
	Child-directed speech and conversational exchanges
	Caregivers' talk in conversational exchanges is a particular kind of CDS
	that is closely related to children's focus of attention, to what children
	say and to how they say it. Both CDS and caregivers' talk in
	conversation are part of the input. Often input, CDS and caregivers' talk
	in conversational exchanges are confounded in studies of the effects of
	the environment on language acquisition. In a recent study of children's
	early verbs, the specific contributions of CDS and conversational
	exchanges were assessed