Yassine Hachaïchi
email: hachaichi.ens@gmail.com

Logic for Unambiguous Context-Free Languages

Keywords: Descriptive complexity, logic and language theory, implicit definability on finite models

We give in this paper a logical characterization for unambiguous Context Free Languages, in the vein of descriptive complexity. A fragment of the logic characterizing context free languages given by Lautemann, Schwentick and Thérien based on implicit definability is used for this aim. We obtain a new connection between two undecidable problems, a logical one and a language theoretical one.

Introduction

A language L over an alphabet A can be defined by several manners. The most famous are:

(1) a subset of A * whose elements satisfy some given property; it is the analogous of comprehension schema in set theory, (2) a subset of A * whose elements are generated by some formal grammar, (3) a subset of A * whose elements are recognized by some model of computation.

In complexity theory, we try to classify languages according to the recognizer used (finite automata, push down automata, • • •), or by the ressources (time, space, • • •) neded by some model of computation (turing machine, random access machine, • • •), see [START_REF] Papadimitriou | Computational complexity[END_REF] for a detailed introduction to the field.

One of the aims of descriptive complexity [START_REF] Ebbinghaus | Finite model theory[END_REF][START_REF] Straubing | Finite automata, formal logic, and circuit complexity[END_REF] is to evaluate how easy or hard it is to express a given property defining some language (as in 1 above) in the language of logic.

The answer to this question got a meaning by the works of Büchi [START_REF] Üchi | Weak Second-Order Arithmetic and Finite Automata[END_REF] and Elgot [START_REF] Elgot | Decision problems of finite automata design and related arithmetics[END_REF] who made the link between formal logic and formal language theory. This connection was made by identifying words to finite logical structures.

Their result was that a word language is regular if, and only if it is the class of models of some Monadic Second-order sentence. Two questions were naturally asked:

The first one is:

(1) What is the expressive power of Monadic Second-order Logic on other structures than words, graphs and trees for example?

The other question is: (2) Is there a logical description for each known class of words: star free, context free, . . .?

Both directions were explored since, we will recall some results in the next section.

The logical description of the behaviour of computational models was also taken up in complexity theory. Starting with Fagin's work, it was shown that many complexity classes such as NP, P, LogSpace, NLogSpace, Pspace, • • • could be characterized by different varieties of second-order logic (involving for example fixed point logic or transitive closure operator). For an introduction to this field see Ebbinghaus and Flum's book [START_REF] Ebbinghaus | Finite model theory[END_REF].

In [START_REF] Hacha Ïchi | A descriptive complexity approach to the linear hierarchy[END_REF] and [START_REF] Hacha Ïchi | Fragments of monadic second-order logics over word structures[END_REF], I used some generalized quantifiers of comparison of cardinality, to get a new logical characterizations of the class of rudimentary languages in the scope of descriptive complexity. Lautemann, Schwentick and Thérien [START_REF] Lautemann | Logics for context-free languages[END_REF] gave recently a logical description of Context Free Languages. They used for this purpose the semantic quantifier of matching.

Our contribution in this paper is, in a first time, using a result of McNaughton and Papert [START_REF] Mcnaughton | Counter-Free Automata[END_REF] we will refine an algebraic normal form of Chomsky and Schützenberger which characterizes Context Free Languages using the Dyck languages.

The Second result of this paper is a description of Unambiguous Context Free Languages. This description uses a fragment of a logic built from first-order implicitely definable predicates introduced by Kolaitis [16]. This logic was motivated by the failure of the Beth property when we confine ourselves to finite structures.

This paper is organized as follows:

In the next section we give some background of language theory and logic, and we introduce some results of descriptive recognizability. We introduce in the last subsection the result of Lautemann and al [START_REF] Lautemann | Logics for context-free languages[END_REF].

In section 3 we refine an algebraic normal form given by Chomsky and Schützenberger [START_REF] Schutzenberger | ALGEBRAIC THEORY OF CONTEXT-FREE LANGUAGES[END_REF], for describing Context Free Languages using the Dyck language.

In section 4 we give the logical characterization of unambiguous context free languages.

In the conclusion we try to link undecidability of unambiguity and undecidability of the logic IM P .

Notations and Background

We give here some definitions and results in formal language theory, logic and the connection between them.

For the rest of the section Σ will denote a finite vocabulary {c 1 , . . . , c s }. A language is a subset of Σ * , which is the set of finite words on Σ.

Formal Language Theory

We will recall in this section some notions of language theory, from the grammatical point of view, which we will use later in this paper, the curious reader can find more details on this area in Harrison's book [START_REF] Harrison | Introduction to formal language theory[END_REF].

A context free grammar is a 4-tuple < Σ, N, S, P > such that:

• Σ and N are finite disjoint sets, called respectively the set of terminal and non-terminal symbols, • S is a special symbol of N , called the start symbol or the axiom of the grammar, • P is a set of productions of the form X → w, where X is a non-terminal and w ∈ (Σ ∪ N ) * .

If we replace each non-terminal symbol by a new symbol | not in Σ ∪ N in the right-hand side of a production we obtain a string called the pattern of the production.

A context free grammar is regular if all productions are of the form X → w|wY where X and Y are non-terminals and w ∈ Σ * .

We define the (one step) derivation rule ⇒ G for a grammar G by

w 1 Xw 2 ⇒ G w 1 ww 2 is a derivation if and only if X → w ∈ P .
The reflexive and transitive closure of

⇒ G is denoted * ⇒ G .
A language L ⊆ Σ * is context free (resp. regular) if and only if there is a context free (resp. regular) grammar which derives it from S, i.e

L = L(G) = {w ∈ Σ|S * ⇒ G w}.
A language is star free if it is build from finite languages by only boolean operations and concatenation.

The derivation tree of a word w associates naturely to the derivations made from S until reaching w.

Formally, a derivation tree of a word w ∈ L(G) is a tree so that :

• the root is labelled by the start symbol S,

• the leaves are labelled by terminals,

• the internal nodes are labelled by non terminals,

• the passage from an internal node to its sons corresponds to a production,

• the lecture of leaves from left to right give w.

Example Let's take the grammar

G =< {a, b}, {X 0 , X 1 , X 2 , X 3 , X 4 }, X 0 , P >
where P contains the following productions:

P 0,1 : X 0 → aX 1 X 2 ba P 1,1 : X 1 → aX 3 X 2 b P 2,1 : X 2 → aab P 2,2 : X 2 → ab P 3,1 : X 3 → ab
Let w = aaababbaabba the word with derivation tree given in figure 1.

A context free grammar is unambiguous if every word in L(G) has a unique derivation tree.

A context free language is unambiguous if it has an unambiguous context free Fig. 1. A derivation tree of w grammar which derives it.

Logic

As we mentioned in the introduction, we can identify words to finite models in a special logical signature τ Σ = {<, P c 1 , . . . , P cs }.

In this introductory section to logic we define formally the word model and some logics that we will use in the forthcoming sections.

We will confine ourselves to finite structures and especially to words.

Let Σ = {c 1 , . . . , c s } be a finite vocabulary. We associate with a word w = a 1 . . . a n over Σ, the word model S w , namely the relational structure S w = ({1, ..., n}, <, P c 1 , . . . , P cs ), where < is the natural order on {1, ..., n} and P a is the unary predicate collecting the positions of w labelled a:

P a = {i ∈ N |a i = a}.
For example let's take the word w = aabbabb on the vocabulary Σ = {a, b}.

The corresponding logical structure will be:

S w = ({1, 2, 3, 4, 5, 6, 7}, <, P w a = {1, 2, 5}, P w b = {3, 4, 6, 7}).
The set of first-order formulas (on words), F.O., is built inductively from atomic formulas of the form:

x < y and P a (x) for a ∈ Σ.

by means of connectives ∧, ∨, →, ↔, and ¬ and the quantifiers ∃ and ∀.

Formally:

(1) If x, y are any variable symbol or constant symbol then x < y and P a (x) for a ∈ Σ are first-order formulas.

(2) If ϕ, ψ are first-order formulas then

ϕ ∧ ψ, ϕ ∨ ψ, ϕ → ψ, ϕ ↔ ψ, and¬ϕ
are also first-order formulas. (3) If ϕ is a first-order formula and x is a variable then ∃xϕ, and ∀xϕ are first-order formulas.

Monadic second-order logic, M.S.O., is built like first-order logic where we add X i (x) to atomic formulas (the first item in the first-order construction), for some unary variables (X i ) i∈N and can quantify over X ′ i s (in the last item of the first-order construction).

A language L is said to be (explicitly) definable in a logic λ if and only if there exists a formula ϕ ∈ λ such that:

∀w ∈ A * (w ∈ L ⇔ S w |= ϕ).
Most classical model theoretical results fail when we confine ourselves to only finite models [START_REF] Ebbinghaus | Finite model theory[END_REF], especially Beth's theorem.

Let R be an n-ary relation symbol not in τ Σ . An F.O. [τ Σ ∪ {R}] sentence, ϕ, defines R implicitly if every word structure has at most one expansion (S w , R) to a τ Σ ∪ {R}-structure satisfying ϕ. The Beth's theorem says that a predicate is implicitly definable in F.O. if and only if it is explicitely definable in F.O., in the class of all structures (finite and infinite).

The failure of the Beth property for finite models, (see [START_REF] Ebbinghaus | Finite model theory[END_REF] for all properties of (classical) model theory that fail in finite model theory), stimulated Kolaitis [START_REF] Kolaitis | Implicit definability on finite structures and unambiguous computations[END_REF] to define a logic of implicitly defined queries in some logic.

We will only use the case of first-order implicitely defined queries.

Remark. We use a different definition from the one used by Kolaitis in [START_REF] Kolaitis | Implicit definability on finite structures and unambiguous computations[END_REF]. For a discussion see [7, page 213] The logic IM P = IM P (F.O.) is the set of formulas, that allows to define exactly those queries (properties) that are expressible in F.O. using first-order implicitely definable queries.

Formally:

An IM P -formula ϕ(x) is a tuple, (ψ 1 (R 1 ), . . . , ψ m (R m ), ψ(x, R 1 , . . . , R m ))
where all ψ ′ i s are first-order sentences on τ Σ ∪ {R i }, and ψ is first-order on

τ Σ ∪ {R 1 , . . . , R m } such that |= f in ∃!R 1 . . . ∃!R m (ψ 1 (R 1 ) ∧ . . . ∧ ψ m (R m )).
Where |= f in means satisfiability on finite models, and ∃! means there is a unique.

The meaning of ϕ(x) is fixed by requiring that:

S w |= ∀X 1 . . . ∀X m (ψ 1 (X 1 ) ∧ . . . ∧ ψ m (X m )) → ∀x(ϕ(x) ↔ ψ(x, X 1 , . . . , X m ))
This means:

S w |= ϕ(a) ⇔ S w |= ψ(a, R 1 , . . . , R m )), where the R ′ i s are uniquely determined by S w |= ψ i (R i ).
If we use only unary predicates we will denote this logic IM P (1).

Logic vs. Language theory

We will give in this section some results, in chronological order of their publications, on logical characterization of classes of languages, and the link between logical complexity and recognizability complexity.

Theorem 1 (Büchi [4], Elgot [9] and Lacroix [17]) A language is regular if and only if it is definable in monadic second-order logic if and only if it is definable in IMP(1).

Thomas improved the result of Büchi and Elgot to formulas of the form ∃P F.O. where P is a monadic predicate.

The connection between trees and words was given by Mezei and Wright, for a comprehensive proof and a definition of regular tree languages see [START_REF] Gcseg | Tree languages. In : Handbook of formal languages[END_REF].

Theorem 2 (Mezei and Wright [20]) A word language is context free if and only if the set of the derivation trees of its words is regular.

And a new description of regular tree languages in the same vein as Büchi's result arises, Theorem 3 (Doner, Thatcher and Wright [6,24]) A tree language is regular if and only if it is definable in monadic second-order logic.

First-order logic, the most natural sublogic of monadic second-order logic, on words was studied by McNaughton, for more details see [START_REF] Straubing | Finite automata, formal logic, and circuit complexity[END_REF].

Theorem 4 (McNaughton and Papert [19]) A language is star free if and only if it is definable in first-order logic.

Fagin studied the Existensial fragment of Second-order Logic and proved: Theorem 5 (Fagin [START_REF] Fagin | Generalized first-order spectra and polynomial time recognizable sets[END_REF]) Languages definable in existential second-order logic are exactly those computable in polynomial time by a non deterministic Turing machine.

This result is true for all finite relational structures not only for word structures.

Theorem 6 (Thomas, Perrin and Pin [25]) A star free set is of dot depth n if and only if it is definable in the boolean closure of Σ n , Where Σ n is the set of first-order formulas allowing n alternations of quantifiers (universal, existential).

A recent result of Eiter and al [START_REF] Eiter | Existential secondorder logic over strings[END_REF], which says that every Existential Secondorder prefix class either describes only regular languages or describes an NPcomplete problem. I suggest to curious readers to see the expository papers of Thomas [START_REF] Thomas | Languages, automata, and logic, Handbook of formal languages[END_REF], or Pin's one [START_REF] Pin | Logic, semigroups and automata on words[END_REF] for more details and results.

Matching vs. Context free languages

In this section we recall a result of Lautemann, Shwentick and Thérien for the description of Context Free Languages using the semantic quantifier of Matching.

Definition 7 A binary relation M is called a matching if it satisfies the following conditions :

(

1) ∀ij[(i, j) ∈ M ⇒ i < j] . (2) ∀ij[(i, j) ∈ M ⇒ ∀k ̸ = i, j ((i, k), (k, i), (j, k), and(k, j) are not in M )]. (3) ∀ijkl[(i, j), (k, l) ∈ M ⇒ (i < k < j → i < l < j)].
We will denote by ψ(M ), the conjunction of these three first-order items on τ ∪ {M }.

Let Match denote the class of matchings on word structures.

∃M atch ϕ means : there exists a relation M ∈ M atch such that < S, M >|= ϕ.

In order to define any non regular language, one have to go beyond M.S.O. Logic. On the other hand, existential quantification over a simple binary relation express all context free languages and some N P -complete languages by the result of Eiter and al [START_REF] Eiter | Existential secondorder logic over strings[END_REF], their result says that any prefix class of Existential Second-order Logic either expresses only regular languages or expresses some N P -complete language.

Moreover they proved that N P -hardness is present with a sentence ∃Rϕ where R is a binary predicate and ϕ is first-order of the appropriate form.

Lautemann and al [START_REF] Lautemann | Logics for context-free languages[END_REF] choose a semantical approach for this purpose, in which they restrict the second-order quantifier to range over the class of matchings, Match. They define the class ∃M atch F.O. to consist of all those sets L of τ -structures for which there is a first-order sentence ϕ over τ ∪ {M } such that, For every τ -structures S w : S w ∈ L if and only if, there is some matching M over S w such that < S w , M >|= ϕ.

They proved the following:

Theorem 8 (Lautemann, Schwentick and Thérien [18]) A language L is context free if and only if it is definable by a formula of the form ∃M atch ϕ

where ϕ ∈ F.O.

The result remains true also for ϕ ∈ M.S.O.

For proving this result, the first step was to construct a first-order sentence over τ ∪ {M } for each grammar G, which holds for a word structure S w if and only if there is a G-derivation tree T of w, and there is an effective way to construct the matching from the tree, and vice versa.

For the other direction they combined results of Doner [START_REF] Doner | Tree acceptors and some of their applications[END_REF], Thatcher and Wright [START_REF] Thatcher | Generalized finite automata theory with an application to a decision problem of second-order logic[END_REF] and Mezei and Wright [START_REF] Mezei | Algebraic automata and context-free sets[END_REF] to have the fact: A language is context free if and only if the set of derivation trees of his words is a regular tree language. (And this is independent of the grammar used.)

The last step was to construct trees from the matching, and prove that these trees satisfy some monadic second-order sentence. More details will be given in the proof of the theorem 10.

A new Chomsky and Schützenberger Normal form

In this section we reprove a stronger version of the Chomsky and Schützenberger theorem, by restricting the expression K, of theorem 8, to be only star free. This result is also given in [START_REF] Autebert | Théorie des langages et des automates[END_REF], but we reprove it by only logical arguments.

Theorem 9 (Chomsky and Schützenberger [5]) A language L in Σ * is context free if and only if L = ψ(D n ∩ K) where D n is the Dyck language on n "brackets", K a regular expression and ψ a monoïd homomorphism from

Γ ∪ Γ into Σ * .
We recall the Dyck language D n on n brackets is the language generated by the grammar: G =< {a 1 , . . . , a n , a 1 , . . . , a 1 }, {S}, S, P > where P is the set of productions: S → a 1 Sa 1 S| . . . |a n Sa n S|ε where ε denotes the empty word.

If the a ′ i s are assumed to be the opening brackets and a i ′ s the closing ones, D n will be the set of well balanced brackets words.

Theorem 10 A language L is context free if and only if L = ψ(D n ∩ K)

where D n is the Dyck language on n "brackets", K a star-free expression and ψ a monoïd homomorphism from Γ ∪ Γ into Σ * .

We recall the double Greibach normal form.

Lemma 11

Every context free language is generated by a grammar G =< N, Σ, S, P > which satisfies the following condition: all productions are of one of the forms:

(1) S → a, a ∈ Σ or (2) X → aub, X ∈ N, a, b ∈ Σ, and u ∈ (Σ ∪ N ) * .
For a detailed proof we send the reader to the paper of Autebert and al [START_REF] Autebert | Context-free languages and pushdown automata[END_REF].

Proof of the Theorem The way L = ψ(D *

n ∩K) for some star free expression K implies that L is a context free language derives obviously from the Chomsky and Schützenberger theorem because star free expressions are regular.

For the other way we will give some first-order conditions on a Dyck language to construct a set Z such that L = ψ(Z). These conditions are intimately connected to the history of derivations.

Let L be a context free language. By the previous lemma we have a grammar in double Greibach normal form G =< Σ, N, S, P > which derive it from S.

We enumerate first the non-terminal symbols, X 0 = S, ..., X N .

After we label productions by ordered pairs < i, j > where X i is the left hand side non terminal of the production, and j enumerates injectively the productions having X i as left hand side non terminal. The elements of P are:

P 0,1 : X 0 → w 0,1 . . . P 0,i 0 : X 0 → w 0,i 0 . . . P N,1 : X N → w N,1 . . . P N,i N : X N → w N,i N
and for each production we denote c i,j the total number of right hand side non terminals in the production p i,j .

We construct now the set of brackets Γ. It is the set of tuples of integers < a,b,c,d,e,f We give now the conditions on the words of the Dyck language on D Γ to be in Z.

We will decide of the successor of each symbol in this word and give the range of the first and the last symbol.

(1) The first symbol in our word must be an opening bracket of a start configuration and the last one must close this bracket b,c,d,e,f > (x) andc e,f = 0 then we must close immediately our bracket P <a,b,c,d,e,f > (x + 1) because p e,f is a terminal production. (3) P <a,b,c,d,e,f > (x) and c e,f > 0 then we have

∨ 1≤i≤i 0 (P <0,0,1,1,0,i> (min)∧ P <0,0,1,1,0,i> (max)). (2) P <a,
∨ e ′ ,f ′ P <e,f,c e,f ,1,e ′ ,f ′ > (x + 1)
such that e ′ is the first non terminal in the right hand side of p e,f . (4) P <a,b,c,d,e,f > (x) for some x and c > d then we must have We are sure in item 5 to close the good type of parenthese because we are in a Dyck language.

∨ e ′ ,f ′ P <a,b,c,d+1,e ′ ,f ′ > (x+ 1) for some f ′ < i ′ e such
Because of the finiteness of the set Γ these conditions are expressed by a first-order formula.

p a,b : X a → w (a,b,0) X j 1 . . . w (a,b,c a,b -1) X jc a,b w (a,b,c a,b ) .
We now give the homorphism ϕ: ϕ(< a, b, c, d, e, f >) = w (e,f,0) , andϕ(< a, b, c, d, e, f

>) = w (a,b,d) , and ϕ(< 0, 0, 1, 1, 0, i >) = ε.
Where ε is the empty string.

By identifying the brackets to internal nodes of the spanning tree and the homomorphism images to leaves in the right place, we can trivially verify the eqality L = ψ(Z). Q.E.D Example Let's take the grammar G =< {a, b}, {S, Y, Z}, S, P > where P contains the following productions:

S → abba|aY abZba Y → aaY baZbb|aZb Z → ab
We first enumerate the non-terminals: S = X 0 , Y = X 1 , and Z = X 2 . We can now enumerate productions:

p 0,1 : X 0 → abba p 0,2 : X 0 → aX 1 abX 2 ba p 1,1 : X 1 → aaX 1 baX 2 bb p 1,2 : X 1 → aX 2 b p 2,1 : X 2 → ab So we have: Σ = {⟨001101⟩, ⟨001102⟩, ⟨022111⟩, ⟨022112⟩, ⟨022221⟩, ⟨112111⟩, ⟨112112⟩, ⟨112221⟩, ⟨121121⟩}
Which we will denote later 1, 2, 3, 4, 5, 6, 7, 8, and 9.

The Dyck words must satisfy the formula F ≡ (((P 1 (min) ∧ P 1 (max)) ∨ (P 2 (min) ∧ P 2 (max)))∧ (P 1 (x) → P 1 (x + 1))∧ (P 2 (x) → (P 3 (x + 1) ∨ P 4 (x + 1)))∧ (P 3 (x) → (P 6 (x + 1) ∨ P 7 (x + 1)))∧ (P 4 (x) → P 9 (x + 1))∧ (P 5 (x) → (P 5 (x + 1))∧ (P 6 (x) → (P 6 (x + 1) ∨ P 7 (x + 1)))∧ (P 7 (x) → P 9 (x + 1))∧ (P 8 (x) → (P 8 (x + 1))∧ (P 9 (x) → (P 9 (x + 1))∧ We then remark that ϕ(w D ) = w.

(P 1 (x) → x = max)∧ (P 2 (x) → x = max
The construction is closely connected to the derivation tree this is why we are sure of the equivalence.

A logic for unambiguous Context free languages

We give now a logic for unambiguous Context free languages. The main idea is that unambiguity needs unicity of existence.

Let the Logic IM P 2 be the sublogic of IM P where we use the implicit definition of only one predicate, which is binary.

∃M atch F.O. ∩ IM P 2 will be the set of formulas of ∃!M atch F.O. where only one matching M satisfy the first-order formula.

(1) S → a, a ∈ Σ or (2) X → aub, X ∈ N, a, b ∈ Σ, and u ∈ (Σ ∪ N ) * .
This lemma uses only the fact that the classical construction preserves unambiguity.

Proof of the theorem. The proof of this theorem is intimately connected to the one of Lautemann and al for giving a logic for context free languages, we only have to prove that unambiguity of the language implies uniqueness of the matching and vice versa.

By the previous lemma we have an unambiguous grammar in the normal form used in [START_REF] Lautemann | Logics for context-free languages[END_REF]. The processes:

(1) Eliminate all productions of the form X → α for some α ∈ Σ by introducing a new production Y → uαv, for every production Y → uXv ∈ P . (2) Enumerate all non-terminals, X 1 = S, ..., X N . Starting with i = 2 do the following for every i, as long as there is non-terminal production p= X i → v whose pattern also appears as the pattern of a production with left-hand side X j , j < i replace p by all productions which can be obtained from it by substituting one of the non-terminals in v in all possible ways.

terminates and preserves unambiguity.

Then for every Unambiguous Context Free Language we have a Unambiguous Context Free Grammar in double Greibach Normal Form and any two non terminal productions have the same pattern iff they have the same left hand non terminal.

Let T be a derivation tree of w, the matching corresponding to T is M T defined by:(i, j) ∈ M T if and only if i corresponds to the leftmost and j to the rightmost child of the same internal node of T.

We construct now the formula ψ G over < Σ, <, M > which holds for a string w with matching M iff there is a G derivation tree T for w such that M = M T . It follows that there is a matching M on w with < w, M >|= ψ G iff w can be derived in G.

Let (i, j) ∈ M T an arch, the pattern of (i, j) is the string composed of their "brothers" written from left to right where internal nodes are replaced by|.

To be the matching constructed from a G derivation tree, the pattern must correspond to the pattern of a production in G.

For

p ≡ X 0 → αv 0 X 1 v 1 . . . X s v s β where α, β ∈ Σ, v i ∈ Σ * , and X i ∈ N we construct a first-order formula: π p (x, y) = P α (x) ∧ P β (y) ∧ ∃x 1 y 1 . . . x s y s [(x < x 1 < y 1 < . . . < x s < y s < y) ∧(ψ v 0 (x, x 1 ) ∧ ψ v 1 (y 1 , x 2 ) ∧ . . . ∧ ψ vs (y s , y)) ∧(M (x 1 , y 1 ) ∧ . . . ∧ M (x s , y s ))],
where ψ v (i, j) is the first-order formula

∧ n=j n=i P w n-i (n) if v = w 0 .
. . w r , Which characterize the pattern between two positions x and y to correspond to some production p of G.

Let π X (x, y), for x ∈ N be the disjunction of all the π p (x, y) whenever p has X as lefthand side.

We can write now the formula π p (x, y) =

P α (x) ∧ P β (y) ∧ ∃x 1 y 1 . . . x s y s [(x < x 1 < y 1 < . . . < x s < y s < y) ∧(ψ v 0 (x, x 1 ) ∧ ψ v 1 (y 1 , x 2 ) ∧ . . . ∧ ψ vs (y s , y)) ∧(M (x 1 , y 1 ) ∧ . . . ∧ M (x s , y s )) ∧ (π X 1 (x 1 , y 1 ) ∧ . . . ∧ π Xs (x s , y s )],
which restricts the pattern of the matching between x and y to correspond to the matching of a production having the appropriate non terminal as left hand side.

The formula ψ G is then: Since every production is uniquely determined by its pattern, this formula is appropriate for our aim.

For the other direction we remark that the construction of the tree is intimately connected to the matching. Then the uniqueness of the matching implies the uniqueness of the derivation tree for each word, this gives us, by definition, the unambiguity of the language. Q.E.D. Note. As the property "a binary relation is a matching" can be expressed in first-order logic, we can construct a syntactic sublogic of IM P 2 which captures Unambiguous Context Free Languages. This can be done by the set of formulas ϕ ∧ ψ, where ϕ defines a binary relation implicitely and ψ test if this relation is a matching. We gave in this paper the semantic definition rather than the syntactic one because of the simplicity of this notion in this case.

Corollary 14 IM P 2 is undecidable.

This is a simple consequence of undecidability of unambiguity.

Conclusion

We reproved in this paper an algebraic characterization of Context Free Languages by means of Dyck languages, using a result of McNaughton and Papert [START_REF] Mcnaughton | Counter-Free Automata[END_REF] for the logical description of star free expressions and the Double Greibach Normal Form. We could get a cleaner proof by using the Double Quadratic Greibach Normal Form.

Unambiguity of Context Free languages is relevant for compiling theory because if a program has two different derivations we can have different results for the same input.

This motivates me to try to describe Unambiguous Context Free Languages by logical means. But the undecidability of Unambiguity compels us to use an undecidable logic, which is IM P . For a proof of its undecidability see [START_REF] Kolaitis | Implicit definability on finite structures and unambiguous computations[END_REF].

The undecidability of IM P is in the sense commonly understood. That is the set of IM P -formulas is co-recursively enumerable complete. But the undecidability of IM P 2 is in the sense that we can't decide if a given binary predicate, which is a matching, can be whether or not implicitly defined by a first-order formula.

  > where: a, b are a production code such that c a,b ̸ = 0 or a = b = 0. c is 1 if a = b = 0, else c = c a,b . d is such that 1 ≤ d ≤ c and represents the range of the current non terminal in p a,b , 1 ≤ d ≤ c. e, f are the next production code where e must be the code of the c th non terminal in the right hand side of the production p a,b and f ≤ i e ,or e = 0 if a = b = 0. Γ will be the set of < a, b, c, d, e, f > for each element < a, b, c, d, e, f >∈ Γ.

  that e ′ is the d + 1 st non terminal in p a,b . (5) P <a,b,c,d,e,f > (x) for some x and c = d then we must have ∨ <a,b,c,d,e,f > P <a,b,c,d,e,f > (x+ 1).

By

  McNaughton and Papert's theorem Z is a star free subset of D Γ . If c a,b ̸ = 0 then the production p a,b have the form:

Fig. 2 .

 2 Fig. 2. Matching from derivation tree of w

∨

  S→u∈P(ψ u (min, max)) ∨ [∀x∀y(M (x, y) → ∨ p∈P π p (x, y)) ∧ (M (min, max) ∧ π S (min, max))]

The result of Eiter and al [8] discouraged me to look for some more syntactic logic for all classes between N.P. and regular sets.

The result makes the link between two undecidable problems, a logical one and a language theoretic one.

The question which naturally arises after our result is:

Is there a logic for deterministic Context Free Languages?


Romain Barillot

Christian Fournier

Pierre Huynh

Abraham Escobar Gutiérrez

Didier Combes
email: didier.combes@lusignan.inra.fr

Abraham J Escobar-Gutiérrez

How do variations of architectural parameters affect light partitioning within wheat -pea mixtures? A simulation study based on a virtual plant approach

Keywords: Pisum sativum, plant architecture, Triticum aestivum, virtual plant model, wheat-pea mixture

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Light partitioning among intercropped species is highly related to the physical structure of the canopy (Barillot et al., 2011) emerging from the architecture of the individuals growing within the stand (Barillot et al., 2012). Plant architecture is defined as the resultant of i) the inventory of the plant components, ii) the topological relations between these components, and iii) their geometry (Godin, 2000). The multiscale description of the canopy structure reveals the importance of the architectural parameters as underpinning factors that determine light partitioning within mixed cropped systems.

Modelling approaches such as Functional -Structural Plant Models (FSPMs, DeJong et al., 2011) have been proved to be well suited for studying light partitioning within contrasting canopies (Barillot et al., 2011). As a consequence, these models can be considered as pertinent frameworks for assessing the relations between architectural parameters and light partitioning among the component species of intercropping systems.

The aim of the present study was therefore to assess the effect of architectural variations on light partitioning within wheat -pea mixtures. To this end, virtual mixtures were built up from architectural models of both species for which a strong variability of the architecture has been showed among genotypes and environmental conditions (Baccar et al., 2011, Dornbusch et al., 2011, Barillot et al., 2012).

SIMULATIONS

Virtual

wheat -pea mixtures were generated from architectural models of wheat and pea. First, we used a dynamic model of wheat development (Adel-Wheat, Fournier et al., 2003). Then an architectural model of pea, hereafter called L-Pea, was built up using the L-Py platform (Boudon et al., 2012). A detailed description of the model will be given in a companion poster (Barillot et al., 2013). Briefly, the development of pea architecture is modelled as a function of the growing degree day. Kinetics of phytomer and branch production are described in a vegetative module, based on an experiment conducted in

A B

field on cultivar Lucy grown in mixture with wheat. The elongation and coordination of the organs generated by the vegetative module are handled by a growth module. L-pea model was then implemented into the OpenAlea platform (Pradal et al., 2008) in order to generate virtual wheat -pea mixtures (Fig. 1). Sowing densities were set to 125 and 45 plant m -2 for wheat and pea respectively. Finally, virtual wheat -pea mixtures were interfaced with the radiative transfer model Caribu (Chelle and Andrieu, 1998) that allows to estimate the dynamic of light partitioning at each step of the growing cycle. Simulations were processed from 0 to 2000 GDD with a time step of 50 GDD. Architectural parameters were selected as a function of their contribution to the Leaf Area Index (LAI) and plant height (Table 1) that are known to affect light interception.

A first simulation with unmodified architectural parameters for both wheat and pea models was run and called reference simulation. Based on this simulation, the architectural parameters of wheat and pea were then modified by ± 25 and ± 50%.

RESULTS AND DISCUSSION

The modifications performed on the final number of branches and tillers led to variations of light partitioning compared to the reference simulation (Fig. 2). The highest variation of light partitioning resulted from a reduction by 50 % in the number of branches of pea (Fig. 2, left). Lower absolute variations of light partitioning were observed consecutively to an increase of the number of pea branches, thus defining asymmetric variations. Compared to pea, alterations of the number of tillers produced by wheat (Fig. 2, right) led to slighter relative variations of light partitioning (at most 15 %).

Modifications of internode length appeared to have the most dramatic effects on light partitioning compared to branching (Fig. 3). These effects were observed earlier in pea, since the internode elongation of wheat began around 1000 GDD. A strong asymmetry was found in the variations of light partitioning between plants subjected to an increase of their internode length and those whose internodes were reduced. Similar variations of light partitioning were observed after an increase of the internode length of pea or an Branches Tillers equivalent reduction of wheat internodes. In contrast, increasing the internode length of wheat did not bring a similar gain of light interception as an equivalent reduction of pea internodes.

The preliminary results presented here stemmed from a simulation study where the plasticity of plants in response to environmental variations was not included in the model. Therefore, further works have to be conducted in order to study how morphological variations can affect the interactions between the component species and their development. However, we used the FSPM approach to assess the sensitivity of light partitioning to the architecture of wheat and pea plants. These results therefore provide information that enables to identify / design suitable cultivars / ideotypes for intercropping systems towards light partitioning.

LITERATURE CITED

Internode length Internode length

Fig. 1 .

 1 Fig. 1. Illustrations of a virtual wheat -pea mixture. The gradient of colour is a function of the light intercepted by organs (from blue to red).

Fig. 2 .

 2 Fig.2. Relative variations of light interception (%PAR, estimated from the reference simulation) by pea and by wheat (secondary axis in reverse order). Light interception was computed consecutively to a modification in the number of i) branches of pea (left) and ii) tillers of wheat following the gradient of colours.

  Baccar R, Fournier C, Dornbusch T, Andrieu B, Gouache D, Robert C. 2011. Modelling the effect of wheat canopy architecture as affected by sowing density on Septoria tritici epidemics using a coupled epidemic-virtual plant model. Annals of Botany, 108: 1179-1194. Barillot R, Combes D, Chevalier V, Fournier C, Escobar-Gutiérrez AJ. 2012. How does pea architecture influence light sharing in virtual wheat-pea mixtures? A simulation study based on pea genotypes with contrasting architectures. AoB Plants, pls038. Barillot R, Huynh P, Escobar-Gutiérrez AJ, Combes D. 2013. L-Pea: an architectural model of pea (Pisum sativum) development. 7 th International Workshop on Functional-Structural Plant Models. Saariselkä, Finland. Barillot R, Louarn G, Escobar-Gutiérrez AJ, Huynh P, Combes D. 2011. How good is the turbid medium-based approach for accounting for light partitioning in contrasted grass-legume intercropping systems? Annals of Botany, 108: 1013-1024. Boudon F, Pradal C, Cokelaer T, Prusinkiewicz P, Godin C. 2012. L-Py: an L-System simulation framework for modeling plant development based on a dynamic language. Frontiers in Plant Science, 3. Chelle M, Andrieu B. 1998. The nested radiosity model for the distribution of light within plant canopies. Ecological Modelling, 111: 75-91. DeJong TM, Da Silva D, Vos J, Escobar-Gutiérrez AJ. 2011. Using functional-structural plant models to study, understand and integrate plant development and ecophysiology. Annals Of Botany, 108: 987-989. Dornbusch T, Baccar R, Watt J, Hillier J, Bertheloot J, Fournier C, Andrieu B. 2011. Plasticity of winter wheat modulated by sowing date, plant population density and nitrogen fertilisation: Dimensions and size of leaf blades, sheaths and internodes in relation to their position on a stem. Field Crops Research, 121: 116-124. Fournier C, Andrieu B, Ljutovac S, Saint-Jean S. 2003. ADEL-wheat: A 3D architectural model of wheat development. Proceedings of the 2003 Plant Growth Modeling, Simulation, Visualization, and Applications. Beijing, China, IEEE Computer Society. Godin C. 2000. Representing and encoding plant architecture: A review. Annals of Forest Science, 57: 413-438. Pradal C, Dufour-Kowalski S, Boudon F, Fournier C, Godin C. 2008. OpenAlea: a visual programming and component-based software platform for plant modelling. Functional Plant Biology, 35: 751-760.

Fig. 3 .

 3 Fig. 3. Relative variations of light interception (%PAR, estimated from the reference simulation) by pea and by wheat (secondary axis in reverse order). Light interception was computed consecutively to a modification of internode length for pea (left) and wheat (right) following the gradient of colours.

Table 1 :

 1 Architectural parameters selected for modifying the species LAI and height.

	Variable


Keywords: architectural model, morphogenesis, Pisum sativum, plant architecture

Highlights: an architectural model of pea, called L-Pea, was developped based on the L-System formalism

Currently, pea (Pisum sativum) is the principle source of vegetable proteins. However, the productivity of pea crop is still under its potential. Studying pea architecture (e.g. Leaf Area Index (LAI), plant height, foliar inclination) enables to analyze its interactions with abiotic (light, nirtogen, water) and biotic factors (foliar diseases). Architectural models therefore appear as suitable tools for studying the functioning of pea (Barillot et al., 2012). The aim of the present work was therefore to develop an architectural model of pea growth, hereafter called L-Pea (Fig. 1).

The model is based on the L-system formalism and implemented on the L-Py platform (Boudon et al., 2012). Pea morphogenesis was modelled as being driven by thermal time which can be incremented from meteorological data at each time step. The above ground architecture is represented as a succession of phytomers that compose main stems and branches. Kinetics of phytomer and branch production are described in a vegetative module. Phytomers are considered as a collection of organs encoded as modules that support their state i.e. age, length, topology and geometry. The elongation and coordination of the organs generated in the vegetative module are then handled by a growth module. The initial parameters of phytomer production and organ growth were mainly based on measurements performed on a field-grown crop of winter pea, cv. Lucy.

In a companion study, the L-Pea model was interfaced with a dynamic model of wheat development (Fournier et al., 2003) in order to generate virtual wheat-pea mixtures. This allowed us to study the relations between the architecture of the component species and the level of light partitioning. Detailed methods and results are given in Barillot et al. (2013). To our kwonoledge L-Pea is the first architectural model of pea available in the literature. This model can therefore provide a suitable framework for studying the behaviour of contrasted pea architecture towards light interception or foliar disease dispersion.

LITERATURE CITED

  Barillot R, Combes D, Chevalier V, Fournier C, Escobar-Gutiérrez AJ. 2012. How does pea architecture influence light sharing in virtual wheat-pea mixtures? A simulation study based on pea genotypes with contrasting architectures. AoB Plants pls038. Boudon F, Pradal C, Cokelaer T, Prusinkiewicz P, Godin C. 2012. L-Py: an L-System simulation framework for modeling plant development based on a dynamic language. Frontiers in Plant Science 3. Fournier C, Andrieu B, Ljutovac S, Saint-Jean S. 2003. ADEL-wheat: A 3D architectural model of wheat development. Proceedings of the 2003 Plant Growth Modeling, Simulation, Visualization, and Applications. Beijing, China: IEEE Computer Society, 54-63. Barillot R, Fournier C, Huynh P, Escobar-Gutiérrez AJ, Combes D. 2013. How do variations of architectural parameters affect light partitioning within wheat pea mixtures? A simulation study based on a virtual plant approach. 7 th International Workshop on Functional-Structural Plant Models. Saariselkä, Finland.

Fig. 1 :

 1 Fig.1: side view of a canopy of 3D pea plants generated from L-Pea model

Proceedings of the 7 th International Conference on Functional-Structural Plant Models, Saariselkä, Finland, 9 -14 June 2013. Eds. Risto Sievänen, Eero Nikinmaa, Christophe Godin, Anna Lintunen & Pekka Nygren. http://www.metla.fi/fspm2013/proceedings.

Romain Barillot 1 , Pierre Huynh 1 , Abraham J Escobar-Gutiérrez 2 and Didier Combes 2* 1 LUNAM Université, Groupe Ecole Supérieure d'Agriculture, UPSP Laboratoire d'Ecophysiologie Végétale & Agroécologie, 55 rue Rabelais, BP 30748, F-49007 Angers cedex 01, France. 2 INRA, UR4 P3F, Equipe Ecophysiologie des plantes fourragères, Le Chêne -RD 150, BP 6, F-86600 Lusignan, France.


Gaëtan Louarn
email: gaetan.louarn@lusignan.inra.fr

Abraham Escobar-Guttierrez

Didier Combes

"Virtual grassland": an OpenAlea package to deal with herbaceous plant architecture and grassland community dynamics

Keywords: Architecture, grass, legume, community, dynamics

whether they are published or not. The documents may come

"Virtual grassland": an OpenAlea package to deal with herbaceous plant architecture and grassland community dynamics

Gaëtan Louarn, Abraham Escobar Gutiérrez, Didier Combes

To cite this version:

Gaëtan Louarn, Abraham Escobar Gutiérrez, Didier Combes. "Virtual grassland": an OpenAlea package to deal with herbaceous plant architecture and grassland community dynamics. 7. International Conference on Functional Structure Plant Models, Jun 2013, Saariselkä, Finland. 371 p. hal-01299604

Grasslands are the major source of forages worldwide. They are exploited via grazing and mowing and can be natural or cultivated. Their agricultural use-value depends on the structure of their canopy and on their botanic composition (most are indeed multi-specific). Both determine the quantity and the quality of the biomass harvested by grazing or mowing. In temperate grasslands, perennial grasses and forage legumes dominate the floristic composition of grasslands and are generally intended to be grown in mixtures because of their agronomic (feeding value) and ecological (resource capture and use) complementarities. An appropriate species balance is however difficult to maintain in such non-equilibrium communities. The proportion of forage legumes fluctuates both from year-to-year and within a single growth period as a result of species interactions and management. In spite of its agronomic significance, most grassland models developed so far ignore plant-plant interactions and the community dynamics of grasslands. Efforts have been done mainly on white clover based mixtures for which a gain of understanding of coexistence conditions was achieved thanks to individual-based models. White clover has however rather atypical colonisation strategy and persistence habit among forage legumes and these predictions may present a limited interest for other grass-legume combinations. To deal with this question, the "Virtual grassland" package was developed under the OpenAlea platform (Pradal et al. 2008) to simulate the architecture of various grass and legume species and predict the effects of competition / facilitation interactions at the population and community levels.

The "Virtual grassland" package provides i) two generic plant models accounting respectively for grass (L-grass) and legume (L-egume) morphogenesis above-and below-ground, and considering responses to defoliation (Verdenal et al. 2008), ii) coupling methods (in the form of OpenAlea nodes) between the MTG central data structure for plant architecture and environmental models above-(light) and belowground (water and soil N) available through the platform and finally iii) dataflows enabling to scale up from plant to community and ecosystem (soil-plants-atmosphere) levels by combining the different plant and environmental models together, and providing a graphical interface to manage model input parameters and visualise simulation results. The two plant models are based on the l-system formalism (L-py software) and aim at accounting for intra-and inter-specific variations in morphogenesis, dry matter production and C/N composition. In the legume functional group, different growth habit in terms of shoot growth (erect/prostrate), branching, coordination of organ growth and ability to develop adventitious roots/shoots enable to distinguish between colonisation strategies ranging from herbs perennating by formation of a single taproot (such as alfalfa or red clover) to clonal patches resulting from rhizome spreading (creeping lucerne) or rooted shoots at the soil surface (white clover). Similarly, in grasses, differences in the self-regulation of leaf growth and tiller development enable to account for growth habit ranging from long-leaf forage species/cultivars to short-leaf turfs. Leaf gas-exchange is simulated using the Farqhar model. A simple soil model adapted from the STICS soil module is currently tested for water and nitrogen acquisition. The coupled soil-plant-atmosphere model is currently being assessed both for the behaviour of isolated plants, and the dynamic of plant populations into binary species mixtures.

LITERATURE CITED

  Pradal C, Dufour-Kowalski S, Boudon F, Fournier C, Godin C. 2008. OpenAlea: a visual programming and component-based software platform for plant modelling. Functional Plant Biology 35(10): 751-760. Verdenal A, Combes D, Escobar-Gutiérrez AJ. 2008. A study of ryegrass architecture as a self-regulated system, using functional-structural plant modelling. Functional Plant Biology 35: 911-924.


domain: math stat

text:
Paolo Leonetti

FINITE PARTIALLY EXCHANGEABLE LAWS ARE SIGNED MIXTURES OF PRODUCT LAWS

Keywords: 2010 Mathematics Subject Classification. Primary 44A60, 60G09; Secondary 15A24, 46A55, 62E99 Finite partial exchangeability, signed measure, de Finetti representation, true mixture, reduced Hausdorff moment problem

Given a partition {I 1 , . . . , I k } of {1, . . . , n}, let (X 1 , . . . , Xn) be random vector with the X i taking values in an arbitrary measurable space (S, S ) such that their joint law is invariant under finite permutations of the indexes within each class I j . Then, it is shown that this law has to be a signed mixture of independent laws and identically distributed within each class. The representation is unique if and only if the set of these signed measures is weakly compact.

We provide a necessary condition for the existence of a nonnegative directing measure. This is related to the notions of infinite extendibility and reinforcement. In the special case where (X 1 , . . . , Xn) is an exchangeable sequence of {0, 1}-valued random variables, the directing measure can be chosen nonnegative if and only if two effectively computable matrices are positive semi-definite.

1. Introduction de Finetti's theorem, in one of its most general forms, states that if (X n : n ∈ N) is a sequence of random variables such that each X n takes values in a Borel space (S, S ) and their joint law is invariant under finite permutations of the indexes, then there exists a unique probability measure µ on the set P(S) of probability measures on S such that

Pr ((X n : n ∈ N) ∈ A) = P(S) ν ∞ (A) µ(dν) (1)
for all A ∈ S N . Here, ν ∞ stands for the (countably infinite) product measure ν × ν × • • • , and P(S) is equipped with the σ-field generated by the weak ⋆ topology; see, for instance, [START_REF]Probabilistic Symmetries and Invariance Principles[END_REF]Theorem 1.1]. Similarly, the result holds if S is a compact Hausdorff space and S its Baire σ-field, as shown by Hewitt and Savage in [START_REF] Hewitt | Symmetric measures on Cartesian products[END_REF]Theorem 7.2]. On the other hand, some kind of assumptions on S are needed to ensure representation (1) holds: indeed, Dubins and Freedman have shown that there exists a separable metric space S for which the result fails [START_REF] Dubins | Exchangeable processes need not to be mixtures of independent, identically distributed random variables[END_REF]Theorem 2.14].

The finite case is completely different. Recently, Kerns and Székely proved in [17, Theorem 1.1] that, if (S, S ) is an arbitrary measurable space and (X 1 , . . . , X n ) is exchangeable, then there exists a bounded signed measure µ on the set P(S) of probability measures on S such that Pr ((X 1 , . . . , X n ) ∈ A) = P(S)

ν n (A) µ(dν) (2)
for all A ∈ S n . Similarly, ν n stands for the product measure ν ו • •×ν, and P(S) is equipped with the smallest σ-field for which all the maps ν → ν(B) are measurable, where B ranges over S . Accordingly, the directing measure µ cannot be assumed to be nonnegative, as it is shown in the famous example provided by Diaconis and Freedman [START_REF]Finite exchangeable sequences[END_REF]. An interpretation of the geometric structure underlying the representation (2) can be found in [START_REF] Diaconis | Finite forms of de Finetti's theorem on exchangeability[END_REF].

With these premises, the article focuses entirely on the finite case. In the first part, Theorem 1 provides a generalization of the finite representation [START_REF] De Finetti | Sur la condition d'equivalence partielle[END_REF] to the case of finite partially exchangeable sequences, i.e., whenever the law of (X 1 , . . . , X n ) is invariante under permutation of the indexes within each class I j , for some partition {I 1 , . . . , I k } of {1, . . . , n}. This type of invariance could be termed subgroup exchangeability, cf. Remark 2. Relationships with other types of partial exchangeability studied in the literature will be clarified in Section 7. As pointed out in [START_REF] Kerns | De Finetti's theorem for abstract finite exchangeable sequences[END_REF] and remarked in [START_REF] Janson | On a representation theorem for finitely exchangeable random vectors[END_REF], the result allows to prove consistency of Bayesian estimators. In addition, under rather weak topological assumptions, this finite representation is unique if and only if the set of directing measures is compact.

In the second part, we notice that, if the directing measure can be chosen nonnegative, then the representation may provide a justification for the use of priors in Bayesian parametric. In this respect, Theorem 2 provides a necessary condition for its existence. This is related to the notions of infinite extendibility and reinforcement.

Lastly, we obtain necessary and sufficient conditions on exchangeable sequences taking values in {0, 1} to be mixtures, in the classical sense, of i.i.d. (Bernoulli) random variables. Accordingly, the problem can be equivalent reformulated to question whether a point belongs to the convex hull of a known finite set of extremal points; see, for instance, [3, p. 275]. Here, differently from the geometric characterization, we show that an exchangeable law on {0, 1} n is a mixture of i.i.d. random variables if and only if two effectively computable matrices are positive semi-definite.

The finite representation

Given an index set I and a subset G of the group of permutations on I, a sequence (X i ) i∈I of random variables defined on a probability space (Ω, F , P) with each X i taking values in a measurable space (S, S ) is said to be exchangeable over G whenever

(X i : i ∈ I) d = (X σ(i) : i ∈ I) for all σ ∈ G.
Hereafter, let us suppose that G can be written as the product of the symmetric groups on I 1 , . . . , I k , for some partition {I 1 , . . . , I k } of {1, . . . , n}. In other words, the joint law of (X 1 , . . . , X n ) is invariant under permutations of the indexes within each class I j . Then, our main result can be stated as follows:

Theorem 1. Let (X 1 , . . . , X n ) be an exchangeable sequence over G of random variables with each X i taking values in a measurable space (S, S ). Then there exists a bounded signed measure µ on P(S) k such that

P ((X i : i ∈ I j ) ∈ A j , j = 1, . . . , k) = P(S) k ν n1 1 (A 1 ) • • • ν n k k (A k ) µ(dν 1 , . . . , dν k ) (3)
for all A 1 ∈ S n1 , . . . , A k ∈ S n k , where n j stands for the cardinality of I j for each j.

It is worth noting that Theorem 1 generalizes the results of Jaynes [START_REF] Jaynes | Some applications and extensions of the de Finetti representation theorem[END_REF], Kerns and Székely [17, Theorem 1.1], and Janson, Konstantopoulos and Yuan [START_REF] Janson | On a representation theorem for finitely exchangeable random vectors[END_REF]Theorem 1]. Moreover, it solves an open question in the latter article, see [START_REF] Janson | On a representation theorem for finitely exchangeable random vectors[END_REF]Section 4.8].

However, our main interest in Theorem 1 is related to its consequences.

Corollary 1. With the notation of Theorem 1, let us assume that S is a separable Banach space with induced Borel σ-field S . Then there exists a bounded signed measure η on S k such that

P ((X i : i ∈ I j ) ∈ A j , j = 1, . . . , k) = S k ν n1 θ1 (A 1 ) • • • ν n k θ k (A k ) η(dθ 1 , . . . , dθ k ) (4)
for all A 1 ∈ S n1 , . . . , A k ∈ S n k , where each ν θj is a probability measure on S depending measurably on the parameter θ j .

Note that the result holds in the case of real-valued random variables. If the directing measure η can be chosen nonnegative, this may provide a sort of justification for the use of priors in Bayesian parametric.

Moreover, it is reasonable to question whether the finite representation (3) is unique. To this aim, denoting with M = M(G) the set of these bounded signed measures, we obtain the following: Corollary 2. With the notation of Theorem 1, let us assume that S is a locally convex topological vector space with induced Borel σ-field S . Then the finite representation (3) is unique if and only if M is weakly compact.

In particular, the result holds whenever S is Banach space. Proofs follow in Section 5.

True Mixtures

In most cases, the main difference between the finite and the infinite case is that the directing measure µ may be signed. Therefore, it looks natural to ask about the positiveness of µ and, more in general, about the infinite extendibility of an exchangeable sequence (X 1 , . . . , X n ).

In this respect, Konstantopoulos and Yuan have shown in [START_REF] Konstantopoulos | On the extendibility of finitely exchangeable probability measures[END_REF]Theorem 2] that if S is a locally compact Hausdorff space and the law of X 1 is inner and outer regular, then such an infinite extension exists if and only if for each integer N ≥ n there is an exchangeable sequence (Y 1 , . . . , Y N ) with each

Y i taking values in (S, S ) such that (X 1 , . . . , X n ) d = (Y 1 , . . . , Y n ).
In turn, this is equivalent of being a true mixture of i.i.d. random variables whenever S is equipped with its Baire σ-field (hereafter, "true" underlines that the directing measure is nonnegative), see [START_REF] Konstantopoulos | On the extendibility of finitely exchangeable probability measures[END_REF]Theorem 3].

In this section, we provide a set of necessary conditions on the joint law of a random vector (X 1 , . . . , X n ) exchangeable over G which can be represented as true mixture of independent random variables and identically distributed within each class I j . To this aim, we fix some additional notation: given a square matrix M = (m i,j ) with entries in S n1 × • • • × S n k , we shorten the real-valued matrix (P(X ∈ m i,j )) with P M. Moreover, given positive integers a, b and matrices A, B with entries in S a and S b , respectively, we denote by A B the matrix with entries in S a+b , constructed as the analogue of Kronecker product, where the multiplication of entries is replaced by their cartesian products.

Accordingly, we obtain the following result:

Theorem 2. Let (X 1 , . . . , X n ) be an exchangeable sequence over G of random variables with each X i taking values in a measurable space (S, S ), and let us suppose that the signed measure µ in the the finite representation (3) is nonnegative.

Then, for all even nonnegative integers 2m 1 ≤ n 1 , . . ., 2m k ≤ n k , for all A 1 , . . . , A k ∈ S , and for all B 1 ∈ S n1-2m1 , . . . , B k ∈ S n k -2m k , the following matrix

P k j=1         A 2mj j × B j A 2mj -1 j × S × B j • • • A mj j × S mj × B j A 2mj -1 j × S × B j A 2mj -2 j × S 2 × B j • • • A mj -1 j × S mj+1 × B j . . . . . . . . . . . . A mj j × S mj × B j A mj -1 j × S mj+1 × B j • • • S 2mj × B j         is positive semi-definite.
The main result of von Plato [START_REF] Plato | Finite partial exchangeability[END_REF]Theorem 4] follows in the special case where n = 4, k = 2,

n 1 = n 2 = 2, m 1 = m 2 = 1, S = {0, 1}, and A = {1}; cf. Remark 3.
Moreover, it follows that, if k = 1, m 1 = 1, and P(X ∈ S 2 × B) > 0, then

P(X 1 ∈ A|X 2 ∈ A, (X 3 , . . . , X n ) ∈ B) = P(X ∈ A 2 × B) P(X ∈ A × S × B) ≥ P(X ∈ A × S × B) P(X ∈ S 2 × B) = P(X 2 ∈ A|(X 3 , . . . , X n ) ∈ B).
This can be intepreted as a reinforcement property; see, e.g., [START_REF] Muliere | Urn schemes and reinforced random walks[END_REF] and [START_REF] Pemantle | Phase transition in reinforced walk and RWRE on trees[END_REF]. The same observation applies to partially exchangeable sequences, once we set each m j = 1 in Theorem 2.

In the special case where G is the symmetric group on {1, . . . , n} and S = {0, 1}, we provide an explicit characterization of the finite exchangeable sequences which can be written as true mixtures of i.i.d. (Bernoulli) random variables.

To this aim, , define

x i = P(X 1 = • • • = X i = 0, X i+1 = • • • = X n = 1) for each i = 0, 1, . . . , n.
Then, for each positive integer n, let

H n = h (n) i,j
and

K n = k (n) i,j
be the Hankel matrices given by

h (n) i,j =            n+2-i-j k=0 n + 2 -i -j k x k if n is even and 1 ≤ i, j ≤ n + 2 2 n+1-i-j k=0 n + 1 -i -j k x k if n is odd and 1 ≤ i, j ≤ n + 1 2
, and

k (n) i,j =            n-i-j k=0 n -i -j k x k+1 if n is even and 1 ≤ i, j ≤ n 2 n+1-i-j k=0 n + 1 -i -j k x k+1 if n is odd and 1 ≤ i, j ≤ n + 1 2
.

With these premises, we obtain the following necessary and sufficient condition:

Theorem 3. Let (X 1 , . . . , X n ) be an exchangeable sequence of {0, 1}-valued random variables. Then the joint law of (X 1 , . . . , X n ) is a true mixture of i.i.d. random variables if and only if H n and K n are positive semi-definite.

Interestingly, Wood [28, Theorem 2] calculated the probability that, picking at random an exchangeable sequence of {0, 1}-valued random variables (X 1 , . . . , X n ), this is infinitely extendible; in particular, this probability goes to 0 as n → ∞.

Lastly, we obtain the following corollary, which turns out to be a generalization of [27, Theorem 1 and 2]: Corollary 3. Let (X 1 , . . . , X n ) be a {0, 1}-valued exchangeable sequence which can be represented as a true mixture of i.i.d. random variables. Then, for all i = 1, . . . , n -1, it holds

x i ≤ √ x i-1 x i+1 . (5)
On the other hand, these conditions are also sufficient if and only if n ≤ 3.

An alternative proof of the first part of Corollary 3 has been given in a manuscript of Muliere and Walker [START_REF] Muliere | Reinforcement and Finite Exchangeability[END_REF], which, however, focuses on the relationship between the concepts of reinforcement and finite exchangeability. Proofs of Theorem 2 and Theorem 3 follow in Section 6.

Notations and Preliminaries

The sets of reals and positive integers are denoted, respectively, with R and N. Each of these sets is endowed with its usual addition, multiplication, and (total) order ≤.

Given sets X, Y, Z and functions f : X → Y and g : Y → Z, we write f [X] for the image set (or range) of f , namely f [X] := {f (x) : x ∈ X} ⊆ Y , and g • f for the composition X → Z : x → g(f (x)). Moreover, for each nonempty subset A ⊆ X, the indicator function 1 A : X → {0, 1} is defined by

1 A (x) = 1 if and only if x ∈ A.
Given a probability space (X, Σ, µ) and a measurable space (Y, G ), we say that two random variables α, β : X → Y have the same distribution, shortened with

α d = β, whenever µ • α -1 = µ • β -1 . Also, for each x ∈ X, let δ x be the Dirac measure at x, that is, the probability measure Σ → R : A → 1 A (x).
Lastly, the symbol ⊗ will be reserved for the Kronecker product. We refer to [START_REF] Engelking | General Topology[END_REF], [START_REF] Horn | Matrix Analysis[END_REF], [START_REF] Kallenberg | Foundations of Modern Probability[END_REF], and [START_REF] Rudin | Functional Analysis[END_REF], respectively, for basic aspects of topology, matrix analysis, probability theory, and functional analysis (including notation and terms not defined here).

Remark 1. Notice that the integral on the right hand side of ( 3) is well defined. Indeed, for each

A 1 ∈ S n1 , . . . , A k ∈ S n k , each map (ν 1 , . . . , ν k ) → ν n1 1 (A 1 ) • • • ν n k k (A k ) is measurable.
To this aim, it will be sufficient to show the statement for k = 1. The σ-field defined on P(S), hereafter shortened with σ(P(S)), may be written explicitly as σ ({ν ∈ P(S) : ν(A) ∈ B} : A ∈ S , B ∈ B), where B stands for the usual Borel σ-field on R. Then it is claimed that the map

P(S) → R defined by ν → ν n (A) is measurable for each n ∈ N and A ∈ S n , that is, {ν ∈ P(S) : ν n (A) ∈ B} belongs to σ(P(S)) for each B ∈ B. Let E be the collection of all A ∈ S n such that the mapping ν → ν n (A) is measurable. Then E contains all rectangles A = A 1 × • • • × A n with A 1 , . . . , A n ∈ S ,
as far as the product of measurable functions ν → ν(A i ) is measurable. In particular, E contains S n . Moreover, it is easily seen that E is closed under finite intersection and countable disjoint union. Therefore, it follows by the monotone class theorem that E = S n . Remark 2. The type of partial exchangeability used in Theorem 1 could be termed subgroup exchangeability. Indeed, let G be a subgroup of the symmetric group on {1, . . . , n}. Then there exists a unique partition {I 1 , . . . , I k } of {1, . . . , n} such that G is equal to the product of the symmetric groups on I 1 , . . . , I k . This is trivially true for n = 1. Let us assume that it holds for n -1 and consider all permutations of G which leaves the element n unchanged. This subset, being isomorphic to a subgroup of the symmetric group on {1, . . . , n -1}, can be written as the group the generated by the symmetric groups on I 1 , . . . , I k , for a necessarily unique partition {I 1 , . . . , I k } of {1, . . . , n -1}. If the subset is equal to G itself, then the required partition equals {I 1 , . . . , I k , {n}}; otherwise, let J be the subset of integers in {1, . . . , n -1} which are connected with n, for some permutations in G. Then the required partition is a coarsening of {I 1 , . . . , I k , {n}}, obtained making the union of {n} with all I j containing at least one element of J. The claim follows by induction.

The next identity will be useful in the proof of Theorem 3: Lemma 1. Let n be a positive integer. Then, for each nonnegative integer j ≤ n -1 it holds

n-1 i=j n i i j (-1) i = n j (-1) n-1 .

Paolo Leonetti

Proof. We have equivalently to prove that n i=j n i i j (-1) i = 0. To this aim, rewrite it as

n i=j n i i j (-1) i = n j n i=j n -j i -j (-1) i = (-1) j n j n-j k=0 n -j k (-1) k .
The claim follows by the fact that the last sum is the binomial expansion of (1 -1) n-j .

We conclude the section with a result about positive semi-definite matrices:

Lemma 2. Let (X, F , µ) be a finite measure space and let f 1 , g 1 , . . . , f k , g k : X → R be measurable functions. Fix also positive integers m 1 , . . . , m k such that f i1

1 g 1 • • • f i k k g k are integrable for all nonnegative integers i 1 ≤ 2m 1 , . . . , i k ≤ 2m k , and define the matrix M = (m i,j ) by k j=1         f 2mj j g j f 2mj -1 j g j • • • f mj j g j f 2mj-1 j g j f 2mj -2 j g j • • • f mj -1 j g j . . . . . . . . . . . . f mj j g j f mj-1 j g j • • • g j        
.

Then, the matrix X m i,j dµ is positive semi-definite.

Proof. Let ν be the function

F → R : F → F g 1 • • • g k dµ.
Then, it is straightforward to check that ν is a finite measure such that

X hg 1 • • • g k dµ = X h dν whenever h : X → R is measurable. It means that it is enough to prove the claim for g 1 = • • • = g k = 1 X .
In addition, the statement is trivial is µ(X) = 0, hence we can assume without loss of generality that µ is a probability measure on X. At this point, for each z ∈ R n1•••n k , we have to show that z ′ X m i,j dµ z is nonnegative, where z ′ stands for the transpose of z. Accordingly, define the measurable functions h j,1 , . . . , h j,n1•••n k : X → R, for each j = 1, . . . , k, such that they have distribution f j and all h j,i 's are jointly independent. Consider the following Kronecker product

k j=1         f 2mj j f 2mj -1 j • • • f mj j f 2mj-1 j f 2mj -2 j • • • f mj -1 j . . . . . . . . . . . . f mj j f mj-1 j • • • 1        
and replace each function f j in the i-th column with a h j,i , for all i = 1, . . . , n

1 • • • n k . Averaging over all (n 1 • • • n k )! k
permutations of the columns, we obtain by a symmetric argument that the above matrix is equal to

1 (n 1 • • • n k )! k k j=1 n1•••n k i=1         h 2mj j,i h 2mj -1 j,i • • • h mj j,i h 2mj -1 j,i h 2mj -2 j,i • • • h mj -1 j,i . . . . . . . . . . . . h mj j,i h mj-1 j,i • • • 1         .
Taking the expected values at each entry, and using independence, it follows that

z ′ X m i,j dµ z = 1 (n 1 • • • n k )! k z ′         X k j=1 n1•••n k i=1         h 2mj j,i h 2mj -1 j,i • • • h mj j,i h 2mj -1 j,i h 2mj -2 j,i • • • h mj -1 j,i . . . . . . . . . . . . h mj j,i h mj -1 j,i • • • 1         dµ         z = 1 (n 1 • • • n k )! k X z ′ k j=1 n1•••n k i=1         h 2mj j,i h 2mj-1 j,i • • • h mj j,i h 2mj-1 j,i h 2mj-2 j,i • • • h mj -1 j,i . . . . . . . . . . . . h mj j,i h mj -1 j,i • • • 1         z dµ = 1 (n 1 • • • n k )! k X z ′ k j=1 H j H ′ j z dµ,
where we define

H j =         h mj j,1 h mj j,2 • • • h mj j,n1•••n k h mj-1 j,1 h mj-1 j,2 • • • h mj -1 j,n1•••n k . . . . . . . . . . . . 1 1 • • • 1        
for each j = 1, . . . , k. This is clearly nonnegative since the Kronecker product of positive semi-definite matrices is positive semi-definite.

Remark 3. It turns out that Lemma 2 is the determinant analogue of the Cauchy-Schwarz's inequality [19, Chapter 2.6], indeed: Let (X, F , µ) be a finite measure space and let f, g : X → R be measurable square-integrable functions. Then f g is integrable and

X f g dµ 2 ≤ X f 2 dµ X g 2 dµ .
To this aim, set k = 2, m 1 = m 2 = 1 and g 1 = g 2 = 1 X in Lemma 2 and assume without loss of generality that µ is a probability measure (the case µ(X) = 0 being trivial). Then, setting f 1 = f and f 2 = g, we obtain that the matrix with entries given by the µ-integrals of each entry in

f 2 f f 1 ⊗ g 2 g g 1
is positive semi-definite. The claim follows by Sylvester's criterion [10, Theorem 7.2.5], indeed the principal minor

  X g 2 dµ X f g dµ X f g dµ X f 2 dµ  
has a nonnegative determinant.

Proofs of Theorem 1

We are finally ready to prove our main result:

Proof of Theorem 1. Denoting with n j the cardinality of I j , we obtain by the exchangeability assumption that

P ((X i : i ∈ I j ) ∈ A j , j = 1, . . . , k) = |G| -1 σ∈G P (σX ∈ A) = Ω U X (A) dP for each A 1 ∈ S n1 , . . . , A k ∈ S n k , where A = A 1 × • • • A k , σX = (X σ(1) , . . . , X σ(n) )
, and U X (A) : Ω → P(S) is the mapping defined by the arithmetic mean of empirical distributions over permutations on G, i.e.,

ω → |G| -1 σ∈G δ σX(ω) (A).
Let T be the σ-field generated by S and the singletons in S. Moreover, given x = ((x i ) : i ∈ I j , j = 1, . . . , k) ∈ S n , let ν j (x) be the distribution in P(S) defined by i∈Ij δ xi for each j = 1, . . . , k. It follows by the exchangeability assumption that, for each x ∈ S and A ∈ S n , it holds

U x (A) = |S(x)| -1 y∈S(x) δ y (A),
where S(x) stands for the set of all y ∈ S n such that ν j (x) = ν j (y) for each j = 1, . . . , k. Observe that the set S(x) has exactly n ν1(x),...,ν k (x) elements, where n λ1,...,λ k is equal to n!/ k j=1 s∈S λ j {s} whenever λ 1 , . . . , λ k are point measures on S such that λ j (S) = n j for each j = 1, . . . , k. In other words, U x represents the uniform distribution on S(x). Hereafter, the set of these point measures λ = (λ 1 , . . . , λ k ) ∈ P(S) k will be denoted with L . In particular, for each λ ∈ L , the product measure k × j=1 λ j n j nj is a probability measure on (S n , T n ). Given x ∈ S n , denote also by V x the subset of point measures ν = (ν 1 , . . . , ν k ) in L supported on {x 1 , . . . , x n }. Lastly, notice that the collection {S(x) : x ∈ S n } is made of pairwise disjoint subsets in T n and their union is S n .

With these premises, it follows that, for each x ∈ S n and λ ∈ L , it holds

( k × j=1 λ nj j )(S(x)) = |S(x)| λ ν(x) ,
where α β := k j=1 s∈S α j {s} βj{s} for each α, β ∈ L . Hence, for each x ∈ S n , λ ∈ V x , and A ∈ T n , we obtain

( k × j=1 λ nj j )(A) = ν∈Vx n ν 1 , . . . , ν k λ ν U η(ν) (A),
with η(ν) being any element of S n for which ν(η(ν)) = ν. In particular, it represents a linear system of identities between measures on (S n , S n ). Having fixed an order on the finite set V x = {γ 1 , . . . , γ m }, the m × m square symmetric matrix of coefficients with (i, j)-th entry given by n γi γ γj i can be seen a leading principal minor of the bigger matrix obtained similarly by setting k = 1.

It has been shown in [START_REF] Moak | Combinatorial multinomial matrices and multinomial Stirling numbers[END_REF]Theorem 2] that all eigenvalues of the latter bigger matrix are (real, of course, and) positive, which is well known to be equivalent of being positive definite. In turn, all leading principal minors are positive definite by Sylvester's criterion. This implies that the above matrix of coefficients has full rank. Therefore, for each x ∈ S n , there exist real coefficients {c x,λ , λ ∈ V x } such that for all A ∈ S n it holds

U x (A) = λ∈Vx c x,λ ( k × j=1 λ nj j )(A).
At this point, define the bounded signed measure µ : σ(P(S)) k → R on the k-fold product P(S) k by

Q → Ω ν∈V X(ω) n n1 1 • • • n n k k c X(ω),ν ( k × j=1 δν j/n j )(Q) P(dω).
Hence we obtain that

P((X i : i ∈ I j ) ∈ A j , j = 1, . . . , k) = Ω U X(ω) (A 1 × • • • × A k ) P(dω) = Ω λ∈V X(ω) c X(ω),λ ( k × j=1 λ nj j )(A 1 × • • • × A k ) P(dω) = Ω λ∈V X(ω) n n1 1 • • • n n k k c X(ω),λ k × j=1 ( λ j n j ) nj (A 1 × • • • × A k ) P(dω),
which can be rewritten as

Ω λ∈V X(ω) n n1 1 • • • n n k k c X(ω),λ P(S) k ν n1 1 • • • ν n k k ( k × j=1 δλ j/n j )(dν 1 , . . . , dν k ) (A 1 × • • • × A k ) P(dω)
or, equivalently

Ω P(S) k ν n1 1 • • • ν n k k λ∈V X(ω) n n1 1 • • • n n k k c X(ω),λ ( k × j=1 δλ j/n j )(dν 1 , . . . , dν k )(A 1 × • • • × A k ) P(dω).
This is equal by Fubini's theorem to

P(S) k ν n1 1 (A 1 ) • • • ν n k k (A k )   Ω λ∈V X(ω) n n1 1 • • • n n k k c X(ω),λ ( k × j=1 δλ j/n j )P(dω)   (dν 1 , . . . , dν k ), hence P((X i : i ∈ I j ) ∈ A j , j = 1, . . . , k) = P(S) k ν n1 1 (A 1 ) • • • ν n k k (A k ) µ(dν 1 , . . . , dν k ).
Proof of Corollary 1. More generally, let us assume that S is a locally convex with induced Borel σ-field S . Then there exists a bounded signed measure η on S n such that

P ((X i : i ∈ I j ) ∈ A j , j = 1, . . . , k) = S n ν n1 (θi:i∈I1) (A 1 ) • • • ν n k (θi:i∈I k ) (A k ) η(dθ 1 , . . . , dθ n ) (6)
for all A 1 ∈ S n1 , . . . , A k ∈ S n k , where each ν (θi:i∈Ij ) is a probability measure on S depending measurably on n j parameters (θ i : i ∈ I j ). This is a straighforward generalization of [START_REF] Janson | On a representation theorem for finitely exchangeable random vectors[END_REF]Theorem 2], to which we refer the reader for the proof, taking in account also [START_REF] Rudin | Functional Analysis[END_REF]Theorem 3.4]. In particular, since any two uncountable Polish spaces are isomorphic in the category of measurable spaces, it follows by a change of variable argument that the number of indexes reduces to one for each class I j .

Proof of Corollary 2. Theorem 1 shows that the set M is nonempty. Also, the uniqueness of representation (3) is equivalent of M being a singleton, from which the "only if" part trivially follows.

Conversely, let us suppose that M is nonempty and weakly compact. Then M is also compact in the weak ⋆ topology of P(S). Moreover, it is easily seen that if µ 1 , . . . , µ r ∈ M and α 1 , . . . , α r ∈ R then µ := α 1 µ 1 + • • • + α r µ r belongs to M too, hence M coincides with its affine hull. In particular, it is a convex set. Indeed, for each A 1 ∈ S n1 , . . . , A k ∈ S n k , it holds

P(S) k ν n1 1 (A 1 ) • • • ν n k k (A k ) µ(dν 1 , . . . , dν k ) = r i=1 α i P(S) k ν n1 1 (A 1 ) • • • ν n k k (A k ) µ i (dν 1 , . . . , dν k ),
according to the standard properties of Lebesgue integral. At this point, the assumption of S being a locally convex topological vector space implies S ⋆ separates points by [START_REF] Rudin | Functional Analysis[END_REF]Theorem 3.4]. It follows by Krein-Milman's theorem [24, Proposition 1.2] that M coincides with the closure of the convex hull of the extremal points of M itself. Then, it is claimed this is impossible if M is not a singleton. Indeed, in the opposite case, for each µ ∈ M there exists a distinct µ ′ ∈ M, with the consequence that µ cannot be an extremal point, since µ itself can be rewritten as

1 2 µ ′ + 1 2 (2µ -µ ′ ).
Of course, M cannot be equal to closure of the empty set. This completes the proof.

Proofs of Theorem 2 and 3

Proof of Theorem 2. According to the standing assumptions, there exists a probability measure µ on P(S) such that, for all nonnegative integers p j , q j , r j summing up to n j , and for each A j ∈ S and B j ∈ S qj , it holds

P((X i ) i∈Ij ∈ A pj j × B j × S rj , j = 1, . . . , k) = P(S) k k j=1 ν j (A j ) pj (ν j × • • • × ν j ) qj times (B j ) µ(dν 1 , . . . , dν k ).
The claim follows by Lemma 2, where each function f j is given by P(S) → R : ν → ν(A j ) and the function g j by P(S) → R : ν → ν qj (B j ).

Proof of Theorem 3. By the exchangeability assumption, it holds n i=0 n i x i = 1. Hence, we are asking for necessary and sufficient conditions on the (column) vector x = (x 0 , . . . , x n ) ′ such that there exists a probability measure µ : B[0, 1] → R for which x i = [0,1] p n-i (1 -p) i µ(dp)for all i = 0, 1, . . . , n. Moreover, let us define y i as the (n -i)-th moment of µ. It follows that the above conditions are equivalent to

x i = i j=0 i j
(-1) i+j y j [START_REF] Engelking | General Topology[END_REF] for each i = 0, 1, . . . , n, where by convention 0 0 = 1. In addition, define y = (y n , . . . , y 0 ) ′ and let A be the square matrix of dimension (n + 1) where the (i, j)-th element is

i -1 n + 2 -i -j (-1) i+j+n 1 [n+2,∞) (i + j).
Accordingly, the system (7) can be rewritten in matrix form as x = Ay. Since the determinant of A is 1, each y i can be rewritten uniquely as a linear combination of the x j .

Let us prove by induction that y i = i j=0 i j x j for each i = 0, 1, . . . , n. It is trivially true for n = 0, and let us suppose that it holds for all nonnegative integers smaller than n. Then, by the system [START_REF] Engelking | General Topology[END_REF] and the inductive hypothesis, we obtain

y n = x n - n-1 i=0 n i (-1) n+i y i = x n - n-1 i=0 n i (-1) n+i i j=0 i j x j = x n -(-1) n n-1 i=0 n i (-1) i i j=0 i j x j = x n -(-1) n n-1 j=0 x j n-1 i=j n i i j (-1) i .
Hence, it follows by Lemma 1 that

y n = x n -(-1) n n-1 j=0 n j (-1) n-1 x j = n j=0 n j x j . (8)
Having this in mind, the joint law of (X 1 , . . . , X n ) is a true mixture of i.i.d. {0, 1}-valued random variables if and only if there exists a probability measure µ : B[0, 1] → R which satisfies

p i µ(dp) = y n-i
for each i = 0, 1, . . . , n. This problem, commonly known as "reduced Hausdorff moment problem," have been extensively studied in literature; see, for instance, [26, pp. 8-9] and [START_REF] Hildebrandt | On the moment problem for a finite interval[END_REF]. According to [13, Theorem 1], a necessary and sufficient condition for the existence of a solution is that, if n is even, both matrices

      y n y n-1 • • • y n 2 y n-1 y n-2 • • • y n 2 -1 . . . . . . . . . . . . y n 2 y n 2 -1 • • • y 0       and       y n-1 -y n-2 y n-2 -y n-3 • • • y n 2 -y n 2 -1 y n-2 -y n-3 y n-3 -y n-4 • • • y n 2 -1 -y n 2 -2 . . . . . . . . . . . . y n 2 -y n 2 -1 y n 2 -1 -y n 2 -2 • • • y 1 -y 0      
are positive semi-definite, whereas in case n is odd, both matrices

       y n-1 y n-2 • • • y n-1 2 y n-2 y n-3 • • • y n-3 2 . . . . . . . . . . . . y n-1 2 y n-3 2 • • • y 0        and        y n -y n-1 y n-1 -y n-2 • • • y n+1 2 -y n-1 2 -1 y n-1 -y n-2 y n-2 -y n-3 • • • y n-1 2 -y n-3 2 . . . . . . . . . . . . y n+1 2 -y n-1 2 y n-1 2 -y n-3 2 • • • y 1 -y 0       
are positive semi-definite too. The claim follows by equation ( 8) and standard properties of the binomial coefficients.

Proof of Corollary 3. For each i = 1, . . . , 2⌊n/2⌋ -1, the inequality (5) follows by Lemma 2. Indeed, having fixed k = 1, m 1 = ⌊n/2⌋, A = {1}, and B = {0, 1} if n is odd, we obtain that the matrix

      x 2m x 2m-1 • • • x m x 2m-1 x 2m-2 • • • x m-1 . . . . . . . . . . . . x m x m-1 • • • x 0      
is positive semi-definite. In particular, each principal minor x i+1 x i x i

x i-1 has nonnegative determinant whenever i + 1 ≤ 2⌊n/2⌋. Therefore, we miss only to prove that, if n is odd, then x n-1 ≤ √

x n x n-2 . This is easily seen, according to Theorem 3, by choosing the 2 × 2 leading principal minor of K n , which has to have nonnegative determinant. Indeed, by the standard properties of the determinant, we conclude that

det y n -y n-1 y n-1 -y n-2 y n-1 -y n-2 y n-2 -y n-3 = det x n x n-1 x n-1 x n-2 ≥ 0.
On the other hand, for n ≤ 3, the sufficiency of these inequalities, follows by Theorem 3. Conversely, again by Theorem 3, given an integer n ≥ 4, it is enough to show the existence of a sequence (x 0 , . . . , x n ) such that the inequalities x i ≤ √ x i-1 x i+1 hold for all i = 1, . . . , n -1, while the matrix H n admits a principal minor with negative determinant. To this aim, set ).

(x 0 , . . . , x n ) = 1 3 • 2 n + 2n + 6 ( 9
Then, it is routine to check that this defines an exchangeable law on {0, 1} n , while, on the other hand, the 3 × 3 south-east principal minor has a negative determinant.

By Sylvester's criterion, a matrix is positive semi-definite if and only if its principal minors have nonnegative determinant. Therefore, Theorem 3 allows the establish whether each {0, 1}-valued exchangeable sequence (X 1 , . . . , X n ) is a true mixture of i.i.d. laws in o(2 n ) operations (indeed the number of principal minors of a matrix of dimension n is n i=1 n i 2 , which is asymptotically equal to 4 n √ πn ). Just to realize the computational burden related to Theorem 3, for n = 4, notice that the exchangeable law defined by the sequence (x 0 , . . . , x 4 ) is a true mixture of {0, 1}-valued i.i.d. random variables if and only if each of the following numbers are nonnegative:

(i) x 0 x 2 -x 2 1 ; (ii) x 1 x 3 -x 2 2 ; (iii) 2x 0 x 2 -2x 2 1 -x 2 x 1 + x 0 x 3 ; (iv) x 0 x 3 -x 2 1 -x 1 x 2 + x 3 x 1 -x 2 2 + x 0 x 2 ; (v) x 0 x 4 x 2 -x 4 x 2 1 + 2x 1 x 2 x 3 -x 3 2 -x 0 x 2 3 ; (vi) 4x 0 x 3 -4x 2 1 -4x 1 x 2 -x 2 2 + 4x 0 x 2 + x 0 x 4 ; (vii) 2x 0 x 2 + 3x 0 x 3 -3x 1 x 2 + x 0 x 4 + 2x 1 x 3 + x 1 x 4 -x 2 x 3 -2x 2 1 -3x 2 2 ; (viii) x 0 x 2 + 2x 0 x 3 -2x 1 x 2 + x 0 x 4 + 2x 1 x 3 + 2x 1 x 4 -2x 2 x 3 + x 2 x 4 -x 2 1 -3x 2 2 -x 2
3 . Nevertheless, it would be sufficient that the leading principal minors of H n and K n have positive determinants (in the above example, e.g., it means that x 0 , . . . , x 4 , and numbers (i), (ii), and (vii) are strictly positive). It is unclear whether this result could be extended to arbitrary spaces S.

Concluding remarks

Let (X 1 , . . . , X n ) be an exchangeable sequence over an arbitrary subset G. The representation provided in Theorem 1 gives, informally, the same amount of information when the assumption of exchangeability over G is replaced by the exchangeability over the largest subgroup contained in G. This highlights the differences with other types of exchangeability considered in the literature. To make some examples, fix an array X = (X i,j : 1 ≤ i ≤ n, 1 ≤ j ≤ m) of random variables and consider the following different notions of (finite) partial exchangeability: ⋄ (de Finetti, cf. [START_REF] De Finetti | Sur la condition d'equivalence partielle[END_REF]) The joint law of X is invariant under permutations of the random variables within each column: in this case, the information provided by our representation is maximal, since G can be written exactly as product of symmetric groups on the indexes of the columns; ⋄ (Aldous and Kallenberg, cf. [START_REF] Aldous | Representations for Partially Exchangeable Arrays of Random Variables[END_REF] and [START_REF]On the Representation Theorem for Exchangeable Arrays[END_REF]) The law of X is invariant under all pairs of (respectively, the same) permutations of the indexes of rows and columns; this is commonly known as separately row-column exchangeability (resp., jointly row-column exchangeability). For example, a 2 × 2 array is separately row-column exchangeable if and only if, up to relabelings to indices, it holds

X 1 X 2 X 3 X 4 d = X 2 X 1 X 4 X 3 d = X 3 X 4 X 1 X 2 d = X 4 X 3 X 2 X 1 .
This implies that the unique contained subgroup of permutations is the trivial one. In a sense, this minimizes the amount of information provided by our representation because it is as if there were no constraints.

Similar considerations apply to other types of invariance considered in literature, e.g., Markov exchangeability introduced by Diaconis and Freedman [START_REF] Diaconis | de Finetti's theorem for Markov chains[END_REF]. Lastly, notice that if G is the trivial subgroup of the symmetric group on {1, . . . , n}, then all joint laws of random vectors (X 1 , . . . , X n ) are exchangeable over G. Hence, Theorem 1 implies the existence of a bounded signed measure µ such that P (X 1 ∈ A 1 , . . . , X n ∈ A n ) = P(S) n ν 1 (A 1 ) • • • ν n (A n ) µ(dν 1 , . . . , dν n ) for all A 1 , . . . , A n ∈ S . This is not surprising. Indeed, joint laws can be always represented as true mixtures of product laws. To prove this, denote by q the measurable map S n → P(S) n : (s 1 , . . . , s n ) → (δ s1 , . . . , δ sn ). Then, it follows that, for all measurable sets A 1 , . . . , A n ∈ S , the probability P(X 1 ∈ A 1 , . . . , X n ∈ A n ) is equal to

Open questions

Generally, given a bounded signed measure µ on P(S) such that µ(P(S)) = 1, it is not true that the map

S n → R : A → P(S) ν n (A)µ(dν)
represents the joint law of some exchangeable sequence (X 1 , . . . , X n ) with values in S. Indeed, the integral may attain negative values. Accordingly, can we provide a characterization of the set M of such signed measures µ? Is there a way to represent µ itself?

In addition, with the notations of Theorem 1, is it true that n 1 + • • • + n k k → ∞ implies µ -(P(S)) → 0 ?

Finally, given subgroups G and G ′ such that G ⊆ G ′ , can we quantify how much M(G) is "larger" than M(G ′ )?

, 5 , 3 , 3 , 3 n- 1

 53331 . . . , times

P(S) n 1

 1 A1ו••×An (s 1 , . . . , s n )P(ds 1 , . . . , ds n ) = S n δ s1 (A 1 ) • • • δ sn (A n )P(ds 1 , . . . , ds n ) = P(S) n ν 1 (A 1 ) • • • ν n (A n )(P • q -1 )(dν 1 , . . . , dν n ).

Acknowledgments

The author is supported by a PhD scholarship from Università Bocconi. He thanks Nate Eldredge (Northern Colorado, US) and Pierpaolo Battigalli, Sandra Fortini, Fabio Maccheroni, Pietro Muliere, and Sonia Petrone (Università Bocconi, IT) for useful comments.