Emmanuel Filiot
email: emmanuel.filiot@lifl.frsophie.tison@lifl.fr

Sophie Tison

Regular n-ary Queries in Trees and Variable Independence

Regular n-ary queries in trees are queries which are definable by an MSO formula with n free first-order variables. We investigate the variable independence problem -originally introduced for databases -in the context of trees. In particular, we show how to decide whether a regular query is equivalent to a union of cartesian products, independently of the input tree. As an intermediate step, we reduce this problem to the problem of deciding whether the number of answers to a regular query is bounded by some constant, independently of the input tree. As a (non-trivial) generalization, we introduce variable independence w.r.t. a dependence forest between blocks of variables, which we prove to be decidable.

Introduction

Querying a tree consists of selecting nodes of its domain. This task has received a special interest from the XML community as it is fundamental to information extraction and document transformation. Several formalisms have been proposed to express unary queries [START_REF] Libkin | Logics over unranked trees: an overview[END_REF], but less work has been done on n-ary queries, ie the selection of n-tuples of nodes [START_REF] Berlea | On-the-fly tuple selection for XQuery[END_REF][START_REF] Filiot | Polynomial time fragments of xpath with variables[END_REF][START_REF] Niehren | N-ary queries by tree automata[END_REF]. Nevertheless, n-ary queries are of special interest, for instance to select tuples of the form (name, addr, email, phone, fax) in an XML document representing a directory. Since the arity of the query can easily get up to 10, efficiency becomes crucial to evaluate (n-ary) queries.

On the other hand, the notion of variable independence has been introduced in the context of (infinite) constraint databases [START_REF] Chomicki | Variable independence in constraint databases[END_REF][START_REF] Cosmadakis | On the orthographic dimension of definable sets[END_REF][START_REF] Grumbach | On the orthographic dimension of constraint databases[END_REF][START_REF] Libkin | Variable independence for first-order definable constraints[END_REF]. Query evaluation can be improved considerably when variables are independent. In particular, complexities of many evaluation algorithms on constraint databases are related to some independence between the components of the output tuples. For instance if the query can be decomposed into a Cartesian product of queries of lower arities, then all sub-queries of the product can be evaluated independently. Orthographic dimension has been proposed as a measure for variable independence [START_REF] Grumbach | On the orthographic dimension of constraint databases[END_REF]. It corresponds to the size of the largest block of dependent variables. It is shown in [START_REF] Cosmadakis | On the orthographic dimension of definable sets[END_REF] that this notion is well-defined, since every pair of decompositions can be intersected into a decomposition of lower maximal block size.

However, in the context of constraint databases, the structure is infinite but fixed. A natural question is whether these results carry over into the context of an infinite number of finite tree structures. The notion of variable independence is also closely related to the representation of the set of answers of an n-ary query. In particular, if the variables are independent, this allows to represent the set of answers as a Cartesian product of sets of (sub)answers of lower sizes. More generally, aggregated answers have been introduced in [START_REF] Meuss | Towards aggregated answers for semistructured data[END_REF] as a compact representation of the set of answers. Basically, these are multipartite dags such that each part corresponds to a free variable, and the branching structure of the parts is a tree. This branching structure somehow reflects the structure of the input tree. Consider for instance the tree of Fig. 1 representing a directory. Data are omitted in this picture. Consider the ternary query q which selects all triples (x, y, z) where x is labeled person, y is the first name of this person, and z one of its emails. Once x is selected, then y and z are independent. The set of answers to this query can be represented as a 3-partite graph with sets of vertices {V x , V y , V z }, where there is a directed edge from a node u of V x to a node v of V y , if v is the name of u. Similarly, edge relations between V y and V z correspond to the (person, email) relations of the input tree. A person may have several emails, making this representation more compact than the set of all answers. Moreover, as argued in [START_REF] Meuss | Towards aggregated answers for semistructured data[END_REF], this representation keeps the information on how the components of the output tuples are related in the tree. It is also particularly appropriate for post-processing tasks, such as answer searching, answer browsing, statistical computing, answer enumeration, and cascade-style querying. It raises the fundamental question of how compact this representation is. We answer this question by extending variable independence to relative independence. In particular, it allows more complex dependencies between variables, as emphasized by the previous example. We measure compactness in the settings of data-complexity, as we want to be independent of the query formalism.

To achieve the formal study of variable independence, we choose Monadic Second Order Logic to express n-ary queries, as it is often used as a yardstick logic in the context of trees [START_REF] Libkin | Logics over unranked trees: an overview[END_REF].

We show that variable independence is decidable for MSO queries in trees, and that a decomposition is computable. We reduce this problem to testing whether a query is bounded, i.e. its number of answers is bounded by some constant independent of the input tree. We prove this problem to be decidable. We show that the notion of orthographic dimension is also well-defined in the context of trees. Finally, we introduce variable independence w.r.t. to a dependence forest, which introduces dependencies between blocks of variables.

Note that in the context of trees, a restricted notion of variable independence has been investigated in [START_REF] Niehren | N-ary queries by tree automata[END_REF] and proved to be equivalent to non-ambiguity of tree automata.

Preliminaries

Although XML documents are usually modeled as unranked trees [START_REF] Libkin | Logics over unranked trees: an overview[END_REF], we consider finite binary trees only. All our results can easily be lifted to unranked trees via a binary encoding [START_REF] Libkin | Logics over unranked trees: an overview[END_REF].

Binary trees We consider a finite alphabet Σ consisting of symbols ranged over by a, f, g. A binary tree t over Σ is inductively defined by the following grammar: t ::= a | a(t, t) a ∈ Σ The set of binary trees over Σ is denoted by T Σ . The set of nodes N t of a tree t ∈ T Σ is a set of words over {0, 1}. We write ǫ for the empty word and u.u ′ for the concatenation of u and u ′ . The set N t is inductively defined by N a = ǫ and N a(t0,t1

) = {ǫ} ∪ {b.u | b ∈ {0, 1}, u ∈ N t b }. Nodes u ∈ N t for
which there is some b ∈ {0, 1} such that u.b ∈ N t are called inner-nodes. Other nodes are called leaves, and the node ǫ is called the root of t. Let Σ ′ be another finite alphabet. Let t ∈ T Σ and t ′ ∈ T Σ ′ be two binary trees such that N t = N t ′ . The product tree t × t ′ is the tree over Σ × Σ ′ inductively defined by: a

× b = (a, b), for all a ∈ Σ, b ∈ Σ ′ , and f (t 0 , t 1 ) × g(t ′ 0 , t ′ 1 ) = (f, g)(t 0 × t ′ 0 , t 1 × t ′ 1 ), for all f ∈ Σ, g ∈ Σ ′ , t 0 , t 1 ∈ T Σ and t ′ 0 , t ′ 1 ∈ T Σ ′ .
More generally, we can define the product of n trees modulo associativity of ×. Trees are also viewed as structures over the signature consisting of the binary successor symbols S 0 and S 1 and the unary symbols lab a , for all a ∈ Σ, interpreted by their intuitive meanings.

MSO Monadic Second Order (MSO) logic extends first-order logic with quantification over sets. We consider first-order (resp. second-order) variables ranged over by x, y (resp. X, Y ). MSO formulas consists of atomic formulas lab a (x), S 0 (x, y), S 1 (x, y) or x ∈ X, and are closed by boolean connectives ∧, ¬ and quantification ∃x, ∃X. We let t, ρ |= φ denotes the satisfaction relation and say that the formula φ holds in the tree t under the variable assignment ρ. We refer the reader to [START_REF] Libkin | Logics over unranked trees: an overview[END_REF] for more details about the semantics of MSO.

Definition 1 (regular n-ary queries). Let n ≥ 0. An n-ary query q is a mapping from trees t ∈ T Σ into subsets of N n t . It is regular (or MSO-definable) if there is an MSO-formula φ(x 1 , . . . , x n ) with n free first-order variables such that for all trees t, we have:

q(t) = {(ρ(x 1 ), . . . , ρ(x n )) | t, ρ |= φ(x 1 , . . . , x n )} If n = 0 (resp. n = 1, n = 2)
, q is called Boolean (resp. unary, binary). We also say that φ defines q and denote q by q φ . Those queries are called regular since there is a close correspondence between MSO-definable queries and tree automata. In particular, it is well-known that every MSO-definable n-ary query φ(x 1 , . . . , x n ) on trees over Σ can be represented as a tree automaton A over the alphabet Σ × {0, 1} n [START_REF] Niehren | N-ary queries by tree automata[END_REF][START_REF] Thatcher | Generalized finite automata with an application to a decision problem of second-order logic[END_REF][START_REF] Comon | Tree automata techniques and applications[END_REF]. Moreover, we can assume that A is canonical, i.e. for any tree t ∈ L(A), and any i ∈ {1, . . . , n}, there is exactly one node of t such that the (i + 1)-th component of its label is 1 [START_REF] Thatcher | Generalized finite automata with an application to a decision problem of second-order logic[END_REF][START_REF] Comon | Tree automata techniques and applications[END_REF]. The following holds: for all its nodes u 1 , . . . , u n of t, t |= φ(u 1 , . . . , u n ) iff

t×χ u1 ו • •×χ un ∈ L(A)
, where for all i ∈ {1, . . . , n}, χ ui is the tree on {0, 1} such that N t = N χu i and all nodes except u i are labeled 0.

Boundedness Properties of Regular Queries

In this section, we prove intermediate results which are useful for Section 4, but might be of independent interest. Let φ(x 1 , . . . , x n ) be an MSO formula whose free variables are first-order. We say that φ is bounded if there is K ∈ N such that for all t ∈ T Σ , the number of assignments ρ of variables x i s into N t such that t, ρ |= φ is bounded by K.

Lemma 1. Given an MSO formula φ(x 1 , . . . , x n ) with n free first-order variables x 1 , . . . , x n , it is decidable whether φ is bounded and, in this case, a bound is computable.

Proof. As said at the end of Section 2, φ can be represented as a canonical tree automaton A over Σ × {0, 1} n . Now, we can easily transform A in linear time into a bottom-up transducer T A which takes trees t 1 over Σ as inputs and outputs trees t 2 over {0, 1} n such that N t1 = N t2 and t 1 × t 2 ∈ L(A). Since for all trees t, we have |T A (t)| = |q φ (t)|, it suffices to test whether |T A (t)| is bounded by some constant, which is decidable in polynomial time (in the size of T A ). This is called finite valuedness in [START_REF] Seidl | Ambiguity, valuedness and costs[END_REF][START_REF] Seidl | Equivalence of finite-valued tree transducers is decidable[END_REF]. Moreover, for all fixed k ∈ N, one can decide in non-deterministic polynomial time whether the number of images by T A is greater than k [START_REF] Seidl | Ambiguity, valuedness and costs[END_REF][START_REF] Seidl | Equivalence of finite-valued tree transducers is decidable[END_REF] (with a constant factor which is several exponentials in the size of k). Moreover, the bound is lesser than 2 2 p(|T A |) for some polynomial p independent of T A . Hence, based on a dichotomy algorithm, one can compute the smallest upper bound. The time complexity however is several exponentials in the size of T A .

Concerning time complexity, it is known that the size of the tree automaton associated with φ might be non-elementary in the size of φ [START_REF] Thatcher | Generalized finite automata with an application to a decision problem of second-order logic[END_REF], making the whole procedure possibly non-elementary. However, if the query is given by a canonical tree automaton A, testing boundedness becomes polynomial in the size of A, since testing finite valuedness of a tree transducer can be done in polynomial time [START_REF] Seidl | Equivalence of finite-valued tree transducers is decidable[END_REF][START_REF] Seidl | Ambiguity, valuedness and costs[END_REF].

Lemma 1 could also be deduced from a result of [START_REF] Bojanczyk | A bounding quantifier[END_REF]. This paper considers an extension of MSO on infinite trees with bounding quantifiers. In particular, for any MSO formula ψ(X), the bounding quantified formula BX.ψ(X) holds in an infinite tree t, if there is a bound b ∈ N such that the size of any subset of the set of nodes of t that satisfies ψ(X) is bounded by b. Two fragments are proved to be decidable: formulas of the form ¬BX.ψ(X), where ψ is in MSO, and formulas built from arbitrary MSO formulas and B, ∃, ∨ and ∧. We can easily reduce our problem to satisfiability of some formula in the first fragment. First, boundedness of an n-ary query reduces to boundedness of all its projections. Hence, we only need to consider unary queries. Now, from a formula ψ(x) in one free variable, we construct a closed formula γ such that ψ(x) is bounded iff γ is unsatisfiable. The formula γ is a conjunction γ = γ 1 ∧ γ 2 . The first formula γ 1 checks whether the model is a tree (possibly infinite) of the form #(t 1 , #(t 2 , #(t 3 , . . .), for some fresh symbol # ∈ Σ and t 1 , t 2 , t 3 , . . . ∈ T Σ are finite trees over Σ. The second formula γ 2 has the form ¬BX.γ ′ (X), where γ ′ (X) is an MSO formula which holds in #(t 1 , #(t 2 , #(t 3 , . . .) under some assignment ρ if there is i ≥ 1 such that ρ(X) corresponds to the set of nodes u of t i such that t i |= ψ(u). The formula γ ′ is defined by first choosing some node x 0 labeled # and then relating ψ(x) under x 0 . However, we cannot benefit from this reduction if the query is given by a tree automaton (in term of time complexity).

An equivalence relation on n-tuples is a 2n-ary query , often denoted ≡, such that for all trees t, ≡ (t) is an equivalence relation on N n t . We let ≡ t stands for ≡ (t). It is regular if ≡ is regular. We say that ≡ is of bounded index if for all trees t, the number of ≡ t -equivalence classes is bounded by some constant which does not depend on the tree. We can define a regular query which selects the minimal representatives of the equivalence classes, for some MSO-definable order on tuples. Hence, as a corollary of Lemma 1, we get:

Corollary 1 (bounded index property). Let ≡ be a regular equivalence relation on n-ary tuples. It is decidable whether ≡ is of bounded index.

Proof. Let t be a tree, we define a total order ≤ t on N n t . It suffices to start from a total order on N t and to extend it to a lexicographic order ≤ t on N n t . Take for instance the lexicographic order on words over {0, 1} which is a total order on N t . We can easily show that the query t →≤ t is regular. Now, we define the n-ary query q min : t → {u | ∀u ′ ∈ N n t , u ≡ t u ′ =⇒ u ≤ t u ′ }. The query q min is regular. Finally it suffices to verify boundedness of q min , which is decidable by Lemma 1.

Beyond Trees

Deciding boundedness of an MSO formula can be done for classes of structures which are images of a regular set of trees by an MSO-transduction. We refer the reader to [START_REF] Courcelle | Structural properties of context-free sets of graphs generated by vertex replacement[END_REF] for a definition of MSO-transductions. Given a set of integers I ⊆ N, we say that I is linear if there are integers α 0 , . . . , α n ∈ N such that

I = {α 0 + n i=1 α i x i | x 1 , . . . , x n ∈ N}. It is semi-linear if it
is a finite union of linear sets. Let σ be a signature and C be a class of σ-structures, θ an MSO-transduction from binary trees to σ-structures such that C is the image by θ of a set of binary trees. In [START_REF] Courcelle | Structural properties of context-free sets of graphs generated by vertex replacement[END_REF], Courcelle proves 1 that given an MSO formula φ(X) over the signature σ with one free secondorder variable X, the set {#ρ(X) | M, ρ |= φ(X), M ∈ C} is semi-linear, and we can compute the coefficients of the polynomials if the transduction θ is known (#ρ(X) denotes the cardinality of ρ(X)). This is the case for instance for the class of graphs of clique-width less than k, for any fixed k [START_REF] Courcelle | Vertex-minors, monadic second-order logic, and a conjecture by seese[END_REF]. To decide boundedness of an MSO formula φ(x) (where x is first-order), it suffices to compute the above coefficients for the formula Φ(X) = ∀x, x ∈ X ↔ φ(x). The formula φ(x) is bounded iff the coefficients α 0 of the linear sets are the unique (possibly) non-null coefficients. Finally, boundedness of a formula φ(x 1 , . . . , x n ) reduces to boundedness of every projection of φ on a single variable x i , for all i ∈ {1, . . . , n}. Hence, boundedness is decidable, for instance, for structures of clique-width less than k, for any fixed k, or for unranked trees. However, to decide the bounded index property, we need an MSO-definable total order.

Variable Independence

The definition of variable independence was originally defined over a fixed structure [START_REF] Chomicki | Variable independence in constraint databases[END_REF][START_REF] Libkin | Variable independence for first-order definable constraints[END_REF]. We state it over the class of binary trees. We let φ be an MSO formula with free variables x 1 , . . . , x n , and P = {B 1 , . . . , B k } be a partition of {x 1 , . . . , x n }. We write x Bi , i = 1, . . . , k, to denote the tuple formed by variables of B i given in order. We say that φ conforms to P , denoted φ ∼ P , if φ is equivalent to a formula of the form N j=1 φ j,1

(x B1 ) ∧ • • • ∧ φ j,k (x B k ),
where N is a natural and φ j,i are MSO formulas with free variables in B i . Note that if we require N to be equal to 1, the problem becomes easy, since it suffices to test whether φ is equivalent to the conjunction of the k projections of φ on the variables from each block B i .

W.l.o.g., we assume that free variables of φ are ranked in order given by B 1 , . . . , B k . In other words, we assume x 1 , . . . , x n = x B1 , . . . , x B k (modulo associativity). Now, for any i ∈ {1, . . . , k}, and any tuples of variables x, y such that |x| = |y| = |B i |, we let ψ i φ (x, y) be the formula defined by:

ψ i φ (x, y) = ∀x B1 . . . ∀x Bi-1 ∀x Bi+1 . . . ∀x B k φ(x B1 , . . . , x Bi-1 , x, x Bi+1 , . . . , x B k ) ↔ φ(x B1 , . . . , x Bi-1 , y, x Bi+1 , . . . , x B k )
For any i ∈ {1, . . . , k}, and any tree t ∈ T Σ , we let R t i be the binary relation on

N |Bi| t defined by R t i = {(u, v) | t |= ψ i φ (u, v)}.
Intuitively, u and v are equivalent if one can substitute u with v, in any tuple selected by φ whose i-th block is u, and conversely. Lemma 2. Let i ∈ {1, . . . , k} and t ∈ T Σ . The following are true:

1. R t i is an equivalence relation on N |Bi| t ; 2. if φ is equivalent to some formula of the form N j=1 φ j,1 (x B1 )∧• • •∧φ j,k (x B k ), then the number of R t i -equivalence classes is bounded by 2 N .
Proof. We only prove the second point, as the first is easy. Given some natural i ∈ {1, . . . , k}, some tree t and some node tuples u, v of length |B i |, we let u ≡ t i v if there is some set F ⊆ {1, . . . , N } (possibly empty) such that for all j ∈ F , we have t |= φ j,i (u)∧φ j,i (v), and for all j ∈ {1, . . . , N }\F , we have t |= ¬φ j,i (u) ∧ ¬φ j,i (v). We can easily prove that ≡ t i is an equivalence relation on N

|Bi| t which has at most 2 N equivalence classes. We now prove that ≡ t i is a refinement of R t i , which will be sufficient to conclude. Let u, v be two node tuples of length |B i | such that u ≡ t i v. Let w 1 , . . . , w i-1 , w i+1 , . . . , w k be node tuples. We have t |= φ(w 1 , . . . , w i-1 , u, w i+1 , . . . , w k ) iff t |=

N j=1 φ j,1 (w 1 ) ∧ • • • ∧ φ j,i (u) ∧ • • • ∧ φ j,k (w k ) iff (by definition of ≡ t i ) t |= N j=1 φ j,1 (w 1 ) ∧ • • • ∧ φ j,i (v) ∧ • • • ∧ φ j,k (w k ) iff t |= φ(w 1 , . . . , w i-1 , v, w i+1 , . . . , w k ). Hence we get (u, v) ∈ R t i .
Lemma 3. If for all i ∈ {1, . . . , k}, there is some m i ∈ N such that for all trees t ∈ T Σ , the number of equivalence classes of R t i is bounded by m i , then φ ∼ P .

Proof. Let i ∈ {1, . . . , n}. We define a successor relation between equivalence classes, then we introduce formulas cl l i (x),l = 1, . . . , m i , to define the l-th equivalence class of R t i , in any tree t ∈ T Σ .

As already seen in the proof of Corollary 1, there is an MSO-definable total order ≤ on node tuples. We now define a successor relation S i φ between the minimal representatives (for ≤) of the equivalence relation defined by ψ i φ . Now, let the formula min i φ (x) holds if x is the minimal representative of some equivalence class. It can be defined by ∀y, ψ i φ (x, y) → x ≤ y. The relation S i φ is now defined by the following MSO formula:

S i φ (x, y) = x < y ∧ min i φ (x) ∧ min i φ (y) ∧¬(∃z, x < z < y ∧ min i φ (z))
We let s 0 (x) stand for ¬∃z, S i φ (z, x) and s l (x), l ∈ N stands for ∃y, s l-1 (y) ∧ S i φ (y, x). We now define cl l i (x) by ∃y, s l (y) ∧ ψ i φ (x, y), for all 1 ≤ l ≤ m i . Intuitively s l (x) holds in t under some assignment ρ if ρ(x) is the minimal representative of the l-th equivalence class of R t i , while cl l i (x) holds in t under ρ if ρ(x) belongs to the l-th equivalence class of R t i . Finally, we let L be the set of tuples of naturals l = (l 1 , . . . , l k ) such that 1 ≤ l i ≤ m i , i = 1, . . . , k, and we denote by β l (x 1 ) the formula ∃x 2 . . . x k , φ(x 1 , x 2 , . . . , x k ) ∧ k j=1 cl lj j (x j ). We let φ l be the formula

β l (x 1 ) ∧ cl l2 2 (x 2 ) • • • ∧ cl l k k (x k )
. We now prove that φ is equivalent to l∈L φ l . Let t ∈ T Σ and u 1 , . . . , u k node tuples of t such that t |= φ(u 1 , . . . , u k ). For all i ∈ {1, . . . , k}, we necessarily have t |= ψ i φ (u i , u i ). Hence, there is some natural l i ∈ {1, . . . , m i } such that t |= cl li i (u i ), i = 1, . . . , k. Let l = (l 1 , . . . , l k ). It is easy to see that t |= φ l (u 1 , u 2 , . . . , u k ). Conversely, suppose there is some tuple l = (l 1 , . . . , l k ) ∈ L such that t |= φ l (u 1 , . . . , u k ). In particular, we have t |= β l (u 1 ), hence there are some node tuples u ′ 2 , . . . , u As a consequence of Lemma 2 and 3, and Corollary 1, we get the main result:

Theorem 1. Given an MSO formula φ with free variables x 1 , . . . , x n and a partition P of {x 1 , . . . , x n }, it is decidable whether φ ∼ P holds or not. If it holds, a decomposition of φ is computable.

Orthographic Dimension

The notion of orthographic dimension has been introduced in [START_REF] Grumbach | On the orthographic dimension of constraint databases[END_REF] to measure the degree of independence between variables, over a fixed database. We define it for any tree structure. Given a formula φ(x 1 , . . . , x n ), the orthographic dimension d φ of φ is defined by d φ = min P : φ∼P max B∈P |B|. Theorem 1 gives us a naive algorithm to compute d φ : for each partition P of {1, . . . , n}, test whether φ ∼ P and compute max B∈P |B|. But as we next show, we can restrict the tests to 2-partitions. Given two partitions P, P ′ of {1, . . . , n}, we write P ⊓ P ′ for the refinement of P and P ′ . Formally, we have P ⊓ P ′ = {B ∩ B ′ | B ∈ P, B ′ ∈ P ′ } -∅. Theorem 1 of [START_REF] Cosmadakis | On the orthographic dimension of definable sets[END_REF] states well-definedness of the notion of orthographic dimension, for first-order logic on any vocabulary, over a fixed structure. In particular, it means that there is a unique partition whose largest block is equal to the orthographic dimension, such that the formula conforms to it. However, the proof given in [START_REF] Cosmadakis | On the orthographic dimension of definable sets[END_REF] also works if the structure is not fixed. Moreover, it also works as soon as the logic contains first-order quantifiers, negations, and Boolean connectives. Hence, it also proves the following: Theorem 2. Let φ be an MSO formula in n free first-order variables x 1 , . . . , x n , and P, P ′ be two partitions of {1, . . . , n}. If φ ∼ P and φ ∼ P ′ , then φ ∼ P ⊓ P ′ . Now, let P = {P |P is a 2-partition of {1, . . . , n} and φ ∼ P }. From Theorem 2, we can deduce that the orthographic dimension of φ is the size of the largest block of ⊓ P ∈P P . Moreover, by Theorem 1, we can compute a decomposition which corresponds to the orthographic dimension.

Relation to the Answer Set Representation

If φ ∼ P , then for any tree t ∈ T Σ , we can represent q φ (t) by an aggregated answer of size O(n|t| d φ ), computable in time O(n|t| d φ ) (φ is assumed to be fixed). Indeed, φ is equivalent to a (computable) formula of the form:

N i=1 φ i,1 (x B1 ) ∧ . . . ∧ φ i,k (x B k )
for some natural N . For every i ∈ {1, . . . , N }, and j ∈ {1, . . . , k}, we compute an automaton A i,j over Σ × {0, 1} |Bj| such that we can compute in time O(|t| |Bj | |A i,j |) the set q φi,j (t) [START_REF] Courcelle | Linear delay enumeration and monadic second-order logic[END_REF]. The answer representation can be identified to the collection of k-tuples (q φi,1 (t), . . . , q φ i,k (t)).

Relative Variable Independence

In this section, we generalize variable independence w.r.t. a partition to variable independence w.r.t. a dependence forest on free variables. Consider for instance the tree of Fig. 1, andlet φ(x, y, z) be an MSO formula, where x denotes a person, y its first name and z one of its emails. Once the interpretation of x is fixed, then y and z are independent. We call this relative independence. Let T be the tree x(y, z), we say that φ conforms to T , denoted φ ∼ T . We next show that relative independence is decidable as a consequence of Theorem 1.

As a slight generalization, we allow dependence forests to specify dependences between sets of variables instead of single variables. For example, if a formula φ(x, y, z, w) conforms to some dependence forest {x, y}({z}, {w}), it means that once x and y are selected, then z and w are independent. Formally, let V = {x 1 , . . . , x n } be a finite set of variables. A dependence forest F over V is a forest whose nodes are labeled by subsets of 2 V and such that the set of labels occurring in F form a partition of V . If F has only one root, then it is called a dependence tree. We often denote by {T 1 , . . . , T k } a dependence forest consisting of the dependence trees T 1 , . . . , T k , and by V ′ (F ) a dependence tree consisting of a dependence forest F rooted by a set V ′ ⊆ V . Although we take a graph point of view, we use the same notations as for binary trees to denote the set of nodes of some forest F over V and its labeling function, respectively by N F and lab F : N F → 2 V . Finally, we confuse the set and tuple notations for variables, so that we sometimes write V = x, for some tuple of variables x. Let φ(x 1 , . . . , x n ) be an MSO formula in n free first-order variables x 1 , . . . , x n . Let µ be a mapping from N F into MSO formulas. We say that µ is admissible for F if for all nodes u, v ∈ N F , if u is the parent of v, then µ(v) is an MSO formula ψ whose free variables are lab F (u) ∪ lab F (v); if u is the root of F , then we require that µ(u) is an MSO formula whose free variables are lab F (u). If µ is admissible, we naturally extend it to an MSO formula µ(F ) = u∈NF µ(u) in free variables x 1 , . . . , x n . Definition 2. We say that φ conforms to F , denoted φ ∼ F , if there is a finite sequence µ 1 , . . . , µ N of admissible mappings for F such that φ is equivalent to

N i=1 µ i (F ).
We prove decidability of relative independence. We start by a base lemma (Lemma 4), for forests of the form x({y, z}). Then we give a recursive algorithm for the general case, that uses Lemma 4 and Theorem 1.

Lemma 4. Given an MSO formula φ(x, y, z) with free variables x, y, z, it is decidable whether φ is equivalent to some disjunction of the form n i=1 α i (x, y) ∧ β i (x, z), for some natural n, and MSO formulas α i , β i for i = 1, . . . , n. Moreover if it holds, a disjunction is computable.

Proof. Intuitively, we fix the interpretation of x by extending the alphabet with Boolean tuples. This gives a formula φ x (y, z), and we test whether φ x (y, z) ∼ {y, z}.

More formally, we first transform φ(x, y, z) into φ x (y, z), interpreted on trees over the alphabet Σ × {0, 1} m , where m = |x|, such that the following property holds (P 1 ): for all trees t, all nodes u 1 , . . . , u m ∈ N t , and all node tuples v, w, we have

t |= φ(u 1 , . . . , u m , v, w) iff t × χ u1 × • • • × χ um |= φ x (v, w)
, where the trees χ ui are defined at the end of Section 2. This can be done by repeating exhaustively the following transformation rule on φ: replace each atom of the form P (x 1 , x, x 2 ), where x is the i-th component of x and is a free occurrence in φ, by ∃x, (f,b)∈Σ×Bi lab (f,b) (x) ∧ P (x 1 , x, x 2 ), where B i ⊆ {0, 1} m is the set of Boolean tuples whose i-th component is 1 for i = 1, . . . , m. Hence, φ(x, y, z) rewrites to some formula φ ′

x (y, z). We define φ x by φ ′

x ∧ φ can , where φ can is a sentence which ensures that all models t ∈ T Σ×{0,1} m of φ x are canonical (ie all nodes except one have their i-th component set to 0 i = 1, . . . , n). We call R 1 the transformation from φ to φ x .

Then it suffices to test whether φ x (y, z) ∼ {y, z}, which is decidable by Theorem 1. If it holds, then φ x (y, z) is equivalent to some formula of the form ψ x (y, z) = n i=1 α i,x (y) ∧ β i,x (z), for some MSO formulas α i,x , β i,x . We next consider the following transformation rule R 2 : replace each Algorithm 1 Testing Relative Independence procedure D(φ,F ) 2:

case F is a leaf or is of the form x(y): return φ 4:

case F is of the form {x1, . . . , x k }: 6:

test whether φ ∼ {x1, . . . , x k } as in the proof of Theorem 1 and return a decomposition. Otherwise breaks.

8:

case F is of the form x(y, z): test whether φ ∼ x(y, z) as in the proof of Lemma 4 and return a decomposition. Otherwise breaks. 10:

case F is of the form x(y(F ′ ), F ′′ ): 12:

z ′ , z ′′ ← sets of variables occurring in

F ′ , F ′′ W i αi(x, y, z ′ ) ∧ βi(x, z ′′ ) ← D(φ, x({y ∪ z ′ , z ′′ })) 14: return W i D(αi, y(F ′ , x)) ∧ D(βi, x(F ′′ ))
16: case F is of the form {T1, . . . , T k }: for i ∈ {1, . . . , k} do 18:

xi ← set of variables occurring in Ti

W n i=1 V k j=1 α j i (xj ) ← D(φ, {x1, . . . , x k }) 20: return W n i=1 D(α 1 i , T1) ∧ • • • ∧ D(α k i , T k )
atom of the form lab f,b (x) by lab f (x) ∧ bi=1 x i = x, where b i denotes the i-th component of b, i = 1, . . . , m. Suppose that x = x 1 , . . . , x m . Applying exhaustively this transformation rule on ψ x leads to a formula ψ(x, y, z) of the form n i=1 α i (x, y) ∧ β i (x, z) interpreted on trees over Σ. We have the following property (P 2 ): for all trees t, all nodes u 1 , . . . , u m ∈ N t , and all node tuples v, w, we have

t |= ψ(u 1 , . . . , u m , v, w) iff t × χ u1 × • • • × χ um |= ψ x (v, w).
Finally, we prove this algorithm to be correct. Suppose that it returns a decomposition. By combining properties P 1 and P 2 , we can prove correctness of this decomposition. Conversely, suppose that φ is equivalent to some formula of the form n i=1 α i (x, y) ∧ β i (x, z). It is easy to see that φ x is equivalent (here we use canonicity of its models) to n i=1 α i,x (y) ∧ β i,x (z), where φ x , α i,x (y) and β i,x (z) are obtained by applying the rewrite rule R 1 on respectively φ, α i (x, y) and β i (x, z). Hence, φ x ∼ {y, z}, and the proof follows since the algorithm of the proof of Theorem 1 is sound. Now, we extend the result of Lemma 4 to full independence forests: Theorem 3. Given a formula φ in free variables V = {x 1 , . . . , x n } and a dependence forest F over V , it is decidable whether φ ∼ F holds or not.

Proof. Consider Algorithm 1. The inputs are a formula φ with free variables V and a dependence forest F over V . The symbols T 1 , . . . , T k denote dependence trees while F ′ , F ′′ denote (possibly empty) dependence forests. First note that the algorithm terminates. Indeed, the number of nodes of the forest strictly decreases at each recursive call except for the 4th case when F ′′ is empty, but in this case the height of the forest strictly decreases. Now, we can prove (inductively and by using Theorem 1 and Lemma 4 for the basic cases) that if this algorithm returns a formula, then it is a decomposition of the input formula φ w.r.t. the input forest F . It suffices to push up the disjunctive connectives to get a sequence of admissible mappings for F . Conversely, let φ (resp. F ) be an input formula (resp. an input dependence forest), such that we have φ ∼ F . We prove by induction that the algorithm outputs a decomposition. We use the fact that the decomposition is not arbitrary, but has a particular form, derived from the algorithms given in the proofs of Theorem 1 and Lemma 4. The first case is obvious, and the two next cases have already been proved. First remark that we have the following property (*): let F be a dependence forest, γ 1 , γ 2 two formulas, α a sentence and β(x) a formula such that x is a label of

F . If γ 1 ∼ F and γ 2 ∼ F , we have γ 1 ∨ γ 2 ∼ F , γ 1 ∧ γ 2 ∼ F , ¬γ 1 ∼ F , α ∧ γ 1 ∼ F , and β(x) ∧ γ 1 ∼ F .
Suppose that F is of the form x(y(F ′ ), F ′′ ). Since φ ∼ F , in particular, φ ∼ x(y ∪ z ′ , z ′′ ), where z ′ , z ′′ are defined as in Algorithm 1. Now, we inspect the proof of Lemma 4. Let φ x be the result of applying the rewriting rule R 1 of this proof. It is clear, by hypothesis, that we have φ x ∼ {y ∪ z ′ , z ′′ }. Hence, algorithm of the proof of Theorem 1 outputs a decomposition of the form l∈L β l 1 (y, z ′ ) ∧ cl l2 2 (z ′′ ), exactly as defined in the proof of Theorem 1. We let ψ -1 be the result of applying exhaustively the rewrite rule R 2 of the proof of Lemma 4 on ψ, for all formulas ψ. Hence, D(φ, x(y ∪ z ′ , z ′′ )) returns the formula l∈L (β l 1 ) -1 (x, y, z ′ ) ∧ (cl l2 2 ) -1 (x, z ′′ )). It remains to prove that formulas (β l 1 ) -1 and (cl l2 2 ) -1 satisfy (β l 1 ) -1 ∼ y(x, F ′ ) and (cl l2 2 ) -1 ∼ x(F ′′ ). We only prove it for formulas (cl l2

2 ) -1 , as the proof for formulas (β l 1 ) -1 is analogous. So let us fix some natural l 2 . By going back to the definition of formula cl l2 2 , we can prove that (cl l2 2 ) -1 is equivalent to a formula of the form Γ = ∃z 0 , γ(x, z 0 ) ∧ ∀u, φ(x, u, z ′′ ) ↔ φ(x, u, z 0 ), for some γ. Now, since φ ∼ F , it easy to see that φ is equivalent to a formula of the form

Ψ = n i=1 ǫ 1 i (x, y, z ′ ) ∧ ǫ 2 i (x, z ′′ ), such that ǫ 1 i ∼ y(x, F ′ ) and ǫ 2 i ∼ x(F ′′ ) for i = 1, . . . , n.
We replace in Γ the formula φ by Ψ , and, after a series of rewritings (by pushing up disjunctions and pushing down quantifiers), we can prove that (cl l2

2 ) -1 is equivalent to a formula of the form n i=1 γ i (x)ǫ 2 i (x, z ′′ ) ∨ P ⊆{1,...,n} γ ′ P (x) ∧ i∈P ¬ǫ 2 i (x, z ′′ ), for formulas γ i , γ ′ P depending only on i and P . The conclusion follows by property ( * ) and the fact that every ǫ 2 i satisfies ǫ 2 i ∼ x(F ′′ ). Suppose now that F is of the form {T 1 , . . . , T k }, let x i be the variables occurring in T i for i = 1, . . . , k, and let P = {x 1 , . . . , x k }. Since φ ∼ F , in particular, φ ∼ P . Hence D(φ, P ) outputs a decomposition of the form l∈L β l 1 (x 1 ) ∧ cl l2 2 (x 2 ) ∧ . . . ∧ cl l k k (x k ), exactly as defined in the proof of Theorem 1. We have to prove that for all l = (l 1 , . . . , l k ) ∈ L, we have β l 1 ∼ T 1 , and cl li i ∼ T i for i = 2, . . . , k. This is sufficient, since by induction hypothesis, D will output a decomposition of every β l 1 and cl li i . We only prove it for formulas cl li i (x i ), as it is similar for formulas β l 1 . Let us fix some l and i. We come back to the definition of cl li i , and we can easily show that it is of the form ∃y, γ(y) ∧ ψ i φ (x i , y), for some formula γ which selects the minimal representatives of the l i -th equivalence class of the relation defined by ψ i φ , where ψ i φ has been defined in Section 4. Now, since φ ∼ F , φ is equivalent to a formula of the form Ψ = n p=1 k j=1 ǫ j p (x j ) such that every ǫ j p satisfy ǫ j p ∼ T j . Next, in ∃y, γ(y) ∧ ψ i φ (x i , y), we replace φ by Ψ (ψ i φ can be viewed as the result of applying the function ψ i . on φ, and we just replace ψ i φ (x i , y) by ψ i Ψ (x i , y)). We get a formula equivalent to cl li i which, after a series of rewritings preserving equivalence (by moving up disjunctions and pushing down quantifiers), rewrites to a formula (equivalent to cl li i ) of the form n p=1 φ p ∧ ǫ i p (x i ) ∨ Q⊆{1,...,n} ψ Q ∧ p∈Q ¬ǫ i p (x i ), for some closed formulas φ p , ψ Q depending on p and Q. The conclusion follows by using property (*) and the fact that every ǫ i p satisfies ǫ i p ∼ T i .

Similarly as the case of variable independence, if φ(x 1 , . . . , x n ) conforms to F , then for any tree t ∈ T Σ , q φ (t) can be represented by an aggregated answer of size O(n|t| b ) (φ is assumed to be fixed, and necessarily |F | ≤ n). The parameter b denotes the maximal sum of the size of a label of F plus the size of the label of its father if it exists.

Note that variable independence w.r.t. a dependence forest subsumes variable independence w.r.t. a partition, since a partition can be viewed as a dependence forest consisting of a set of leaves. Moreover, as stated by the next theorem, there is an MSO formula φ such that there is no dependence forest F such that: (i) labels of F are singletons (ii) φ ∼ F . Nevertheless, we know that on trees, every MSO formula is equivalent to an existentially quantified Boolean combination of MSO formulas in two free variables [START_REF] Schwentick | On diving in trees[END_REF][START_REF] Filiot | Polynomial time fragments of xpath with variables[END_REF]. Theorem 4. There is an MSO formula φ such that there is no dependence forest F whose labels are singletons and such that φ ∼ F .

Finally, we would like to extend independence w.r.t. a dependence forest to independence w.r.t. a dependence graph. The techniques presented here do not seem to be easily extendable to graphs, even for a clique of size 3 for instance. In particular, we cannot use an inductive proof based on Lemma 4 anymore.

Fig. 1 .

 1 Fig. 1. A tree representing a directory

  ∈ {2, . . . , k}, we have t |= φ(u 1 , . . . , u p , u ′ p+1 , . . . , u ′ k ). It is true for p = 1 by hypothesis. Suppose that it is true at rank p > 1. Since t |= cl lp+1 p+1 (u p+1 ), we also have t |= ψ p+1 φ (u p+1 , u ′ p+1 ). By induction hypothesis, we have t |= φ(u 1 , . . . , u p , u ′ p+1 , . . . , u ′ k ), and by definition of ψ p+1 φ , we easily get t |= φ(u 1 , . . . , u p , u p+1 , u ′ p+2 , . . . , u ′ k ).

	′ k , such that t |= i ). We now prove by induction that for i (u ′ k ), and for each i ∈ {2, . . . , k}, t |= cl li 2 , . . . , u ′ φ(u 1 , u ′
	all p

Acknowledgments

We are very grateful to the anonymous referees for their valuable comments, to Bruno Courcelle who pointed out some references and to Slawomir Staworko for his careful re-reading.

Proof. Let x y be an MSO formula which holds in a tree if y is a descendant of x. It is wellknown that it can easily be defined as the reflexive and transitive closure of S 1 ∨ S 2 , this closure being definable in MSO. Now, let φ(x, y, z) be an MSO formula defined by:

For all trees t and all nodes u, v, w of t, we have t |= φ(u, v, w) iff the least common ancestor of u and v is equal to the least common ancestor of u and w.

We now prove by applying algorithm 1 that there is no forest F whose labels are singletons such that φ ∼ F , by proving it for each forest over {x, y, z}. Let n ≥ 0 and t n be the tree over the alphabet {a} inductively defined by t 0 = a and t n = a(t n-1 , a). For all n, we denote by v 0 , v 1 , . . . , v n the nodes 1 n , 1 n-1 , . . . , ǫ respectively, and, if n > 0, by w 1 , . . . , w n the nodes 1 n-1 .2, 1 n-2 .2, . . . , 2 respectively.

1. F = {x, y, z} or F = {x, y(z)} or F = {x, z(y)}. We apply algorithm 1. The formula ψ 1 φ (x, x ′ ) is defined by ∀y, z φ(x, y, z) ↔ φ(x ′ , y, z). We prove that for all n, and all i, j ≤ n,

Hence, the number of classes of the equivalence relation defined by ψ 1 φ is at least n, which is unbounded. So Algorithm 1 breaks; 2. F = {y, x(z)} or F = {y, z(x)}. The formula ψ 2 φ (y, y ′ ) is defined by ∀x, y, z φ(x, y, z) ↔ φ(x, y ′ , z). We prove that for all n, and all i, j ≤ n,

Hence, the number of classes of the equivalence relation defined by ψ 2 φ is at least n, which is unbounded. So Algorithm 1 breaks; 3. F = {z, y(x)} or F = {z, x(y)}. Those cases are symmetric to the previous ones. 4. F = x(y, z). We let ψ(y, y ′ ) = ∀z, φ x (y, z) ↔ φ x (y ′ , z) where φ x has been defined in the proof of Lemma 4. By definition of Algorithm 1, if the equivalence relation defined by ψ has an unbounded index, then the algorithm fails. This is what we next prove. Let n ≤ 0. We fix x by a Boolean in the tree t n : we let t ′ n be the tree over {a} × {0, 1} such that N tn = N t ′ n and all nodes are labeled (a, 0) except v 0 which is labeled (a, 1). It is easy to see that for all i ≥ 1, we have t ′ n |= φ x (v i , w i ) and for all j > i, we have t ′ n |= φ x (v j , w i . Hence there are at least n equivalence classes for the relation defined by ψ. So Algorithm 1 breaks. 5. F = y(x, z). Similarly to the previous case, we fix a variable. Let ψ(z, z ′ ) = ∀x, φ y (x, z) ↔ φ y (x, z ′ ). Let t ′ n be the tree defined in the previous case. Hence y is fixed to denote the node v 0 . We can prove that for all i > 0, we have t ′ n |= φ y (v i , w i ) but for all j > i, we have t ′ n |= φ y (v i , w j ). Hence there are at least n equivalence classes for the relation defined by ψ. So Algorithm 1 breaks. 6. F = z(x, y). This case is symmetric to the previous one.

Further Extensions

First note that all the results presented in the paper also hold for FO-queries, as we do not use second order variables in decompositions (but in this case we need to add in the tree structure a total order on the nodes). We would like to investigate independence problems for more general classes of structures C. Indeed, we can give two sufficient conditions for relative independence to be decidable on C: (i) boundedness of an MSO formula with first-order variables is decidable on C, (ii) there is a computable MSO-definable total order on the elements of the structures of C. The first point has already been detailed in Section 3, while the second point is studied in [START_REF] Courcelle | The monadic second-order logic of graphs x: linear orderings[END_REF]. This is the case for instance for unranked tree structures, over the signature consisting of the first-child and nextsibling predicates, and predicates to test the labels.


Cindy E Morris

Caroline Monteil

Odile Berge

come

O01.004 Novel understanding of the water cycle as a link between unsuspected habitats of airborne pathogens -what consequences for plant disease management?

C.E. Morris. C.L. Monteil and O. Berge INRA,Plant Pathology Research Unit 407,Montfavet,France Email: cindy.morris@avignon.inra.fr Recent research on the ecology of the phytopathogenic bacterium Pseudomonas syringae has revealed that its life history is intimately linked to the water cycle. As a consequence, the current vision of its ecology is moving away from that of a ubiquitous epiphytic plant pathogen to one of a multifaceted bacterium sans frontières in fresh water and other ecosystems linked to the water cycle. lts life history involves adaptation to ubiquity that is facilitated by dissemination via the water cycle and includes an important aspect of atmospheric transport as well as infiltration through soil. This new vision of its life history also integrates spatial and temporal scales spanning billions of years and traversing catchment basins, continents, and the planet and confronts the implication of roles that are potentially conflicting for agriculture (as a plant pathogen and as an actor in processes leading to rain and snowfall). Overall, it sets the stage for the integration of more comprehensive contexts of ecology and evolutionary history into comparative genomic analyses to elucidate how P. syringae subverts attack and defense responses of the cohabitants of the diverse environments it occupies. In practical terms this new ecological perspective has also yielded insight into epidemiological phenomena linked to disease emergence. This latter point will be explored in particular in this presentation and its pertinence for other plant pathogens will be discussed.


The influence of nitrogen (N) fertilization on a plant's susceptibility to pathogens is fairly well documented. However, little is known about possible effects on spore production by fungal pathogens on diseased tissue and on the aggressiveness of this resulting secondary inoculum. To address this question, sporulation by two strains of Botrytis cinerea was quantified on tomato plants produced in hydroponic conditions under different N irrigation regimes with inputs of nitrate from 0.5 to 45 mmol per liter (mM). Sporulation decreased significantly (P < 0.05) with increasing N fertilization up to 15 to 30 mM nitrate. The spores were collected and used to inoculate tomato plants produced under a standard fertilization regime. The aggressiveness of this secondary inoculum was significantly influenced by the nutritional status of its production substrate. Disease severity was highest with spores produced on plants with very low or very high N fertilization (0.5 or 30 mM nitrate). It was lowest for inoculum from plants with moderate levels of N fertilization. The results will be discussed in terms of possible mechanisms involved and in terms of potential consequences for disease control.

P11. 005

 005 Can nitrogen nutrition of the host plant influence the aggressiveness of secondary inoculum? The intriguing case of Botrytis cinerea on tomato MA. Abro, F Lecompte, F Bryone and P.C. Nicot INRA, UR407 Pathologie végétale, Domaine Saint Maurice, CS 60094, F-84143 Montfavet cedex, France Email: philippe.nicot@avignon.inra.fr


come

Toxoplasma gondii: qualified to secrete exosomes?


Comment citer ce document : Maisonneuve, B. (2011). Improvement of the differential lettuce set for Bremia virulence evaluation: new sativa monogenic lines. In: Proceedings Eucarpia Leafy Vegetables 2011 (p. 61).

Presented at Eucarpia Leafy Vegetables 2011, Lille, FRA (2011-08-24 -2011-08-26).

Proceedings

Theo Hendriks Marie-Christine Quillet Jean-Louis Hilbert To produce a universal susceptible line and to eliminate Rcg from the differential line CGDM16, the cross [CGDM16 x F 1 (Cobham green x LSE/18)] was produced. Progeny of that cross was tested with Serr84/99, a Bremia strain isolated by A. Lebeda in the French Alps which was not virulent on Cobham green. Only 18 I 1 progenies of 100 hybrid plants [CGDM16 x F 1 (Cobham green x LSE/18)] were in segregation for the resistance to Serr84/99; 8 out of these 18 I 1 families were homogeneous resistant and 10 showed segregation for Dm16 resistance. In the progenies from these 18 selected hybrid plants, I 2 families were produced on 71 I 1 plants tested as susceptible to Serr84/99. The capitulum of these 71 plants was observed and the I 2 progenies were tested with Serr84/99; therefore 14 lines I 2 susceptible to Serr84/99 and with an erect capitulum were selected. A ring test was realized with Serr84/99 and Bl:22 in 6 laboratories: one line without resistance (susceptible to Bl:22 or NL2) and 8 lines with Dm16 (resistant to Bl:22 or NL2) were selected. These 9 lines were tested with the 16 UPOV strains of Bremia used for cultivar inscription in Europe, and 2 I 2 were selected: one line (Rcg + , Dm16 + ) and one line (Rcg + , Dm16). These two lines are good candidates as a susceptible genotype and as a Dm16 line in the set of lettuce differentials for Bremia evaluation.

To create a differential line with only Rsal-1, a screening in the progenies from (Discovery x Angie) was realized with Bl:17 to eliminate Dm6 from Angie (a cultivar Dm6, Rsal-1) and the strain FR30/99 (sextet 63-62-16-01) to eliminate Dm7 from Discovery. In a first step, 22 out of 287 F 3 families, issued from 287 harvested F 2 (Discovery x Angie) plants, were selected as homozygous for Dm6 + and Dm7 + (susceptible to Bl:17 and to FR30/99). After a ring test in 6 laboratories, 5 F 3 were selected and tested with the 16 UPOV strains of Bremia; the results were up to expectation except with Bl:5. In conclusion, interesting candidates for Bremia differential lines were obtained to replace (1) Cobham green by a line susceptible to all know Bremia strains, called FrDm0, (2) CGDM16 by a monogenic Dm16 sativa line, called FrDm16, and (3) Ninja and Discovery by a monogenic Rsal-1 line, called FrRsal-1. The partners of that project decided to improve the homogeneity of these F 3 lines with one extra generation of selfing and observations on the morphology of the lines. An extra control of the conformity of the susceptibility/resistance especially with Serr84/99 and with Bl:5 will be also realized before proposing the material to the IBEB group.

Vegetables 2011 Proceedings August 24-26, 2011 Université Lille Nord de France Villeneuve d'Ascq France

  Improvement of the differential lettuce set for Bremia virulence evaluation: new sativa monogenic lines. In: Proceedings Eucarpia Leafy Vegetables 2011 (p. 61).

	Presented at Eucarpia Leafy Vegetables 2011, Lille, FRA (2011-08-24 -2011-08-26).

Comment citer ce document : Maisonneuve, B. (2011). Improvement of the differential lettuce set for Bremia virulence evaluation: new sativa monogenic lines. In: Proceedings Eucarpia Leafy Vegetables 2011 (p. 61). Presented at Eucarpia Leafy Vegetables 2011, Lille, FRA (2011-08-24 -2011-08-26).

EUCARPIA Leafy

Comment citer ce document : Maisonneuve, B. (

2011

).

Improvement of the differential lettuce set for Bremia virulence evaluation: new sativa monogenic lines Maisonneuve Brigitte INRA

  , UR 1052, Unité de Génétique et d'Amélioration des fruits etLégumes, Domaine Saint Maurice, 84143-Montfavet Cedex, France. Contact: Brigitte.Maisonneuve@avignon.inra.fr Key words: Lactuca, downy mildew, differential set, resistance Several accessions of the actual set of host differentials are difficult to use to determine the virulence of Bremia isolates; some are Lactuca serriola with reflex capitula and slow germination, some are not monogenic, like Ninja (Dm3, Dm4, Dm11, and a resistance from L. saligna called here Rsal-1) or Discovery (Dm7, Rsal-1). Besides, some Bremia isolated recently on some cultivars do not sporulate on Cobham green, the accession used as universal susceptible. In collaboration with 5 breeding societies (Enza Zaden, Gautier Semences, Rijk Zwaan, Seminis, Syngenta) and the Geves-Snes, and with some financial support from French Agricultural Ministry, a project was developed to create some new differential lines: a susceptible line without the resistance from Cobham green (called Rcg here), a sativa monogenic line with Dm16 to replace L. serriola LSE/18, and the sativa line CGDM16 (Dm16, Rcg), a monogenic line with Rsal-1 to replace Ninja and Discovery.