Sylvain Rousseau
email: sylvain.rousseau@ec-lille.fr

Pierre Chainais
email: pierre.chainais@ec-lille.fr

Christelle Garnier
email: christelle.garnier@telecom-lille.fr

DICTIONARY LEARNING FOR A SPARSE APPEARANCE MODEL IN VISUAL TRACKING

Keywords: dictionary learning, sparse coding, particle filtering, object tracking

This paper presents a novel approach to visual object tracking based on particle filtering. The tracked object is modelled by a sparse representation provided by dictionary learning. Such an approach permits to describe the target by a model of reduced dimension. The likelihood of a candidate region is built on a similarity measure between the sparse representations of a set of patches (at known positions) in the dictionary learnt from the reference template. Experimental validation is performed on various video sequences and shows the robustness of the proposed approach.

INTRODUCTION

Tracking objects in a video sequence is an essential task in computer vision. Among the many tracking methods (see [START_REF] Yang | Recent advances and trends in visual tracking: A review[END_REF]), particle filters are currently widely used. The performance strongly depends on the appearance model used to characterise the target object and on the likelihood function which measures the similarity between the candidate region and the reference object. Recently new models based on sparse representation, initially introduced in [START_REF] Bruno | Emergence of simple-cell receptive field properties by learning a sparse code for natural images[END_REF], have been successfully applied in visual tracking [START_REF] Zhang | Sparse coding based visual tracking: Review and experimental comparison[END_REF]. A global sparse appearance model is proposed in [START_REF] Mei | Robust visual tracking using 1 minimization[END_REF]. The dictionary is composed of two parts: target templates used to represent the entire object and trivial templates introduced to account for noisy pixels. A candidate is then sparsely represented with a few atoms of the complete dictionary. The likelihood is related to the reconstruction error in the target dictionary. The discriminative ability of the method can be improved by adding background templates in the dictionary [START_REF] Zhong | Robust object tracking via sparsity-based collaborative model[END_REF]. To better handle partial occlusions, a local sparse appearance model based on a dictionary of patches sampled from target Thanks to the BNPSI ANR project no ANR-13-BS-03-0006-01, the AR-CIR REPAR project and to the Fondation École Centrale Lille for funding.

templates [START_REF] Liu | Robust tracking using local sparse appearance model and k-selection[END_REF] or learnt from these patches [START_REF] Wang | Transferring visual prior for online object tracking[END_REF] is more appropriate. The principle is to extract patches from a candidate and to compute their sparse encoding in the dictionary. The representation coefficients or sparse codes are then exploited as appearance features. The eventual step, referred to as the pooling step, is to extract meaningful coefficients from these appearance features. The likelihood is based on the similarity between the candidate and the object features vectors.

Several pooling operators have been considered. The average pooling [START_REF] Zhang | Robust visual tracking using feature-based visual attention[END_REF] averages the sparse codes to build up the final feature vector. The max pooling method [START_REF] Wang | Transferring visual prior for online object tracking[END_REF] keeps the maximum absolute value of the sparse code coefficients. Both methods are imprecise because they lose the location of patches and thus the spatial structure of the object. To overcome this loss, an alignment pooling method is developed in [START_REF] Jia | Visual tracking via adaptive structural local sparse appearance model[END_REF]. It preserves the spatial information, but it imposes constraints on the dictionary construction. It is composed of patches extracted from target templates according to a fixed spatial structure that can not change over time.

In this paper we propose to combine the principle of alignment pooling with dictionary learning for sparse representation of the target object patches. Then tracking is performed in a space of reduced dimension by comparing sparse codes of patches in the candidate region with sparse codes of patches extracted from the target template at known locations. The paper is organised as follows. Section 2 recalls related previous works. Section 3 presents the proposed sparse coding model. In Section 4, the tracking algorithm based on particle filtering is described. Section 5 presents performance results obtained on public datasets and Section 6 concludes.

RELATED WORK

We first recall the alignment pooling approach [START_REF] Jia | Visual tracking via adaptive structural local sparse appearance model[END_REF]. The target is described by several templates. For simplicity, we consider only one target template T , typically a rectangle comprising M overlapping square patches of size c 2 . A set of N ≤ M patches is extracted from the template at predefined locations according to a spatial layout. The matrix L p = [p 1 , . . . , p N ] ∈ R c 2 ×N , formed by the concatenation of the vectorised patches (p i ) N i=1 is directly used as the dictionary. Then a candidate region C is modelled as follows. The candidate is first resized to match the target template's size. A set of N patches (q i ) N i=1 is sampled at the same locations as in the target. The sparse codes u i of each of these patches in the dictionary L p of size N are obtained by solving the following

1 -constrained minimisation problem arg min ui q i -L p u i 2 2 s.t. u i 1 ≤ ρ, (1)
where ρ controls the sparsity of the code u i ∈ R N . Each patch q i is then approximated by a sparse combination of the patches (p i ) N i=1 weighted by u i . The alignment pooling of u i consists in selecting the contribution of patch p i at the same location as patch q i which is the i-th coefficient u ii of u i . Consequently, if the u i 's are the columns of the square matrix U ∈ R N ×N , the pooled coefficients are located on the diagonal. The log-likelihood of candidate C with respect to template T is defined as the trace of matrix U

L(C, T ) = Tr U = N i=1 u ii . (2)
For comparison, the max and average pooling operators respectively compute the maximum and average of each u i , before summing the results. The alignment pooling is more accurate because it takes into account the locations of extracted patches. However the major drawback is the lack of flexibility. To increase the number of patches or change their locations for better performance, the dictionary has to be completely redefined. The size of the dictionary is necessarily the number N of extracted patches so that if one wants to take all available patches into account, the size of the dictionary becomes large since N = M . Moreover, as shown on Fig. 2, that method may suffer from a lack of robustness.

PROPOSED APPROACH

To overcome these limitations, we propose to learn a dictionary

D p ∈ R c 2 ×K of fixed size K M from a set of patches L p = [p 1 , . . . , p N ] ∈ R c 2 ×N
extracted from template T to obtain an adapted representation of the data. This is carried out by solving the minimisation problem

arg min Dp,Z L p -D p Z 2 F s.t. z i 1 ≤ ρ, ∀i, (3)
where z i is the i-th column of the matrix Z ∈ R K×N and

• F denotes the Frobenius norm. Dictionary learning is performed on centered patches while average values are processed apart. Consequently, z i is the sparse code of the patch p i with respect to the dictionary D p . The dimension reduction performed by dictionary learning imposes no limit on the number N . We can afford to use all the overlapping patches (N = M ) of size c 2 within the template to learn the dictionary of size K M . Figure 1 illustrates the atoms of the dictionary D p of size K = 161 learnt over all the N = 16109 patches of size 8 × 8 extracted from the target template image in Fig. 1a. To compare, the alignment pooling has to solve the minimisation problem (1) with a dictionary of size 16109 whereas the proposed method uses a dictionary D p that is 100 times smaller. To describe a candidate region, n patches (q i ) i∈J are extracted at locations defined by some set J ⊂ {1, . . . N } and #J = n. We compute their sparse codes

V = [v i ] i∈J ∈ R K×n in D p by solving arg min vi q i -D p v i 2 2 s.t. v i 1 ≤ ρ. (4)
Compared to [START_REF] Jia | Visual tracking via adaptive structural local sparse appearance model[END_REF] where n = N , the choice of the number of patches n and their locations is completely free. To build the log-likelihood of a candidate region C, we compare the sparse representations using D p of these n patches from C and T at the same locations defined by J. This comparison is quantified by matched filtering which provides optimal SNR for pattern detection. Thus, the log-likelihood of a candidate set of n sparse codes V with respect to the template sparse codes Z J = [z i ] i∈J is defined as a cross-correlation:

1 Z J F Tr Z T J V . (5)
This log-likelihood optimally detects the presence of the template patches represented by Z J at known positions. This approach can be interpreted as an alignment pooling strategy since the trace operation pools the individual alignment scores z T i v i of the set of n patches (which all 'vote' for the same target position). Note that the similarity proposed in [START_REF] Jia | Visual tracking via adaptive structural local sparse appearance model[END_REF] can be seen as a special case of [START_REF] Zhong | Robust object tracking via sparsity-based collaborative model[END_REF] where D p = L p (no dictionary learning) and Z J = I (trivial coding). Last remains to take into account the average values of patches denoted by pi and qi : large differences of average gray levels |p i -qi | should be penalised. We propose to add a term -λ|p i -qi | 2 to (5) to finally get the log-likelihood

L J (C, T ) = 1 Z J F Tr Z T J V -λ i∈J |p i -qi | 2 , (6)
where λ > 0 is some weighting parameter (default is 1). Figure 2 compares the proposed approach to the alignment pooling method. A patch q i0 is selected in a resized candidate region of Fig. 2a. Figures 2b and2c show the similarity maps between q i0 and all the patches (p i ) i∈J with J = {1, . . . , M } extracted from T . Without dictionary learning, see Fig. 2b, this similarity map is directly given by the sparse code u i0 of the patch q i0 in L p . With the proposed approach at Fig. 2c, it is given by Z T J v i0 where v i0 is the sparse code of q i0 in D p . The alignment pooling consists in selecting the coefficient of the sparse code corresponding to the contribution of the patch p i0 at the same location as q i0 (red circles in Fig. 2b and2c). With a standard alignment pooling, little matching is found between the patches p i0 and q i0 . In the set of the template patches used as the dictionary, a lot of atoms (patches) are similar and the atoms selected by the sparse decomposition do not necessarily include the aligned patch p i0 . This effect can be reduced by considering templates from different frames. Our approach gives better matching results because the learnt dictionary is of reduced dimension and the template patches (p i ) i∈J are described by several atoms of D p . A match is found every time p i , i ∈ J, shares atoms with q i0 . Figure 2c shows several matches in particular with the aligned patch.

TRACKING ALGORITHM

Object tracking is carried out by particle filtering [START_REF] Isard | Condensationconditional density propagation for visual tracking[END_REF]. Given a sequence of observations y 1:k = (y 1 , . . . , y k ) up to time k, the aim is to estimate the object state x k from the posterior density p(x k |y 1:k ) which is recursively approximated with a set of N p weighted particles {x

(m) k , w (m) k } Np i=1 : p(x k |y 1:k ) ≈ Np i=1 w (m) k • δ(x k -x (m) k ).
The target object is represented by a bounding window. The state vector is defined as k-1 ). As often, we assume that x k evolves as a Gaussian random walk:

x k = [c k , d k ] T where c k = c x k ,
x k |x k-1 ∼ N (x k-1 , Σ)
where Σ is a diagonal covariance matrix which defines the uncertainty region around the previous state. During the second stage, the weights w (m) k are updated according to the recursive expression: w

(m) k = w (m) k-1 •p(y k |x (m)
k ) where the observation likelihood p(y k |x k ) measures the matching between the observation and the state. We define the likelihood directly from expression (6) as

p(y k |x (m) k ) ∝ exp µ • L J (C, T ) , (7)
where C is the candidate region identified by x

(m) k
and µ is a tuning parameter. Finally, after weight normalisation and if necessary, particle resampling, the object state is obtained by MMSE (Minimum Mean Square Error) estimation

x k = E x k |y 1:k = Np m=1 w (m) k x (m) k . (8)

EXPERIMENTAL VALIDATION

In this section, we validate our approach by comparing it to other pooling strategies. The optimisation problems (1), ( and (4) are solved using the Spams Matlab toolbox 1 [START_REF] Mairal | Online learning for matrix factorization and sparse coding[END_REF] with ρ = 0.25. J is set to a fixed grid of step 8. For particle filtering, N p = 600 particles, µ = 4.6 and Σ = diag (20,20,[START_REF] Mei | Robust visual tracking using 1 minimization[END_REF][START_REF] Mei | Robust visual tracking using 1 minimization[END_REF].

Concerning the proposed method, the size of the dictionary is set to K = 64. Four pooling strategies are considered: alignment pooling (without dictionary learning) and maximum, average or alignment pooling (proposed method) with dictionary learning. They are compared in the first 100 frames of the sequences Suv and Woman. For a fair comparison, all the trackers adopt the same dynamical model, only the observation likelihood differs. Figure 3 shows the qualitative tracking results obtained on a few images of the sequences. These sequences present challenging scenarios with partial occlusion and illumination changes. Figure 4 shows the quantitative tracking results. The first row depicts the center location error (in pixels) between the ground truth bounding box and the estimated bounding box. The second row depicts the overlap rate [START_REF] Everingham | The pascal visual object classes (voc) challenge[END_REF] which is the ratio between the area of the intersection of both bounding boxes and the area of the union.

The maximum and average pooling give the worst performance in the first frames of both videos, because they use a similarity between patches regardless of their locations. However this lack of precision is compensated by a good robust- ness, and the performances are maintained or even can improve along the sequences. On the opposite, the alignment pooling is more accurate at the beginning of the sequences, because its takes into account the spatial information and a similarity is found between aligned patches. But the tracking results degrade along the videos. As shown in Figure 2, it can miss the matching between patches that are similar. For example on the Suv sequence, the target partially exits the image around frame 30. When the target comes back, the maximum and average pooling can find it whereas the alignment pooling fails. Along both sequences, the best tracking performance is achieved with our approach. The proposed cross-correlation based similarity is both accurate and robust.

As the maximum and average pooling, our tracker can retrieve the target after a partial exit and as the alignment pooling, it preserves the spatial information. Table 1 gathers results obtained on a set of publicly available video sequences [START_REF] Wu | Online object tracking: A benchmark[END_REF]. It compares success rates R(α) that are the proportions of frames for which the overlap rate is ≥ α. To this aim, we compare the values of R(α = 0.5) and, in the spirit of the usual AUC, the Area Under the Curve {α ∈ (0, 1), R(α)} which is a more general indicator. The proposed method either equals or outperforms other methods.

CONCLUSIONS

In this paper we propose a sparse representation of patches in a learnt dictionary to model the appearance of an object. Then tracking is performed by a matched filter on the sparse codes of the patches extracted from the candidate. This method generalises the alignment pooling method and improves on other pooling strategies with learnt dictionaries such that the max or average pooling. Numerical results show that it compares favourably with previous works.

Fig. 1 :

 1 Fig.1: Atoms of a learnt dictionary by order of contributions in the image.

Fig. 2 :

 2 Fig. 2: (a) A patch q i0 taken from a resized candidate. (b) Reshaped sparse code u i0 . (c) Cross-correlation Z T J v i0

Fig. 3 :

 3 Fig. 3: Qualitative tracking results on the sequences Woman and Suv with different pooling strategies: proposed in red, maximum pooling in green, average pooling in blue and alignment pooling in black.

  c y k is the position of the top left corner and d k = d x k , d y k is the size of the window. To obtain the set of particles at time k from the previous particles {x Np i=1 , the particle filter algorithm includes two major steps: prediction and update. During prediction, the samples x (m) k are propagated according to the dynamic model using the prior density p(x

Fig. 4 :

 4 Fig. 4: Quantitative tracking results on the sequences Woman and Suv

Table 1 :

 1 Success rate R(α = 0.5) and Area Under the Curve (AUC) R(α)dα for the proposed method, max pooling and alignment pooling.

	1 http://spams-devel.gforge.inria.fr/


Pierre Bourhis
email: pierre.bourhis@inria.frmarkus.kroetzsch

Markus Krötzsch

Sebastian Rudolph
email: sebastian.rudolph@tu-dresden.de

Reasonable Highly Expressive Query Languages

Expressive query languages are gaining relevance in knowledge representation (KR), and new reasoning problems come to the fore. Especially query containment is interesting in this context. The problem is known to be decidable for many expressive query languages, but exact complexities are often missing. We introduce a new query language, guarded queries (GQ), which generalizes most known languages where query containment is decidable. GQs can be nested (more expressive), or restricted to linear recursion (less expressive). Our comprehensive analysis of the computational properties and expressiveness of (linear/nested) GQs also yields insights on many previous languages.

Introduction

The significance of query languages in KR is twofold. On the one hand, evaluating queries in the presence of a background ontology allows us to express more complex information needs, leading to the notion of ontology-based query answering. This topic has been studied for a wide range of ontology languages and many different query languages, including conjunctive queries [Calvanese et al., 2007b;[START_REF] Eiter | [END_REF] and (many variants of) regular path queries [Calvanese et al., 2007a;2009;[START_REF] Bienvenu | [END_REF]. On the other hand, recursive queries can be used to "implement" reasoning, such that the query plays the role of a logical calculus that computes subsumptions [START_REF][END_REF]Krötzsch, 2011;[START_REF] Bischoff | [END_REF].

In both application areas, we can see a tendency towards more and more powerful recursive queries. Recent works introduced several highly expressive query languages related to applications in KR: Monadically Defined Queries (MQs) [START_REF] Rudolph | Flag & check: Data access with monadically defined queries[END_REF] and Monadic Disjunctive SNP queries (coMMSNP) [START_REF] Bienvenu | [END_REF]. Both can be viewed as fragments of (disjunctive) Datalog.

The proliferation of query languages and their uses in KR raises new questions. The complexity of ontology-based query answering has been studied from its inception, whereas the equally important question of relative expressiveness was studied only recently [START_REF] Bienvenu | [END_REF]. Another important question is the problem of query containment, where we Figure 1: Query languages and complexities; languages higher up in the graph are more expressive consider two queries Q 1 and Q 2 , and ask if every answer to Q 1 is also an answer to Q 2 over all possible inputs. Deciding query containment is relevant for query rewriting algorithms, where it needs to be checked if new queries are contained in previous ones to ensure termination. Further relevant applications are query optimization (finding a simpler yet equivalent query), and verification (checking that a query contains specific test cases). In addition, query containment has a range of applications in databases, e.g., in information integration and database integrity checking.

Although Datalog provides a useful framework for studying many recursive query languages, it does, unfortunately, not have a decidable query containment problem [Shmueli, 1987]. In contrast, the containment is known to be decidable for regular path queries, MQs, and coMMSNP queries. In the latter two cases, however, no upper complexity bound is known. Nevertheless, numerous results exist for various smaller query languages. For the following overview, recall that a predicate in a Datalog program is intensional (IDB) if it occurs in some rule head, and extentional (EDB) otherwise.

Non-recursive Datalog and unions of conjunctive queries

A non-recursive Datalog program is equivalent to a (possibly exponential) union of conjunctive queries (UCQ), and thus expressible in first-order logic. Containment of Dat-alog (Dlog) in UCQ is 2ExpTime-complete, while containment of Dlog by non-recursive Datalog is 3ExpTime-complete [START_REF] Chaudhuri | [END_REF]. Some restrictions for decreasing these complexities have been considered. Deciding if a linear Datalog program (LinDlog, where rule bodies contain at most one recursive predicate) is contained in a UCQ is ExpSpace-complete; complexity further decreases to PSpace when the linear Datalog program is monadic (LinMDlog, see below) [START_REF] Chaudhuri | [END_REF][START_REF] Chaudhuri | [END_REF]. Monadic Datalog A monadic Datalog (MDlog) program is one with only unary IDB predicates. Containment between two MDlog programs is 2ExpTime-complete. The upper bound is well known since the 80's [Cosmadakis et al., 1988], while the lower bound has been established only recently [Benedikt et al., 2012]. Moreover, the containment of Dlog in MDlog is also decidable by a straightforward application of [Courcelle, 1991, Theorem 5.5]. 1 So far, however, tight bounds have not been known for this case. Guarded Datalog Guarded Datalog (GDlog) requires that, for each rule, the variables of the head should appear in a single EDB atom in the rule body. Such (frontier-)guarded rules have been known for a while [START_REF] Calì | [END_REF][START_REF] Baget | [END_REF], but their first use as a query language is recent [START_REF] Bárány | [END_REF]. GDlog is a proper extension of MDlog, since monadic rules can be rewritten into guarded rules [START_REF] Bárány | [END_REF]. Query containment for GDlog is 2ExpTimecomplete, as it corresponds to a satisfiability problem for guarded negation fixed point logic [Bárány et al., 2011]. Navigational Queries Conjunctive two-way regular path queries (C2RPQs) generalize conjunctive queries (CQs) by regular expressions over binary predicates [START_REF] Florescu | [END_REF][START_REF] Calvanese | [END_REF]. Variants of this idea are used in the RDF query language SPARQL 1.1 and the XML query language XPath. Roughly, C2RPQ is a conjunction of atoms of the form xLy where L is a two-way regular expression. A pair of nodes n 1 , n 2 is a valuation of the pair x, y if and only if there exists a path between n 1 and n 2 matching L. Containment of such queries is ExpSpace-complete [START_REF] Florescu | [END_REF][START_REF] Calvanese | [END_REF]Abiteboul and Vianu, 1999;[START_REF] Deutsch | Alin Deutsch and Val Tannen. Optimization properties for classes of conjunctive regular path queries[END_REF], while containment of Dlog in C2RPQ is 2ExpTime-complete [Calvanese et al., 2005]. Fragments of Monadic Second-Order Logic More recently, Monadically Defined Queries (MQs) and their nested version (MQ + s) have been introduced as a proper generalization of MDlog that also captures (unions of) C2RPQs [Rudolph and [START_REF] Rudolph | Flag & check: Data access with monadically defined queries[END_REF]. MQs are expressible in both Dlog and monadic second-order logic, but (in contrast to these languages) feature a decidable query containment problem. The most general recent query language for which containment is known to be decidable is coMMSNP [START_REF] Bienvenu | [END_REF], a fragment of monadic second-order logic motivated by descriptive complexity. As opposed to the above languages, coMMSNP is a non-deterministic query language, closely related to disjunctive Datalog. A simple inspection of the definitions shows that the deterministic (disjunction-free) fragment, i.e., "Horn-coMMSNP", agrees with MQ.

1 We thank Michael Benedikt for this observation.

In this paper, we further extend the known recursive query languages and at the same time settle all major questions related to the complexity of their query containment problems. Figure 1 gives an overview of all languages we consider, together with their respective query-answering complexities.

The main new query language we consider is called guarded queries (GQ), and is based on the use of frontierguarded Datalog rules. GQ can be viewed as an extension of MQ, and is indeed inspired by a similar extension for coMMSNP [START_REF] Bienvenu | [END_REF]. GQ thus also generalizes frontier-guarded Datalog. We further introduce the nested and linear variant of GQ, and establish complexity results for query answering in all cases.

We then turn towards query containment. We obtain tight complexity bounds for (nested) GQs and many other query languages, which are summarized in Table 1. To show the upper bounds, we extend known automata-based approaches by a number of new techniques. Lower bounds are obtained by simulating space-bounded alternating Turing machines in a way that allows for an exponential increase in space with each nesting level. Finally, we also sketch how our results transfer to the case of linear Datalog, where many complexities can be slightly reduced.

In summary, our results settle open problems for (nested) MQs, painting a comprehensive and detailed picture of the state of the art in Datalog query containment. Full proofs can be found in an accompanying report [START_REF] Bourhis | [END_REF].

Preliminaries

We consider a standard language of first-order predicate logic, based on an infinite set C of constant symbols, an infinite set P of predicate symbols, and an infinite set V of firstorder variables. Each predicate p ∈ P is associated with a natural number ar(p) called the arity of p. The list of predicates and constants forms the language's signature S = P, C . We generally assume S = P, C to be fixed, and only refer to it explicitly if needed.

Formulae, Rules, and Queries A term is a variable x ∈ V or a constant c ∈ C. We use symbols s, t to denote terms, x, y, z, v, w to denote variables, a, b, c to denote constants. Expressions like t, x, c denote finite lists of such entities. We use the standard predicate logic definitions of atom and formula, using symbols ϕ, ψ for the latter.

Datalog queries are defined over an extended signature with additional predicate symbols, called IDB predicates; all other predicates are called EDB predicates. A Datalog rule is a formula of the form ∀x, y.ϕ[x, y] → ψ[x] where ϕ and ψ are conjunctions of atoms, called the body and head of the rule, respectively, and where ψ only contains IDB predicates. We usually omit universal quantifiers when writing rules. Sets of Datalog rules are denoted P, R, S. A set of Datalog rules is:

• monadic if all IDB predicates are of arity one;

• frontier-guarded if the body of every rule contains an atom p(t) such that p is an EDB predicate and t contains all variables that occur in the rule's head;

• linear if each rule body has at most one IDB predicate.

A conjunctive query (CQ) is a formula Q[x] = ∃y.ψ[x, y] where ψ[x, y] is a conjunction of atoms; a union of conjunctive queries (UCQ) is a disjunction of such formulae. A Datalog query P, Q consists of a set of Datalog rules P and a conjunctive query Q over IDB or EDB predicates (Q could be expressed as a rule in Datalog, but not in all restrictions of Datalog we consider). We write Dlog for the language of Datalog queries. A monadic Datalog query is one where P is monadic, and similarly for other restrictions. We use the query languages MDlog (monadic), GDlog (frontier-guarded), LinDlog (linear), and LinMDlog (linear, monadic). Databases and Semantics We use the standard semantics of first-order logic (FOL). A database instance I over a signature S = P, C consists of a set ∆ I called domain and a function • I that maps constants c ∈ C to domain elements c I ∈ ∆ I and predicate symbols p ∈ P to relations p I ⊆ (∆ I ) ar (p) , where p I is the extension of p.

Given a database instance I and a formula ϕ[x] with free variables x = x 1 , . . . , x m , the extension of ϕ[x] is the subset of (∆ I ) m containing all those tuples δ 1 , . . . , δ m for which

I, {x i → δ i | 1 ≤ i ≤ m} | = ϕ[x].
We denote this by δ 1 , . . . , δ m ∈ ϕ I or by I | = ϕ(δ 1 , . . . , δ m ); a similar notation is used for all other types of query languages. Two formulae ϕ[x] and ψ[x] are called equivalent if their extensions coincide for every database instance I.

The set of answers of a UCQ Q[x] over I is its extension. A Datalog program P is satisfied by database instance I over the extended signature of EDB and IDB predicates, if all rules of P are satisfied by I in the usual sense. The set of answers of a Datalog query P, Q over I is the intersection of the extensions of Q over all extended database instances I that satisfy P and agree with I on constants and EDB predicates. Datalog can also be defined as the least fixpoint of the inflationary evaluation of Q on I [Abiteboul et al., 1994].

We do not require database instances to have a finite domain, since all of our results are valid in either case. This is due to the fact that every entailment of a Datalog program has a finite witness, and that all of our query languages are positive, i.e., that their answers are preserved under homomorphisms of database instances.

An important reasoning task on queries is to determine if a query contains another. In particular, a Datalog query P, Q is contained in a Datalog query P , Q , denoted P, Q P , Q , iff for each database instance I over the signature of EDB predicates and constants, the set of answers of P, Q over I is included in the set of answers of P , Q over I.

Guarded Queries

Rudolph and [START_REF] Rudolph | Flag & check: Data access with monadically defined queries[END_REF] introduced monadically defined queries (MQs 2 ) as a generalization of conjunctive twoway regular path queries (C2RPQs) and monadic Datalog (MDlog) for which query containment is still decidable. The idea underlying this approach is that candidate query answers are checked by evaluating a monadic Datalog program, i.e., in contrast to the usual evaluation of Datalog queries, we start with a "guessed" answer that is the input to a Datalog program. To implement this, the candidate answer is represented 2 Here we shorten the original acronym MODEQ to MQ.

by special constants λ that the Datalog program can refer to. This mechanism was called flag & check, since the special constants act as flags to indicate the answer to be checked.

Example 1. A query that computes the transitive closure over a relation p can be defined as follows.

p(λ 1 , y) → U(y) U(y) ∧ p(y, z) → U(z) U(λ 2 ) → hit
One defines the answer of the query to contain all pairs δ 1 , δ 2 for which the rules entail hit when interpreting λ 1 as δ 1 and λ 2 as δ 2 .

The original approach used monadic Datalog for its close relationship to monadic second-order logic, which was the basis for showing decidability of query containment. In this work, however, we develop new techniques for showing the decidability (and exact complexity) of this problem directly. It is therefore suggestive to consider other types of Datalog programs for the "check" part. The next definition introduces the general approach for arbitrary Datalog programs, and defines interesting fragments by imposing further restrictions.

Definition 1. Consider a signature S . An FCP ("flag & check program") of arity m is a set of Datalog rules P with k ≥ 0 IDB predicates U 1 , . . . , U k that may use the additional constant symbols λ 1 , . . . , λ m S and an additional nullary predicate symbol hit. An FCQ ("flag & check query") P is of the form ∃y.P(z), where P is an FCP of arity |z| and all variables in y occur in z. The variables x that occur in z but not in y are the free variables of P.

Let I be a database instance over S . The extension P I of P is the set of all tuples δ 1 , . . . , δ m ∈ (∆ I ) m such that every database instance I that extends I to the signature of P and that satisfies λ I 1 , . . . , λ I m = δ 1 , . . . , δ m also entails hit. The semantics of FCQs is defined in the obvious way based on the extension of FCPs.

A GQ is an FCQ ∃y.P(z) such that P is frontier-guarded. Similarly, we define MQ (monadic), LinMQ (linear, monadic), and LinGQ (linear, frontier-guarded) queries.

In contrast to Rudolph and [START_REF] Rudolph | Flag & check: Data access with monadically defined queries[END_REF], we do not define monadic queries as conjunctive queries of FCPs, but we merely allow existential quantification to project some of the FCP variables. Proposition 1 below shows that this does not reduce expressiveness.

We generally consider monadic Datalog as a special case of frontier-guarded Datalog. Monadic Datalog rules do not have to be frontier-guarded. A direct way to obtain a suitable guard is to assume that there is a unary domain predicate that contains all (relevant) elements of the domain of the database instance. However, it already suffices to require safety of Datalog rules, i.e., that the variable in the head of a rule must also occur in the body. Then every element that is inferred to belong to an IDB relation must also occur in some EDB relation. We can therefore add single EDB guard atoms to each rule in all possible ways without modifying the semantics. This is a polynomial operation, since all variables in the guards are fresh, other than the single head variable that we want to guard. We therefore find, in particular, that GQ captures the expressiveness of MQ. The converse is not true, as the following example illustrates. Example 2. The following 4-ary LinGQ generalizes Example 1 by checking for the existence of two parallel p-chains of arbitrary length, where each pair of elements along the chains is connected by a relation q, like the steps of a ladder. q(λ 1 , λ 2 ) → U q (λ 1 , λ 2 ) U q (x, y) ∧ p(x, x ) ∧ p(y, y ), q(x , y ) → U q (x , y ) U q (λ 3 , λ 4 ) → hit One might assume that the following MQ is equivalent:

q(λ 1 , λ 2 ) → U 1 (λ 1 ) q(λ 1 , λ 2 ) → U 2 (λ 2 ) U 1 (x) ∧ U 2 (y) ∧ p(x, x ) ∧ p(y, y ), q(x , y ) → U 1 (x ) U 1 (x) ∧ U 2 (y) ∧ p(x, x ) ∧ p(y, y ), q(x , y ) → U 2 (y )
U 1 (λ 3 ) ∧ U 2 (λ 4 ) → hit However, the latter query also matches structures that are not ladders. For example, the following database yields the answer a, b, c, d , although there is no corresponding ladder structure: {q(a, b), p(a, c), p(b, e), q(c, e), p(a, e ), p(b, d), q(e , d)}. One can extend the MQ to avoid this case, but any such fix is "local" in the sense that a sufficiently large ladderlike structure can trick the query.

Rudolph and [START_REF] Rudolph | Flag & check: Data access with monadically defined queries[END_REF] showed that monadically defined queries can be expressed both in Datalog and in monadic second-order logic. While we lose the connection to monadic second-order logic with GQs, the expressibility in Datalog remains. The encoding is based on the intuition that the choice of the candidate answers for λ "contextualizes" the inferences of the Datalog program. To express this without special constants, we can store this context information in predicates of suitably increased arity. Example 3. The 4-ary LinGQ of Example 2 can be expressed with the following Datalog query. For brevity, let y be the variable list y 1 , y 2 , y 3 , y 4 , which provides the context for the IDB facts we derive. q(y 1 , y 2 ) → U + q (y 1 , y 2 , y) U q (x, y, y) ∧ p(x, x ) ∧ p(y, y ), q(x , y ) → U + q (x , y , y) U q (y 3 , y 4 , y) → goal(y) This result is obtained by a straightforward extension of the translation algorithm for MQs [Rudolph and [START_REF] Rudolph | Flag & check: Data access with monadically defined queries[END_REF], which may not produce the most concise representation. Also note that the first rule in this program is not safe, since y 3 and y 4 occur in the head but not in the body. According to the semantics we defined, such variables can be bound to any element in the active domain of the given database instance (i.e., they behave as if bound by a unary domain predicate).

This observation justifies that we consider MQs, GQs, etc. as Datalog fragments. It is worth noting that the translation does not change the number of IDB predicates in the body of rules, and thus preserves linearity. The relation to (linear) Datalog also yields some complexity results for query answering; we will discuss these at the end of the next section, after introducing nested variants our query languages.

Nested Queries

Every query language gives rise to a nested language, where we allow the use of nested queries as if they were predicates. Sometimes, this does not lead to a new query language (like for CQ and Dlog), but often it affects complexities and/or expressiveness. It has been shown that both are increased when moving from MQs to their nested variants [Rudolph and [START_REF] Rudolph | Flag & check: Data access with monadically defined queries[END_REF]]. We will see that nesting also has strong effects on the complexity of query containment. Definition 2. We define k-nested FCPs inductively. A 1nested FCP is an FCP. A k+1-nested FCP is an FCP that may use k-nested FCPs of arity m instead of predicate symbols of arity m in rule bodies. The semantics of nested FCPs is immediate based on the extension of FCPs. A k-nested FCQ P is of the form ∃y.P(z), where P is a k-nested FCP of arity |z| and all variables in y occur in z.

A k-nested GQ query is a k-nested frontier-guarded FCQ. For the definition of frontier-guarded, we still require EDB predicates in guards: subqueries cannot be guards. The language of k-nested GQ queries is denoted GQ k ; the language of arbitrarily nested GQ queries is denoted GQ + .

Similarly, we define languages MQ k and MQ + (monadic), LinMQ k and LinMQ + (linear, monadic), and LinGQ k and LinGQ + (linear, frontier-guarded).

Note that nested queries can use the same additional symbols (predicates and constants); this does not lead to any semantic interactions, however, as the interpretation of the special symbols is "private" to each query. To simplify notation, we assume that distinct (sub)queries always contain distinct special symbols. The relationships of the query languages we introduced here are summarized in Figure 1, where upwards links denote increased expressiveness. An interesting observation that is represented in this figure is that linear Datalog is closed under nesting: Theorem 3. LinDlog = LinDlog + .

Another kind of nesting that does not add expressiveness is the nesting of FCQs in UCQs. Indeed, it turns out that (nested) FCQs can internalize arbitrary conjunctions and disjunctions of FCQs (of the same nesting level). This even holds when restricting to linear rules. Proposition 1. Let P be a positive query, i.e., a Boolean expression of disjunctions and conjunctions, of LinMQ k queries with k ≥ 1. Then there is a LinMQ k query P of size polynomial in P that is equivalent to P. Analogous results hold when replacing LinMQ k by MQ k , GQ k , or LinMQ k queries.

Query answering for MQs has been shown to be NPcomplete (combined complexity) and P-complete (data complexity). For MQ + , the combined complexity increases to PSpace while the data complexity remains the same. These results can be extended to GQs. We also note the complexity for frontier-guarded Datalog, for which we are not aware of any published result. Theorem 4. The combined complexity of evaluating GQ queries over a database instance is NP-complete. The same holds for GDlog queries. The combined complexity of evaluating GQ + queries is PSpace-complete. The data complexity is P-complete for GDlog, GQ, and GQ + .

The lower bounds in the previous case follow from know results for MQs. Particularly, the hardness proof for nested MQs also shows that queries of a fixed nesting level can encode the validity problem for quantified boolean formulae with a certain number of quantifier alternations; this explains why we show the combined complexity of MQ k to be in the Polynomial Hierarchy in Figure 1. A modification of this hardness proof of Rudolph and [START_REF] Rudolph | Flag & check: Data access with monadically defined queries[END_REF] yields the same results for the combined complexities in the linear cases; matching upper bounds follow from Theorem 4. Theorem 5. The combined complexity of evaluating LinMQ, LinGDlog, or LinGQ queries over a database instance is NPcomplete. The combined complexity of evaluating LinMQ + or LinGQ + queries is PSpace-complete. The data complexity is NLogSpace-complete for all of these query languages.

Complexity of Query Containment

In this section, we first discuss an automata-based way to decide query containment, yielding upper complexity bounds.

We first recall a general technique of reducing query containment to the containment problem for (tree) automata [START_REF] Chaudhuri | [END_REF]. In spite of several extensions we need for λ-terms and nesting, our proofs still follow the same basic approach. An introduction to tree automata is included in the report [START_REF] Bourhis | [END_REF].

A common way to describe the answers of a Dlog query P = P, p is to consider its expansion trees. Intuitively speaking, the goal atom p(x) can be rewritten by applying rules of P in a backward-chaining manner until all IDB predicates have been eliminated, resulting in a CQ. The answers of P coincide with the (infinite) union of answers to the CQs obtained in this fashion. The rewriting itself gives rise to a tree structure, where each node is labeled by the instance of the rule that was used in the rewriting, and the leaves are instances of rules that contain only EDB predicates in their body. The set of all expansion trees provides a regular description of P that we exploit to decide containment.

To formalize this approach, we describe the set of all expansion trees as a tree language, i.e., as a set of trees with node labels from a finite alphabet. The number of possible labels of nodes in expansion trees is unbounded, since rules are instantiated using fresh variables. To obtain a finite alphabet of labels, one limits the number of variables and thus the overall number of possible rule instantiations [START_REF] Chaudhuri | [END_REF]. The set of proof trees obtained in this way is a regular tree language that can be described by an automaton A P . In order to use A P to decide containment of P by another query P , we construct an automaton A P P that accepts all proof trees of P that are "matched" by P . Indeed, every proof tree induces a witness, i.e., a minimal matching database instance, and one can check whether or not P can produce the same query answer on this instance. If this is the case for all proof trees of P, then containment is shown.

Our first result provides the upper bound for deciding containment of GQ queries. In fact, the result extends to arbitrary Dlog queries on the left-hand side. Theorem 6. Containment of Dlog queries in GQ queries can be decided in 3ExpTime.

The proof of this result requires a number of new techniques on top of the established methods. We are looking for an automaton A P P that accepts proof trees of P where the underlying witness is also accepted by P . As a first step, we construct an automaton A P,ρ that verifies that a single rule ρ of P can be applied in a specific way to derive one specific conclusion. Since proof trees reuse variables to obtain a finite alphabet, the conclusion of the rule is an atom p(v) referring to variables v that are ambiguous if we do not know exactly which place in the tree we are referring to. Therefore the input of A P,ρ is a proof tree of P with two kinds of additional information added to the labels: (a) the interpretation of the λ constants that is used, and (b) the expected conclusion of the rule. A P,ρ is a top-down tree automaton of exponential size.

We want to combine many automata of the form A P,ρ to verify complete derivations of P rather than single rule applications. In this case, we cannot add information about the expected conclusion p(v) to the tree, since there are unboundedly many conclusions during one run. Instead, we encode the conclusion by considering auomtata A + P,ρ,v that can start their run not just from the root, but from some node within the tree where all variables v occur with the same meaning as in the conclusion p(v) (this is a single node due to guardedness). Starting in the middle of the tree makes it necessary to consider both nodes below and above the current position, and A + P,ρ,v thus needs to be an alternating 2-way tree automaton.

An automaton A + P P that verifies a complete derivation of P on a proof tree of P is obtained by "concatenating" automata of the form A + P,ρ,v . A + P P is an alternating 2-way automaton that is exponential in size. The trees accepted by A + P P still need to contain information about the interpretation of λ-constants. Using a well-known construction, we obtain an exponentially larger (1-way) top-down tree automaton A P P that accepts the same trees. This automaton of double exponential size can finally be changed into the automaton A P P that does not require λ-annotations-a polynomial transformation. We finish with a doubly-exponential automaton A P P . Checking containment in A P is an exponential process, leading to the claimed 3ExpTime result.

We can modify this proof to obtain another interesting result for the case of frontier-guarded Datalog. If P is a GDlog query, which does not use any special constants λ, we can directly construct a complement tree automaton ĀP P that is only doubly exponential [Cosmadakis et al., 1988, Theorem A.1]. Containment can then be checked by checking the non-emptiness of A P ∩ ĀP P , which is possible in polynomial time, leading to a 2ExpTime algorithm. Theorem 7. Containment of Dlog queries in GDlog queries can be decided in 2ExpTime.

This generalizes an earlier result of Cosmadakis et al. [1988] for monadic Datalog, using another, direct proof.

To lift our results to nested queries, we further extend the ideas developed in the non-nested case. Nested queries are similar to IDB predicates whose validity we need to check using automata. To do this, we first construct alternating two-way tree automata A + P,Q,θ that verify a match of query Q on a tree that is annotated with the expected values of the λ-constants. To remove the need for this annotation when ver- ifying subqueries as part of a longer run, we can again transform A + P,Q,θ into a tree automaton (exponential), and project away the λ-annotations (polynomial). The resulting automaton A P,Q is analogous to the above tree automaton A P,ρ . The rest of the proof uses similar constructions as before. The exponential transformation from A + P,Q,θ to A P,Q is the reason for the exponential complexity increase in each nesting level. Theorem 8. Containment of Dlog queries in GQ k queries can be decided in (k + 2)ExpTime.

To obtain matching lower bounds, we provide direct encodings of Alternating Turing Machines (ATMs) with a fixed space bound. In the context of query containment, this is done by defining a pair of queries P 1 and P 2 such that P 1 matches all structures that encode a sequence (or tree) of (unrelated) Turing machine configurations, while P 2 matches all such structures that do not correctly encode a run of the given TM (i.e., P 2 detects encoding errors). Then any structure that is matched by P 1 but not by P 2 encodes a terminating ATM run, such that the ATM halts iff P 1 is not contained in P 2 .

To obtain hardness results for arbitrary towers of exponential functions, all of our constructions use existing queries to construct larger queries. For example, a query SameCell[x, y] is defined to match the cells in neighboring configurations that are located at the same position of the ATM tape. This query becomes more and more complex (and more and more nested) as we go to exponentially larger tapes, but the construction of the queries needed for the next level always follows the same pattern. In spite of this efficient presentation, the complete ATM encoding requires significant space, and we must refer to the technical report for the details. Theorem 9. Deciding containment of MDlog queries in MQ k queries is hard for (k + 2)ExpTime.

Note that the statement includes the 3ExpTime-hardness for containment of MQs as a special case.

A range of further results can be obtained by considering linear Datalog instead of Datalog in the role of the contained query. This tends to reduce complexity since one can focus on linear derivations, which can be described by word automata instead of tree automata. Accordingly, many ExpTime problems are reduced to PSpace, and all previous complexities for (k + 2)ExpTime translate into results for (k + 1)ExpSpace accordingly. Our ATM constructions are replaced by regular TM constructions, and we obtain tight bounds in most cases. The only exception is containment of LinMQ in LinMQ k , where our lower bounds are one exponential below the upper bounds. The exact complexity remains open.

Conclusions

We have studied the most expressive fragments of Datalog for which query containment is known to be decidable, and we provided exact complexities for query answering and containment in most cases. Our results are summarized in Table 1. While containment tends to be nonelementary for nested queries, we have identified tight exponential complexity hierarchies depending on nesting depth. Our results settle several open problems for known query languages: the complexity of query containment for MQ and MQ + , the complexity of query containment of Dlog in GDlog, and the expressivity of nested LinDlog.

Moreover, we have introduced new query languages based on frontier-guarded Datalog, showing that most complexities are unaffected by this extension.

A few small questions remain open. First, our results are not tight for linear MQs. This case is closely related to conjunctive regular path queries, and inspiration might be drawn from recent results in this field [Reutter, 2013]. Another question is about the role of constants, which we use heavily in some of our hardness proofs. For the case of (linear) monadic Datalog without constants, we conjecture that containment complexities are reduced by one exponential each.

Promising directions for future research include the study of practical containment algorithms, since our automatabased techniques do not lend themselves to implementation yet. Another interesting topic is the search for suitable queries that contain a given query. A special case of this is the boundedness problem, where we try to find a UCQ that contains a given Datalog program. This can be addressed by similar automata-based constructions [Cosmadakis et al., 1988]. Besides boundedness, one can also ask more general questions of rewritability, e.g., whether some Datalog program can be expressed in monadic Datalog or in a regular path query.

Table 1 :

 1 [START_REF] Bourhis | [END_REF]] [Bourhis et al., 2015] [Abiteboul et al., 1994] [Bourhis et al., 2015] [[START_REF] Bourhis | [END_REF]] LinGQ + ,[START_REF] Bourhis | [END_REF] [[START_REF] Bourhis | [END_REF]] [Bourhis et al., 2015] [Bourhis et al., 2015] [Abiteboul et al., 1994] Summary of the known complexities of query containment for several Datalog fragments; sources for each claim are shown in square brackets, using \ to separate sources for lower and upper complexity bounds, respectively

		UCQ,LinMDlog, MDlog,	LinMQ k ,	MQ k ,	LinMQ + ,MQ + ,
		LinGDlog, GDlog	LinGQ k	GQ k	LinGQ + ,GQ +	Dlog
	LinMQ	PSpace-h	kExpSpace-h
		[Chaudhuri and Vardi, 1994]	[Bourhis et al., 2015]	(k + 1)ExpSpace-c	Nonelementary	Undecidable
	ExpSpace [LinGDlog, (k + 1)ExpSpace
	LinMQ n (n ≥ 2), LinMQ + , LinGQ n , LinDlog	ExpSpace-c	(k + 1)ExpSpace-c	(k + 1)ExpSpace-c	Nonelementary	Undecidable
	MDlog, GDlog,	2ExpTime-c
	MQ n , GQ n , MQ + , GQ + ,	[Benedikt et al., 2012], [Chaudhuri and Vardi, 1997]\	(k + 2)ExpTime-c [Th.9]\[Th.8]	(k + 2)ExpTime-c [Th.9]\[Th.8]	Nonelementary [Th.9]	Undecidable [Shmueli, 1987]
	Dlog	[Cosmadakis et al., 1988], [Th.7]

Acknowledgements Pierre Bourhis was partially supported by the INRIA North European associate team Integrating Linked Data. Markus Krötzsch was supported by the DFG in Emmy Noether grant "DIAMOND" (KR 4381/1-1).


François Gillet

published or not. The documents may come

Phytobase: a tool for the integrated synusial approach of vegetation classification at regional to national scale

Phytosociological and ecological diagnostic tools

A comprehensive diagnostic of synusial plot records is implemented in Phytobase, including:

• Synsystematic diagnosis: assignment to a class, an order and an alliance based on the relative number or cover of characteristic and differential species according to Julve's baseveg classification system (8, 9) ; • Syntaxonomic diagnosis: assignment to an elementary syntaxon stored in the database, based on the combination of various indices (10) ; • Ecological diagnosis: ecological indicator values (according to Landolt (11) , Ellenberg or Julve), life forms, CSR strategies, taxonomic diversity indices, pastoral value, etc.

Each elementary syntaxon or coenotaxon is described by the centroid of all plot records that were assigned to it. This centroid relevé includes fidelity indices (e.g., Phi (12) , IndVal (13) ) for species or elementary syntaxa, used in phytosociological diagnoses. An assessment of compositional homogeneity, taking or not into account dominance, is also implemented.

Integrated Synusial Phytosociology

Integrated Synusial Phytosociology (ISP) considers vegetation as organized in nested hierarchical levels, each of them being potentially described in a classification system [START_REF] Barkman | Synusial approaches to classification[END_REF][START_REF] Gillet | La phytosociologie synusiale intégrée : objets et concepts[END_REF][START_REF] Gillet | Integrated synusial phytosociology: some notes on a new, multiscalar approach to vegetation analysis[END_REF] .

The first, finest, level is the synusia, a concrete plant community composed of plant species co-occurring in a local similar environment, with comparable size and habitat use.

Phytobase distinguishes three categories of synusiae, i.e. tree, shrub, herb and moss synusiae, classified into elementary syntaxa.

Synusiae are integrated into phytocoenoses, the second level of vegetation description, based on a list of synusial elementary syntaxa co-occurring in a given phytocoenosis.

Phytocoenoses are classified into elementary coenotaxa according to their synusial composition (elementary syntaxa or alliances).

Phytobase: a tool for the integrated synusial approach of vegetation classification at regional to national scale [START_REF] Barkman | Synusial approaches to classification[END_REF] UMR 6249 Chrono-environnement, Université de Bourgogne Franche-Comté -CNRS, Besançon, France, francois.gillet@univ-fcomte.fr

Phytobase: a relational database for ISP

Phytobase is a relational database management system (RDBMS) devoted to the management of vegetation survey data, following the concepts of the ISP. This application has been developed in the 4D environment (4) from the 1990s at the University of Neuchâtel, at EPFL and now at the University of Besançon.

Phytobase is freely available from the Tela-botanica website (5) , including a sample of relevés and a user guide (6) . It is used by more than 200 registered users in Europe and registered in the GIVD metadatabase (7) .

The current standalone application (version 8.3 for Windows or Mac OS X, built with 4D v13) has a user interface in French language but an English version is planned to allow a broader diffusion to the international community of vegetation scientists.

Main applications

Phytobase has been applied to various ecosystems (wood-pastures, forests, floodplains, wetlands and grasslands) in many regions, mostly in Switzerland and in France. ISP and Phytobase have proved particularly useful when studying structurally and dynamically complex vegetation, such as wooded pastures and alluvial forests, which are poorly described by the Braun-Blanquet approach.

Ecological diagnosis Phytosociological diagnosis

Synusial plot record

( 8 )

 8 Julve P. 1993. Synopsis phytosociologique de la France (communautés de plantes vasculaires). Lejeunia N.S. 140: 1-160. (9) Julve P. 1998-2015. Baseveg -Répertoire synonymique des unités phytosociologiques de France. Available online: http://perso.wanadoo.fr/philippe.julve/catminat.htm (10) Tichý L. 2005. New similarity indices for the assignment of relevés to the vegetation units of an existing phytosociological classification. Plant Ecology 179: 67-72. (11) Landolt E. et al. 2010. Flora indicativa -Ecological indicator values and biological attributes of the flora of Switzerland and the Alps. Haupt, Bern. (12) Chytrý M., Tichý L., Holt J. & Botta-Dukát Z. 2002. Determination of diagnostic species with statistical fidelity measures. Journal of Vegetation Science 13: 79-90. (13) Dufrêne M. & Legendre P. 1997. Species assemblages and indicator species: the need for a flexible asymmetrical approach. Ecological Monographs 67: 345-366.