Nikolaos Vlassopoulos

Nazim Fatès

How Fast can Virtual Amoebae Aggregate? Analysis for the Optimal Firing Rate in an Instance of the Reaction-Diffusion-Chemotaxis Aggregation Scheme

Decentralised gathering is a challenging problem in systems involving numerous identical agents. In our current work we analyse the dynamics of a gathering model that is based on virtual amoebae that fire reactiondiffusion waves with a given probability. Interestingly, it has been shown that there exists a tuning of this probability that minimises the aggregation time. Our study is aimed at experimentally measuring this optimal value and analysing how it is related to the dynamics of the model.

Introduction

The reaction-diffusion-chemotaxis aggregation scheme was introduced as a solution to the decentralised gathering problem. Informally, this problem considers the case where identical agents are randomly initially distributed on a lattice and have to group to form a compact cluster. Each agent is not aware of its position, neither aware of the presence or positions of the other agents. Assume that there is no direct communication among the agents, and they can only interact with each other by exchanging messages that are transferred by the environment. Further, each agent interacts with the environment by either initiating the transmission of a message, that we call firing, or by reacting to the presence of a message in its neighbourhood by means of chemotaxis.

This aggregation scheme draws its inspiration from the species Dictyostelium discoideum. This particular species of amoebae has a very diverse life-cycle, and is known for exhibiting a rich variety of properties, such as cell differentiation, chemotaxis, grouping into a single organism, etc. Starting from single individuals that consume the resources of their environment, they form a single multi-cellular organism when the resources are depleted. This organism moves collectively until a new area that is rich in resources is found and releases spores that start a new life-cycle. During that life period, each amoeba releases a chemical agent that is diffused into the environment and attracts nearby agents by means of chemotaxis. After releasing the chemical agent, each amoeba becomes refractory and insensitive for a period of time. Following that, a new cycle of accumulation and release of the chemical agent follows. The properties of Dictyostelium discoideum have been extensively studied, and several models have been developed, either trying to imitate or model its behaviour, see for example [START_REF] Nagano | Modeling the model organism Dictyostelium discoideum[END_REF], [START_REF] Vasiev | A model for cell movement during Dictyostelium mound formation[END_REF], [START_REF] Agarwal | Simulation of aggregation in Dictyostelium using the cell programming language[END_REF].

We here study an instance of the reaction-diffusion-chemotaxis aggregation scheme that we call the virtual amoebae model, or amoebae model, for short. The amoebae model has been introduced in [START_REF] Fatès | Solving the decentralised gathering problem with a reaction-diffusion-chemotaxis scheme -social amoebae as a source of inspiration[END_REF]. It is formed by a twolayered cellular automaton, with one layer corresponding to the environment while the second layer models the amoebae. In the first layer the transmission of the chemical agents is simulated by using a simple reaction-diffusion cellular automaton, see [START_REF] Greenberg | Pattern formation and periodic structures in systems modeled by reactiondiffusion equations[END_REF], [START_REF] Jörg | Cellular automata for reaction-diffusion systems[END_REF]. In the second layer the movements of the amoebae are guided by presence of chemical agents in the first layer, that we call chemotaxis. The "coupling" of the agent layer with the environment layer is achieved by letting each agent to initiate the transmission of the chemical agent, that we call firing. The firing events of each amoeba occur randomly. The firing probability of each agent is constant over time and is denoted by λ.

This current study is mainly focused on identifying an optimal firing probability, λ * , that minimises the aggregation time. Finding this probability is important both in the merit of applications as well as controlling the behaviour of the model. The existence of an optimal firing probability has first been observed in [START_REF] Fatès | Solving the decentralised gathering problem with a reaction-diffusion-chemotaxis scheme -social amoebae as a source of inspiration[END_REF], but was not studied further. Our purpose here is to give an experimental study of how λ * varies with different simulation conditions and show how the existence of an optimal value is related to the presence of two qualitatively different behaviours of the model.

The paper is organised as follows: In the next section, we describe shortly the basic characteristics of the model, its parameters and we outline the observed model behaviour. Following that, Sec. 3 describes the experimental procedure that we used to determine the optimal firing rate, as well as our observations and comments on the dynamical behaviour of the system. Finally, Sec. 4 presents our conclusions and future studies.

Model Description

As we mentioned above , the amoebae model consists of two different layers on a cellular automaton, one that models the environment and one that models the behaviour of the amoebae. These two layers are coupled, so that the state of the the environment is affected by the amoebae and the amoebae react to changes in the environment. More specifically, chemical agent transmission is modelled using the Greenberg-Hastings reaction-diffusion model, [START_REF] Greenberg | Pattern formation and periodic structures in systems modeled by reactiondiffusion equations[END_REF].

Environment Layer

Let L = {1, . . . , L} × {1, . . . , L} be a square array of cells, where L is the environment size. At time t with each cell c = (c x , c y ) is associated a state σ t c , such that σ t c ∈ {M, . . . , 0}. State M is called the excited state, state 0 the neutral state, while states M -1, . . . , 1 are the refractory states. Each cell c is connected to its 8 nearest neighbours N c according to

N c = {c ′ ∈ L : max(|c x -c ′ x |, |c y -c ′ y |) = 1}
The time evolution of the state each cell can be described as a function of its current state σ t c and the states of the cells in N c . Let E t c denote the number of excited cells in the neighbourhood of c at time t,

E t c = {c ′ ∈ N c : σ t c ′ = M }. Then, σ t c =    M , σ t c = 0 and |E c | > 0 σ t c -1, σ t c ∈ {1, . . . , M -1} 0, otherwise
Note that other neighbourhood types are also possible, as for example 4connected neighbourhood, circular, hexagonal, and so on. Different instances of the amoebae model with different topologies were tested in [START_REF] Fatès | Solving the decentralised gathering problem with a reaction-diffusion-chemotaxis scheme -social amoebae as a source of inspiration[END_REF] and it has been shown that aggregation is successful in all cases. Also note that the environment we use has free boundaries so that the reaction-diffusion waves that reach the boundary cells are absorbed.

Amoebae Layer

From the cellular automata viewpoint, the amoebae are represented in the environment as a property of the cells, in addition to the cell state. Let P t c denote the number of amoebae that are located at time t in cell c. Since we don't assume any death or birth process, the number of amoebae is constant, c∈L P t c = const. A cell will be called empty if it contains no amoebae and free if it contains less than two amoebae. An amoeba can only move to a free cell. If a cell contains more than one amoebae, only one of them will move at each time. This approach simplifies the conflict solving procedure in each cell that would be required to impose a limit on the number of amoebae that a cell may contain. The motion of amoebae is governed by the following rules:

• Move randomly to a free excited neighbouring cell.

• Otherwise, stay on the same cell.

An alternative, equivalent, view of the amoebae model would be that of a multi-agent system, in which the agents "reside" on a two-dimensional grid. The main difference between these two perspectives is that the former is more suitable for computational purposes, since the existence and number of amoebae in each cell can either be incorporated into the cell state or included as a secondary cell state, while the latter focuses on the system as interacting agents. This duality is further discussed in [START_REF] Spicher | From reactive multi-agent models to cellular automata -illustration on a diffusionlimited aggregation mode[END_REF].

Coupling

The coupling of the two layers defines how the amoebae interact with the environment and how chemotaxis is accomplished. This interaction is described by the following informal rules.

• At each time step, an amoeba that is on a neutral cell initiates the transmission of a reaction-diffusion wave with probability λ.

• If an amoeba that lies on a neutral cell detects excited cells in its neighbourhood, it moves towards one randomly selected excited cell.

Movements of the amoebae happen when a reaction-diffusion wavefront has reached their neighbourhood. Although the above rules are very simple, the process of aggregation has been shown, in the previous study, to be robust to the presence of obstacles in the environment and noise on the movements of the amoebae. For a more thorough description of these properties, see [START_REF] Fatès | Solving the decentralised gathering problem with a reaction-diffusion-chemotaxis scheme -social amoebae as a source of inspiration[END_REF].

Qualitative Description of Model Characteristics

We now discuss qualitatively what is the expected and observed model behaviour with respect to the probability of transmission, λ. First of all, note that as λ tends to 0 then the probability that a wave is fired will tend to 0 as well, so the time required for the aggregation will grow and for λ = 0 it is infinite.

Similarly, as λ tends to 1, the amoebae will transmit with a very high probability at each time step. Since reaction-diffusion waves annihilate as they collide, the probability that a reaction-diffusion wave will reach an amoeba, depends on the probability that the amoeba will not fire a wave, 1λ, and therefore will decrease as λ → 1. For λ = 1 all amoebae will fire at the maximum rate and no chemotaxis will take place, since no waves will ever reach an amoeba, which results in an infinite aggregation time.

Since the time required for the agents to form a single cluster tends to infinity as λ → 0 or λ → 1 we expect that there exists at least one value of λ that minimises the time required for the agents to aggregate.

Experimental Results

Experimental Protocol

We determine the time required for the agents to aggregate by measuring the number of different clusters at each time step. Formally, using notions from graph theory, we may define a cluster as follows. Let G = {c 1 , . . . , c N } denote the set of cells c such that P t c > 0. Define C + = {c ∈ L : P t c > 0}. Further, for i ∈ L let Γ({i}) = {j ∈ L : j ∈ N i ∩ C + } and for I ⊂ L, Γ(I) = ∪ i∈I Γ(i). Using the latter, define Γ 2 (i) = Γ(Γ(i)) and similarly Γ * (i) = Γ(Γ(. . . Γ(i) . . .)), the transitive closure of the graph defined on agents and the edge relation defined by Γ. The number of connected components can be expressed compactly as |{Γ * (i) : i ∈ L}|. Determining the formation of a single cluster is accomplished by counting the number of connected components of the graph generated this way. This is equivalent to assigning to each group of amoebae that belong to the same connected component a "colour" property and then counting the number of different "colours". The algorithm we used was based on a recursive exploration and "colouring" of the neighbourhood of each amoeba. Let n c denote the number of colours and col(c) the colour property.

⊲ procedure recursivePaint(c, col)

⊲ col(c) ← col ∀c ′ ∈ N c : col(c) = 0 and P c ′ > 0 recursivePaint(c ′ , col) end procedure • // main procedure ⊲ n c ← 0 ⊲ ∀c ∈ L, col(c) ← 0 ⊲ ∀c ∈ L If P c > 0 and col(c) = 0 n c ← n c + 1, col(c) ← n c recursivePaint(c, n c ) ⊲ return n c
If there is only one colour, then the aggregation of the amoebae into a single cluster has been completed. Each experiment can be defined by the following set of parameters: the grid dimension L, the number of amoebae N and their initial distribution, the firing probability λ as well as the neighbourhood type N c and the number of states of the reaction diffusion waves, M . To identify the dependence λ * = f (N, L) we measure the aggregation time by repeating N s times the simulations. For the sake of simplicity, we do not examine the dependence on M and fix M = 4 in all the experiments. Figure 2 depicts an example of the results of our experiments for a constant density and two different environment sizes1 . The curves clearly show the existence of an optimal firing probability. To identify λ * from the mean measured aggregation times for each L and N , we used the following method: Starting from a polynomial of small degree, we did a numerical polynomial fit on t(log(λ)), and by inspecting the resulting curves, we progressively increased the number of factors, taking care not to obtain an "over-fitted" polynomial. Then, by differentiating the resulting polynomial, we identified the value log(λ)) where the derivative changed sign and that corresponded to a minimum number of time steps required for convergence. The experimental values covered three grid sizes, L = 100, 150, 200 and number of amoebae that corresponds to densities d A ranging from 0.01 to 0.43 with a step 0.07. The value of λ ranged from 0.00001 to 0.16. We used N s = 30 samples per experiment, as the major limiting factor for the quality of our result was the time required to perform the simulations.

Figure 3 shows the dependency of λ * on L and N (or d A ). As we observe, the points for the three different grid sizes seem to follow similar laws, and decrease rapidly as the density increases.

Interpretation of the

To better understand the results, we propose to define the following qualitative phases during the aggregation process.

1 Immediately after the initialisation of an experiment, and for relatively high values of λ the amoebae form small condensates, as is shown in Fig. 1.a.

2 During the second phase, the local condensates are progressively merged into larger size groups 3 The last phase of aggregation, usually involves few large scale groups of amoebae, that compete among each other, Fig. 1.b. Aggregation completes as soon as one cluster grows significantly in size with respect to the others.

4 A single cluster is formed.

Figures 4 and5 show the time evolution of the agent aggregation for two different values of λ. We observe on Fig. 4 that that the amoebae converge directly into a single cluster and that do not go through the phases 1 to 3. In fact, in many cases, for small values of λ the aggregation does not even go through the first phase where the formation of micro clusters occurs, and the amoebae converge rapidly to a single cluster. Values of λ much smaller than λ * display the same behaviour, but with an increased convergence time, since the firing rate is decreased. On the other hand and for relatively high values of λ the system will undergo through phases 1 to 3, as can be seen in Fig. 5. More specifically, as the value of λ increases these phases are further separated into sub-phases, where the initial micro clusters are merged into medium size clusters, and so on, until two or three competing clusters remain. In short, the major factor that slows down the aggregation is the formation of two or more competing clusters of amoebae, of similar size. An example of such a formation can be seen in Fig. 1.b. These structures tend to persist for a comparatively large amount of time and usually appear after the first phase, as smaller clusters merge together. As a conclusion, λ * separates the two qualitative behaviours described above as it corresponds to the highest value of λ for which no competing clusters appear. Now, the dependence of λ * with respect to the density, seems to follow an inverse proportionality law. To intuitively explain this behaviour, we should mention that as the density increases, the number of events, for constant λ, also increases. To minimise the probability of cluster formation, the firing rate should decrease proportionally, so as to prevent local aggregation to micro clusters that

Conclusions and Future Research

The studies of the optimal firing probability gave rise to a series of interesting questions regarding the dynamics and details of the time evolution of the model. An interesting problem is to study to which extent our observations can interpreted as a "symmetry breaking" on the interactions of the agents. This symmetry breaking appears as a change of behaviour in the model, so that, for λ ≫ λ * the dynamics of the model seem to be governed by the local interactions (small-scale interactions) of agents, that guide the cluster formation, while for λ < λ * the model seems to be governed by medium-or large-scale interactions among agents. On the same subject, studying the dynamics of micro cluster formation and the observed coupling of λ and density fluctuations on the small scale dynamics of the model, for λ > λ * is an interesting and rich topic on its own.

Another interesting problem of similar nature deals with the probability of formation of competing clusters as λ varies close to λ * . As we have mentioned, for probability of wave transmission equal to λ * the probability that competing clusters will form seems to be minimal. It is therefore interesting to study how the probability of competing cluster formation scales with respect to |λλ * |.

To improve on the quality of our results we are planning on transferring the simulation environment to FPGAs and exploit their inherent parallelism. Although this will significantly reduce the time required for each experiment and increase the quality of our results, it introduces new challenges, as for example, determining the number of clusters is a non-trivial problem when studied in the context of two dimensional meshes / arrays of processors.

Finally, we would like to study the dependence of the aggregation time with respect to the topology used. More specifically, we would like to investigate how λ * varies for the same parameters and different topologies, i.e. 4-connected, hexagonal and so on. To this end, we are also interested in studying how the aggregation would be affected if we moved towards a true "gradient-following" model. As we mentioned in Sec. 2, currently the amoebae follow only wavefronts, i.e. will move towards a cell, only if the state of the current cell is neutral and a neighbouring cell is excited. Following gradients, i.e. modifying the amoebae so that they move to a neighbouring cell depending on the difference of the state of the cells would enable them to move a longer distances while following a reaction-diffusion wave, and would probably further reduce convergence time.

Our ongoing studies on the model include modelling of the interactions of the agents, and the possibility that the model dynamics can be approximated by a "potential"-like function that describes the interactions of the agents. Finally, we are currently studying the dynamics of clusters. Given a non-zero probability of cluster formation, we are interested in determining how the clusters behave and what governs their aggregation times. On parallel, we are working on an analytic description of the model, that will verify the observed experimental behaviour.

Figure 1 :

 1 Figure 1: Snapshots of simulations for λ = 0.6, d A = 0.15, L = 100 (a) Small cluster formation during the first phase of aggregation (t = 500) (b) An example of two competing clusters, obtained for t ∼ 4000

LFigure 2 :

 2 Figure 2: Examples of convergence time versus λ plots, where the interpolated polynomial is also shown

Figure 3 :

 3 Figure 3: Plot of λ * versus time for the different environment sizes.

Figure 4 :

 4 Figure 4: Example of the evolution of the aggregation for λ = 0.00001, d A = 0.1

  Figure 5: Example of the evolution of the aggregation for λ = 0.08, d A = 0.1

see http://www.loria.fr/ ∼ fates/Amybia/project.html for the remaining curves that we used to obtain our results on λ *


Juslin Koffi

ASSESSMENT OF POLLUTANT SPREAD FROM A BUILDING BASEMENT WITH THREE VENTILATION SYSTEMS

INTRODUCTION

Ventilation aims at providing a sufficient air renewal for ensuring a good indoor air quality (IAQ), yet building energy policies are leading to adapting various ventilation strategies minimising energy losses through air renewal. A recent IAQ evaluation campaign in French dwellings shows important pollution of living spaces by VOCs such as formaldehyde, acetaldehyde or hexanal, particularly in buildings equipped with a garage [START_REF] Kirchner | Campagne nationale Logements (CNL) : Etat de la qualité de l'air dans les logements françaisrapport final[END_REF]. Besides, radon emission from soil is a subject of concern in many countries. Several studies are done to understand its release mode and deal with the spread of this carcinogen gas [START_REF] Collingnan | Basement depressurization using dwelling mechanical exhaust ventilation system[END_REF]. This paper aims to experimentally assess a contaminant spread from a house basement using mechanical exhaust and balanced ventilation systems, and natural ventilation.

METHODS

The investigations are carried out in the experimental house MARIA [START_REF] Ribéron | MARIA: an experimental tool at the service of indoor air quality in housing sector[END_REF] by means of tracer gas methods [START_REF] Roulet | Airflow Patterns within Buildings: Measurement Techniques[END_REF]. MARIA consists of four bedrooms, a bathroom and a shower at first-level, a livingroom, a kitchen and toilets at ground-level, all linked by a hall; the basement is connected to the hall by a closed door. The pollution source is simulated by a release of hexafluoride sulphur (SF 6 ) in the basement at 2 ml/s flow rate for 5 hours; concentrations are measured there and in five rooms of the habitable levels.

RESULTS

The measured SF 6 concentrations are presented by Figure 1 for exhaust ventilation: concentration in the basement reaches 690 mg/m 3 . Pollution levels in the exhaust rooms are quite comparable (up to 180 mg/m 3 ), likewise in the main rooms (bedrooms and living, about 55 mg/m 3 ). The maximum concentration in the hall is around 230 mg/m 3 . The other fraction of the pollutant is probably eliminated through the building envelope air leakage; for achieving this, wind and temperature difference between indoors and outdoors play the key role. That high dispersion of the contaminant within the dwelling tends to partly provide an explanation of the IAQ survey results mentioned above and an idea of what could be exposure to radon release in single-family houses.

Comparable results are found with natural ventilation. However, bedroom 3 is more polluted than the bathroom where the concentration is 150 mg/m 3 : this is due to the low driving forces of natural ventilation during the studies. In addition, concentrations at ground-level are inferior to 14 mg/m 3 .

For these exhaust ventilation systems, the depressurisation produced in the habitable rooms by the exhaust fan and the natural driving forces engenders great airflow from the basement towards these levels of the dwelling. This leads to the pollution of all experienced rooms. The best performance is achieved with balanced ventilation (see Figure 2). Only a little pollution is measured in the habitable levels of the dwelling. The maximum level does not exceed 14 mg/m 3 in the hall and the exhaust rooms, and concentration in the main rooms are lower than 2 mg/m 3 : further studies [START_REF] Koffi | Experimental Evaluation of Ventilation Systems in a Single-Family Dwelling[END_REF] show a suitable drainage of air and pollutant flows from the second room category to the first one with balanced ventilation.

Here, the tracer gas accumulates more in the injection room (930 mg/m 3 ) due to a lower air change rate (0.21 ach vs. 0.41 ach for exhaust ventilation). But in fact, the equilibrium between air extraction and air supply results in an almost zero-pressure zone in the hall, so that airflow from the basement towards the hall is very low. This is a characteristic of balanced ventilation systems. The use of such a system seems to bring a better protection against contaminants from basement. All these results should be interpreted by taking into account the building configuration and envelope air leakage as well as the test conditions. However, they give an evaluation of basement pollutants elimination by ventilation systems.

Figure ( 2 )

 2 Figure (1), Measured concentrations for mechanical exhaust ventilation system.

ACKNOWLEDGMENT

This study was carried out as part of a Ph.D. thesis at CSTB Research Centre in Marne-la-Vallée (Paris). It was directed by Pr. Francis Allard (LEPTIAB -University of La Rochelle, France) and Dr. Jean-Jacques Akoua (CSTB, France).


Édouard Gilbert

Rémi Gilleron

Marc Tommasi

Series, Weighted Automata, Probabilistic Automata and Probability Distributions for Unranked Trees

Keywords: Tree automata, weighted automata, xml Automates d'arbres, Automates pondérés, xml

We study tree series and weighted tree automata over unranked trees. The message is that recognizable tree series for unranked trees can be defined and studied from recognizable tree series for binary representations of unranked trees. For this we prove results of [1] as follows. We extend hedge automata -a class of tree automata for unranked trees -to weighted hedge automata. We define weighted stepwise automata as weighted tree automata for binary representations of unranked trees. We show that recognizable tree series can be equivalently defined by weighted hedge automata or weighted stepwise automata. Then we consider real-valued tree series and weighted tree automata over the field of real numbers. We show that the result also holds for probabilistic automata -weighted automata with normalisation conditions for rules. We also define convergent tree series and show that convergence properties for recognizable tree series are preserved via binary encoding. From [21], we present decidability results on probabilistic tree automata and algorithms for computing sums of convergent series. Last we show that streaming algorithms for unranked trees can be seen as slight transformations of algorithms on the binary representations.

Introduction

Tree structured data is commonly used in computer science. For instance, tree structures are the favorite data model for Internet data. They are also of great interest in natural language processing and bio-computing. Because of the rapid development of these application fields, we are faced with very large data sets of tree structured data. A key challenge is to design methods and algorithms to represent, query, transform, rank and mine into such very large data sets.

The approach we develop in this paper is to model large sets of tree structured data with probabilistic models. The main problem is the inference of such probabilistic models from data. This problem heavily relies on the choice of an adequate representation formalism for probability distributions over tree structured data. In the ranked case, most of the known approaches ( [START_REF] Carrasco | Stochastic inference of regular tree languages[END_REF] or [START_REF] Maletti | Learning deterministically recognizable tree series -revisited[END_REF]) consider the inference of probability distributions defined by deterministic probabilistic tree automata. On the one hand determinism eases the design of machine learning algorithms. On the other hand, determinism restricts the class of probability distributions: already in the string case, there are probability distributions defined by probabilistic automata which can not be defined by deterministic probabilistic automata [START_REF] Denis | Rational stochastic languages[END_REF]. Also, non-deterministic automata are useful for labeling trees because the question is to find the most likely labeling -i.e. the most likely run. Moreover, already in the string case, automata with non negative weights are less expressive than automata with real weights [START_REF] Denis | Rational stochastic languages[END_REF]. Non deterministic weighted tree automata correspond to recognizable tree series over the field of real numbers and, recently, inference of probability distributions defined by recognizable tree series over the field of real numbers has been considered [START_REF] Habrard | Learning multiplicity tree automata[END_REF][START_REF] Denis | Learning rational stochastic tree languages[END_REF].

Motivated by XML applications, we consider the inference of probability distributions over sets of unranked trees (i.e. trees where a node can have an unbounded number of direct subtrees). Thus, the first question is to define recognizable tree series for unranked trees. For this, we define weighted automata for unranked trees.

Along this line, hedge automata [START_REF] Thatcher | Characterizing derivation trees of context-free grammars through a generalization of automata theory[END_REF] are a popular model for unranked trees ( [START_REF] Brüggemann-Klein | Regular tree and regular hedge languages over unranked alphabets: Version 1[END_REF], [START_REF] Comon | Tree automata techniques and applications[END_REF]Chapter 8]). We extend both hedge automata and weighted tree automata defining weighted hedge automata. This leads to a rather intricate automata model and properties of recognizable tree series can not be easily shown. Thus, we consider binary representations of unranked trees. Several bijections which map unranked trees to ranked ones have been defined [START_REF] Comon | Tree automata techniques and applications[END_REF]Chapter 8]. Among them, an algebraic representation similar to the currying transformation of functions has been defined. This algebraic representation has the advantage of defining a bijection between a set of unranked trees over an alphabet Σ and a set of ranked trees over a ranked alphabet containing only one binary symbol and constants in Σ. We define weighted stepwise automata as weighted tree automata over those algebraic representations. We show that weighted hedge automata and weighted stepwise automata define the same sets of recognizable tree series.

Then, we consider tree series over the field of real numbers. As a consequence, weighted hedge automata and weighted stepwise automata define the same sets of recognizable stochastic tree series. We also show that the equivalence between weighted hedge automata and weighted stepwise automata also holds for probabilistic automata, i.e. when normalisation conditions over rules occur. We define convergent tree series ordering trees by increasing size and we show that the definition of recognizable tree series for unranked trees allows to define convergence of tree series in a consistent way. We also recall algorithms to compute sums of recognizable tree series defined by probabilistic tree automata with results from [START_REF] Etessami | Recursive markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF]. Using the same paper, we show that it is decidable whether a probabilistic tree automaton defines a probability distribution.

Last, we study algorithmic properties of the algebraic representation. Algorithms for ranked trees can be extended to unrankeds tree by applying them on binary representations; we show that in many cases, they can also be slightly transformed to apply directly to unranked trees.

Related work

In [START_REF] Hogberg | Bisimulation minimisation of weighted automata on unranked trees[END_REF], following [START_REF] Martens | On the minimization of XML schemas and tree automata for unranked trees[END_REF] for the non-weighted case, the authors provided bisimulation minimisation results for different classes of weighted unranked tree automata. Along the way, they proved the equivalence between weighted automata models (weighted hedge automata are called weighted unranked tree automata (wuta) in [START_REF] Hogberg | Bisimulation minimisation of weighted automata on unranked trees[END_REF], weighted stepwise automata are called weighted stepwise unranked tree automata (wsuta) in [START_REF] Hogberg | Bisimulation minimisation of weighted automata on unranked trees[END_REF]). While our message is to say that all results can be obtained via a binary representation of unranked trees, they do not put such an evidence in their paper. They consider weights from a semiring and do not consider the field of real numbers. Thus, they do not consider probabilistic automata and do not consider convergence properties of tree series.

Preliminaries

Let N be the set of positive integers. Let N * be the set of finite strings over N and let ∈ N * be the empty string. We denote by p.p the concatenation of two strings p, p ∈ N * . A subset P of N * is prefix-closed if p.p ∈ P implies that p ∈ P . A position set P is a non-empty prefix-closed finite set such that for every p.i ∈ P , we have p.j ∈ P whenever 1 ≤ j ≤ i. Let F be a finite set of symbols, a (finite ordered rooted) tree t is a mapping from a position set Pos (t) into F. Each element in Pos (t) is a position. It identifies a node of t associated with a symbol f = t(p) in F. The rank of p in t is the number of direct successors (or children) of p, that is the number of positions p.i ∈ Pos (t) where i ∈ N. A position p such that p.1 ∈ Pos (t) corresponds to a leaf of t, otherwise it corresponds to an internal node. The size |t| of a tree t is the cardinality of its position set. The height height(t) of a tree t is the maximal length of strings in its position set.

In the following, we consider two sorts of trees: ranked and unranked trees. In the ranked case, the alphabet can be partitioned into F = N n=0 F n such that for every n and f ∈ F n , the rank of any node labeled by f is n. In that case, F is said to be a ranked alphabet and f ∈ F n is a symbol of rank n. The set T F is the set of ranked trees on F. Also, T F can be defined as the smallest set such that

∀n ≤ N ∀f ∈ F n ∀(t 1 , . . . , t n ) ∈ T F f (t 1 , . . . , t n ) ∈ T F .
In the unranked case, the rank of nodes is not determined by the symbol. While the rank is finite for every node, it is unbounded. To distinguish between ranked INRIA and unranked trees, we denote by Σ the set of symbols and by T u Σ the set of unranked trees over Σ. Similarly, T u Σ can be defined as the smallest such that

∀n ∈ N ∀f ∈ Σ ∀(t 1 , . . . , t n ) ∈ T u Σ f (t 1 , . . . , t n ) ∈ T u Σ .
Let K be a commutative semiring. A K-tree series over a set of trees is a function r from the given set of trees to K. We will consider tree series over T F or T u Σ . When K is the Boolean semiring, the tree series actually define tree languages. In the following, we will mainly consider the case of tree series over K = R or K = R + . We first consider recognizable tree series over ranked trees defined by means of weighted tree automata [START_REF] Borchard | The Theory of Recognizable Tree Series[END_REF].

Definition 1. A weighted tree automaton is a tuple A = (F, Q, F, δ) such that F is a finite ranked alphabet, Q a finite set of states, F : Q → K a final function and δ : ( n∈N F n × Q n ) × Q → K a transition function.
Definition 2. Let t ∈ T F be a ranked tree and A = (F, Q, F, δ) an automaton on F. A run of A on t is a function from Pos (t) to Q, i.e. every position of t is associated with a state from Q. The weight weight(A, t, r, p) of a run r on a subtree of t at position p is computed as follows: if the rank of p in t is 0, then weight(A, t, r, p) = δ(t(p), r(p)); otherwise, let n > 0 be the rank of p, weight(A, t, r, p) is inductively defined by

weight(A, t, r, p) = δ t(p), r(p.1), . . . , r(p.n), r(p) • n i=1 weight(A, t, r, p.i).
The weight of a run r on t is weight(A, t, r) = F (r( )) × weight(A, t, r, ), i.e. the final function is applied at the root position. The weight of a tree t is the sum of weights of all runs of A on t, i.e. weight(A, t) = r weight(A, t, r). A weighted automaton A defines a recognizable tree series r A , which maps every t in T F on weight(A, t).

We should note that recognizable tree series are equivalent to rational tree series defined in [START_REF] Berstel | Recognizable formal power series on trees[END_REF] (where they are called recognizable formal power tree series) defined by linear representations.

Weighted Hedge Automata

When considering tree languages, there exist several models of unranked tree automata which were proved to have the same expressive power (see [START_REF] Comon | Tree automata techniques and applications[END_REF]Chapter 8]). Hedge automata are popular in the xml community. Roughly speaking, they combine tree-automata rules for the vertical recursion, and string automata over an alphabet of states for the horizontal recursion. We now extend hedge automata to the weighted case (a similar definition was proposed in [START_REF] Hogberg | Bisimulation minimisation of weighted automata on unranked trees[END_REF]). For the horizontal recursion, we use weighted string automata defining rational (string) series over an alphabet of states. We also add weights to tree-automata like rules.

Definition 3. A weighted hedge automaton is a tuple H = (Σ, Q h , F h , δ h ) where Σ is a finite alphabet, Q h a finite set of states, F h : Q h → K a final function. δ h : Σ × Q * h × Q h → K
is a transition function which can be described as follows. For every f ∈ Σ and target state q ∈ Q h there is a K-rational string series π f,q over Q * h and a weight w f,q ∈ K such that, for u ∈ Q * h , δ h (f, u, q) = w f,q • π f,q (u).

A tuple (f, q, π f,q , w f,q ) is called a rule and is written f (π f,q ) → q [w f,q ]. Moreover, the (string) series π f,q is assumed to be defined by a weighted string automaton S f,q = (Q h , Q f,q , ι f,q , ϕ f,q , τ f,q ), where Q h is the alphabet, Q f,q is a set of states, and ι f,q , ϕ f,q and τ f,q are, respectively, the initial, transition and final functions.

In general, it is assumed that the state sets Q f,q are pairwise disjoint. Moreover, we assume that there is only one rule for every f ∈ Σ and every q ∈ Q h . This is done without loss of generality because of the closure of rational (string) series under sum. It is important to note that the weighted string automata are non deterministic and that they can not be replaced by a deterministic one. Indeed, the class of (string) series defined by deterministic weighted automata is stricly included in the class of (string) series defined by non deterministic ones.

In order to define how weighted hedge automata compute weights of input unranked trees, we must define runs. But, it should be noted that, in the unranked case, a run of an automaton H on a tree is not completely defined by a labeling of the unranked input tree by states in the state set Q h of H. This is because a run must also memorize configurations of the weighted string automata over strings in Q * h . Thus, we consider inner positions in the trees that will memorize states associated with runs of the string automata S f,q .

The set IPos (t) of inner positions in a tree t is a subset of Pos (t)×(N∪{0}) defined by

IPos (t) = {(p, k) | p ∈ Pos (t) , 0 ≤ k ≤ rank(p)}. An inner position (p, k) is denoted by p[k].
Inner positions of the tree f (f, f (f, f ), g) are given in Figure 1. Now, a run of H on t defines a computation of a weighted hedge automaton on a tree t. A run is a function σ : IPos (t) → Q f,q which associates to each inner position the state of the automaton S f,q . A run also defines a labeling ρ σ of the unranked input tree t by states in the state set Q h of H. Indeed, for every node p of t of rank n, there is a unique state q in the state set Q h of H such that, for every k ∈ [0, n], we have σ(p[k]) ∈ Q f,q where f = t(p). We denote this state q by ρ σ (p). A run of an automaton on the tree f (f, f (f, f ), g) is shown in Figure 1. It should be noted that in [START_REF] Hogberg | Bisimulation minimisation of weighted automata on unranked trees[END_REF], a run of a weighted hedge automaton (called weighted unranked tree automaton) is defined to be the mapping ρ σ .

Example 1. Figure 1 represents a run of the weighted hedge automaton with two rules f (L 1 ) → q [2] and g(L 2 ) → q [START_REF] Denis | On probability distributions for trees: Representations, inference and learning[END_REF] where L 1 and L 2 , respectively, are the string series recognized by the following weighted string automata: q f,q 0 2 1 q f,q 1 1 q : 1 q : 2 q : 2 and q g,q 0 2 1 . Definition 4. Let H be a weighted hedge automaton defined as in Definition 3. Let t be an unranked tree, let p be a position of t, let f = t(p), and let n be the rank of p. Let σ be a run of H on t, let q = ρ σ (p). The weight weight(H, t, σ, p) of σ at position p and the weight weight(H, t, σ, p, m) of σ at internal position p[m] for 0 ≤ m ≤ n are inductively defined by

INRIA f [0] f 1[0] [1] f 2[0] f 2.1[0] 2[1] f 2.2[0] 2[2] [2] g 3[0] [3] f q f,q 0 f q f,q 0 q f,q 0 f q f,q 0 f q f,q 0 q f,q 0 f q f,q 0 q f,q 0 q f,q 1 g q g,q 0 q f,q 1 Figure 1: left: inner positions of f (f, f (f, f ), g); right: a run of the automaton given in Example 1 over f (f, f (f, f ), g). weight(H, t, σ, p, 0) = w f,q × ι f,q (σ(p[0])) (1) weight(H, t, σ, p, m) = weight(H, t, σ, p, m -1)×ϕ f,q (σ(p[m-1]), ρ σ (p.m), σ(p[m])) × weight(H, t, σ, p.m), 0 < m ≤ n (2) weight(H, t, σ, p) = weight(H, t, σ, p, n) × τ f,q (σ(p[n])). (3)
The weight of a run

σ on t is weight(H, t, σ) = F h (ρ σ ( )) × weight(H, t, σ, ).
The weight of a tree t is the sum of the weights of all runs of H on t, i.e. weight(H, t) = σ weight(H, t, σ). A weighted hedge automaton H defines a recognizable tree series r H which maps every t in T u Σ to weight(H, t).

Forget Unranked Automata Models

Weighted hedge automata is an ad hoc automata model for unranked trees. Definitions are intricate because of the string automata over an alphabet of states. Thus, properties of recognizable tree series for unranked trees can not be easily shown. It is simpler to consider tree automata over binary representations of unranked trees. In this section, we define the binary representation, then we define weighted stepwise automata as weighted tree automata over those binary representations representations. Last, we show that weighted hedge automata and weighted stepwise automata define the same sets of recognizable tree series.

Weighted Stepwise Automata

First, let us define the binary representation we use. The operator @ adds a new child at the end of the list of children of an unranked tree:

f @ t = f (t) ∀f ∈ Σ ∀t ∈ T u Σ f (t 1 , . . . , t n ) @ t = f (t 1 , . . . , t n , t) ∀f ∈ Σ ∀t 1 , . . . , t n , t ∈ T u Σ
Syntactically, given an alphabet Σ, we consider a ranked alphabet F @ = F 0 ∪ F 2 where F 0 = Σ and F 2 = {@}. Then, every unranked tree can be represented by a binary tree over F @ . This can be formally defined with the mapping t → t f

[0] f 1[0] [1] f 2[0] f 2.1[0] 2[1] f 2.2[0] 2[2] [2] g 3[0] [3] @ @ @ f f @ @ f f f g Figure 2: Bijection between inner positions of t = f (f, f (f, f ), g) and positions of t. from T u Σ to T F @ such that f = f and f (t 1 , . . . , t n ) = @(f (t 1 , . . . , t n-1 ), t n ). It should be noted that the mapping t → t is a bijection between T u Σ to T F @ .
Example 2. The binary representation of the unranked tree

f (f, f (f, f ), g) from Example 1 is @(@(@(f, f ), @(@(f, f ), f )), g).
There exists a bijection between the set IPos (t) of inner positions of an unranked tree t and the set Pos t of positions of its binary representation t. An example is given in Figure 2. This bijection is denoted by ψ t and defined by:

for [k] ∈ IPos (t), ψ t ( [k]) = 1 n-k
where n is the rank of in t and 1 n-k denotes the concatenation of n -k 1. It should be noted that ψ t ( [n]) = .

For

p.i[k] ∈ IPos (t) where p ∈ N * and i ∈ N, ψ t (p.i[k]) = ψ t (p[i]).2.ψ t ( [k])
where t is the subtree of t rooted at position p.i.

We define weighted stepwise automata as weighted tree automata (over ranked trees) that operate on binary representations of unranked trees.

From Weighted Hedge Automata to Weighted Stepwise Automata

Proposition 1. For every weighted hedge automaton H over Σ, there is a weighted stepwise automaton A over F @ such that, for every

t in T u Σ , r H (t) = r A (t).
Proof. It is easy to verify that any weighted hedge or stepwise automaton can be augmented with new states and rules of weight 0 without changing the series recognized. Therefore, we will use only one set of states.

Let H = (Σ, Q h , F h , δ h ) be a weighted hedge automaton, with weighted string automata S f,q = (Q h , Q f,q , ι f,q , ϕ f,q , τ f,q ). We modify the definition of H by defining the weighted string automata on the state set Q = f ∈Σ,q∈Q Q f,q by: ι f,q (q) = ι f,q (q) if q ∈ Q f,q , and 0 otherwise; ϕ f,q (q 1 , q , q 2 ) = ϕ f,q (q 1 , q , q 2 ) if q 1 , q 2 ∈ Q f,q , and 0 otherwise ;τ f,q (q) = τ f,q (q) if q ∈ Q f,q , and 0 otherwise. Clearly, this does not affected the series recognized by H. where n is the arity of the node p.m and ψ t (p[m]) = p . Lastly, (p .1, p .2, p ) is subject of a rule in the stepwise case, and its antecedent by ψ t is also subject of a rule in the hedge case. The proof directly follows these observations.

We define a weighted stepwise automaton A = (F @ , Q, F, δ) where Q = f ∈Σ,q∈Q Q f,q and for all q i , q j , q k ∈ Q:

F (q i ) = τ f,q (q i ) × F h (q) δ(f, q i ) = w f,q × ι f,q (q i );
δ(@, q i , q k , q j ) = τ g,q (q k ) × ϕ f,q (q i , q, q j ).

We must prove that, for every t in T u Σ , r H (t) = r A (t). For every unranked tree t, the mapping ψ t defines a one to one correspondence between runs of H on t and runs of A on t. Let σ be a run of H on t, we denote by ψ t (σ) the corresponding run of A on t. In order to prove that r H and r A are equal, it remains to show that, for every t and for every run σ of H on t, weight(H, t, σ) = weight(A, t, ψ t (σ)). Thus, let us consider an unranked tree t and a run σ of H over t. We prove that, for every position p weight(H, t, σ, p, n) = weight(A, t, ψ t (σ),

ψ t (p[n])) ( 4
)
where n is the rank of p in t and t(p) = f . We proceed by structural induction.

Base. Let p be a a position of rank 0. There is only one inner position p[0] and

ψ t (p[0]) is a leaf position in t. Then weight(H, t, σ, p, 0) = w f,q × ι f,q (σ(p[0])) (def. of weight) = δ(f, σ(p[0])) (def. of A) = weight(A, t, ψ t (σ), ψ t (p[0])) (def. of weight) (5)
Structural Induction. Let us consider a position p of rank n > 0 and let us assume that (4) holds for every position p.i in t. We prove by induction that, for every m such that 0 ≤ m ≤ n, we have:

weight(H, t, σ, p, m) = weight(A, t, ψ t (σ), ψ t (p[m])). (6)
Let m = 0, we use (5) thus weight(H, t, σ, p, 0) = weight(A, t, ψ t (σ), ψ t (p[0])). Let 0 < m ≤ n, let us suppose that (6) holds for m -1. We denote by q m the state ρ σ (p.m).

weight(H, t, σ, p, m) = weight(H, t, σ, p, m -1)

× ϕ f,q (σ(p[m -1]), q m , σ(p[m])) × weight(H, t, σ, p.m) (def. of weight) (7)
Let us consider the three terms in this product. By induction hypothesis:

weight(H, t, σ, p, m -1) = weight(A, t, ψ t (σ), ψ t (p[m -1])) (8)
RR n°7200

Let n be the rank of position p.m in t, then as q m = ρ σ (p.m), we have q m = σ(p.m[n ]) and by definition of δ in the construction of A from H:

δ(@, σ(p[m-1]), σ(p.m[n ]), σ(p[m])) = ϕ f,q (σ(p[m-1]), q m , σ(p[m]))×τ f,qm (q m ).
(9) Thus, thanks to the definition of weight in (3) and to the structural induction hypothesis, we get:

weight(H, t, σ, p.m) = weight(H, t, σ, p.m, n ) • τ f,qm (q m ) = weight(A, t, ψ t (σ), ψ t (p.m[n ])) • τ f,qm (q m ). ( 10
)
Using equations ( 7), ( 8), ( 9), [START_REF] Hogberg | Bisimulation minimisation of weighted automata on unranked trees[END_REF], we obtain that

weight(H, t, σ, p, m) = weight(A, t, ψ t (σ), ψ t (p[m -1])) × δ(@, σ(p[m -1]), σ(p.m[n ]), σ(p[m])) × weight(A, t, ψ t (σ), ψ t (p.m[n ])). Now, it remains to recall that ψ t (p[m -1]) = ψ t (p[m]).1 and ψ t (p.m[n ]) = ψ t (p[m]
).2, and then using the definition of weight for A, we obtain:

weight(H, t, σ, p, m) = weight(A, t, ψ t (σ), ψ t (p[m]))
Thus we have proved that (4) holds for every position p in t. Now let q = ρ σ ( ) and let n be the rank of in t. Now using the definition of weights in weighted hedge automata, we have

weight(H, t, σ) = F h (q) × weight(H, t, σ, ) = F h (q) × weight(H, t, σ, , n) × τ f,q (σ( [n])) (11)
Also, by definition of weights in weighted tree automata

weight(A, t, ψ t (σ)) = F (ψ t (σ)( )) × weight(A, t, ψ t (σ), ) = τ f,q (ψ t (σ)( )) × F h (q) × weight(A, t, ψ t (σ), ). (12)
Recall that ψ t ( [n]) = and σ( [n]) = ψ t (σ)( ). Thus using (4), we obtain weight(H, t, σ) = weight(A, t, ψ t (σ)) which concludes the proof.

From Stepwise Weighted Automata to Weighted Hedge Automata

Proposition 2. For every weighted stepwise automaton A over an alphabet {@} ∪ Σ, there is a weighted hedge automaton H over Σ such that, for every t in T F @ , r A (t) = r H (t) where t is the unranked tree which binary representation is t.

INRIA

Proof. Let A = (F @ , Q, F, δ) be a weighted stepwise automaton over F @ = {@} ∪ Σ. Let H = (Σ, Q h , F h , δ h ) be the weighted hedge automaton defined by:

Q h = Q, F h = F , and δ h contains rules f (π f,q ) → q [1]
where each series π f,q is defined by a weighted string automaton S f,q = (Q, Q, ι f , ϕ, τ q ) over alphabet Q with state set Q, and functions defined by: ι f by ι f (q) = δ(f, q), τ q by τ q (q) = 1 and τ q (q ) = 0 whenever q = q ; finally, ϕ(q 1 , q, q 2 ) = δ(@, q 1 , q, q 2 ). Note that the states and the alphabet of these automata are similar, that their initial function will only depend on f , the final function, only on q and the transition function is the same for every automaton. The proof is similar to the proof in Subsection 4.2. It is simpler because final weights are equal to 1.

Probabilistic automata

As said in the introduction, probabilistic automata are used to define probability distributions over sets of trees. We define probabilistic automata over sets of unranked trees and we show that probabilistic hedge automata and probabilistic stepwise automata define the same sets of tree series. Definition 5. Let A be a weighted tree automaton and q a state of A. The state q is accessible if and only if there is a symbol a ∈ Σ such that δ(a, q) = 0 or if there are two accessible states q 1 , q 2 such that δ(@, q 1 , q 2 , q) = 0. Similarly, q is productive if and only if F (q) = 0 or there are states q 1 , q 0 such that q 0 is productive and δ(@, q, q 1 , q 0 ) = 0 or δ(@, q 1 , q, q 0 ) = 0.

The automaton A is trimmed if every state of A is both accessible and productive.

A similar definition can be given for hedge automata. Checking whether an automaton is trimmed can be done with the same algorithms than in the non weighted case (see [START_REF] Comon | Tree automata techniques and applications[END_REF]). Definition 6. A probabilistic stepwise automaton A is a weighted stepwise automaton A = (F @ , Q, F, δ) such that:

∀f ∈ Σ, ∀q ∈ Q, δ(f, q) ∈ R + ; ∀q 1 , q 2 , q ∈ Q, δ(@, q 1 , q 2 , q) ∈ R + ; ∀q ∈ Q, q1,q2∈Q δ(@, q 1 , q 2 , q) + f ∈Σ δ(f, q) = 1; q∈Q F (q) = 1. Definition 7. A probabilistic hedge automaton H is a weighted hedge automa- ton H = (Σ, Q h , F h , δ h ) as in Definition 3 such that: ∀f ∈ Σ, ∀q ∈ Q h , w f,q ∈ R + ; ∀q ∈ Q h , f ∈Σ w f,q = 1; q∈Q h F h (q) = 1; RR n°7200
∀q ∈ Q, ∀f ∈ Σ, S f,q is a probabilistic string automaton.

We prove that probabilistic hedge automata and probabilistic stepwise automata are equally expressive. To do that, we first observe a fact that follows the construction given in the proof of Proposition 2.

Proposition 3. For every trimmed probabilistic hedge automaton H over Σ, there is a probabilistic trimmed stepwise automaton A over F @ such that for every t ∈ T u Σ , r H (t) = r A (t). Vice-versa, for every trimmed probabilistic stepwise automaton A over F @ there is a trimmed probabilistic hedge automaton H over Σ satisfying the same relation.

Proof. It is easy to prove that, given a trimmed probabilistic hedge automaton H, the equivelent trimmed stepwise weighted automaton A defined in the proof of Proposition 1 is probabilistic.

The converse transformation is tedious because we must modify the construction given in the proof of Proposition 2 because of the normalization conditions required by probabilistic automata. It should be noted that we use existence of an inverse for ×.

Let A = (F @ , Q, F, δ) be a trimmed probabilistic stepwise automaton over F @ and H = (Σ, Q, F, δ h ) be the weighted hedge automaton defined in the proof of Proposition 2. Let S f,q be the automaton associated with the rule f (π f,q ) → q in H. Let

s f,q = u∈Q * π f,q (u) .
According to [4, Prop. 17], s f,q is an element of R + . We first prove that

Fact 1. f ∈Σ s f,q = 1. Proof. Given a state q ∈ Q of A, let S b q = (Σ b q , Q b q , ι b q , ϕ b q , τ b q ) be the weighted string automaton defined by Σ b q = Q, Q b q = Q ∪ Σ, ι(f ) = 1 whenever f ∈ Σ, ι(q) = 0 otherwise, δ(f, , q) =
w f →q whenever f ∈ Σ and δ(q 1 , q 2 , q 3 ) = w @(q1,q2)→q3 whenever q 1 and q 3 both are in Q. τ ( q) = 1, τ (q) = 0 when q = q.

Then S b q is a probabilistic automaton. Let π b q be the series defined by S b q . By definition, S b q is clearly equivalent to the union of all S f,b q . Thus for every

u ∈ Q * , f ∈Σ π f,b q (u) = π b q (u). Moreover, u∈Q * π q (u) = 1 [14]. Thus f ∈Σ s f,b q = f ∈Σ u∈Q * π f,b q (u) = u∈Q * f ∈Σ π f,b q (u) = u∈Q * π b q (u) = 1.

INRIA

Now, let us define the automaton H = (Σ, Q, F, δ h ) by defining rules f (π f,q ) → q [s f,q ] for all s f,q = 0. The series π f,q is defined as in the proof of Proposition 2, except for the termination function τ f,q which is defined by τ f,q = τ q • s -1 f,q . H satisfies the conditions of Definition 7:

∀f ∈ Σ, ∀q ∈ Q, w f,q ∈ R + ; ∀q ∈ Q, f ∈Σ w f,q = 1; According to Fact 1, q∈Q F (q) = 1.
The series π f,q is an R + -string series and u∈Q * π f,q (u) = s -1 f,q • u∈Q * π f,q (u) = 1. As a consequence, π f,q can be defined by a probabilistic automaton [START_REF] Denis | Rational stochastic languages[END_REF]Prop. 18].

Finally for every t, r H (t) = r H (t) = r A (t).

5 Convergence of real-valued tree series

Convergence and Absolute Convergence

For applications, we are interested in recognizable tree series over R which define probability distributions. But such series may map trees to negative numbers. This makes harder the computation of the sum of a series. Therefore, a first step is to define convergent tree series according to some fixed ordering over trees. We propose to order trees by increasing size: Definition 8. Let r be an R-tree series over T F ( or over T u Σ ), r is convergent if the sequence of partial sums |t|≤n r(t)

n≥1 has a finite limit. If r is convergent then t∈T F r(t) = n=∞ n=1   |t|=n r(t)   .
We have chosen this definition because it is robust with respect to the binary representation of unranked trees: Proposition 4. Let r be an R-tree series over T u Σ and let r be the R-tree series over T F @ defined by: ∀t ∈ T F @ , r(t) = r(t) where t is the binary representation of t. Then r is convergent if and only if r is convergent. Note that, given an R-tree series r over T F @ , the R-tree series r over T u Σ is uniquely defined.

The proposition holds because, for every t, t ∈ T u Σ , |t| = |t | if and only if t = t . Indeed, for every t ∈ T u Σ , t = 2 |t| -1. Absolute convergence of tree series can be defined: an R-tree series r is said to converge absolutely if t∈T F |r(t)| < ∞. An absolutely convergent Rtree series is convergent according to our definition and also according to any reordering of terms in the infinite sum.

Strong Convergence

The notion of strong convergence was introduced in [15]: Definition 9. An R-tree series r is said to be strongly convergent if the series y defined by y

(t) = |t| × r(t) is convergent. If r is strongly convergent then t∈T F y(t) = t∈T F |t| × r(t) = n=∞ n=1   |t|=n n × r(t)   .
First, we prove that: Proposition 5. If an R-tree series r is strongly convergent then r is convergent.

Proof. Let r be an R-tree series. Let (r n ) and (y n ) be the sequences of partial sums defined by:

r n = t∈T F |t|=n r(t) y n = n × r n = t∈T F |t|=n n × r(t).
The strong convergence of r ensures that the series y n converges. Because r n = y n × 1 n and the sequence 1 n decreases towards zero, Abel's test ensures the series r n to be convergent. Thus the R-tree series r is convergent.

The definition of strong convergence is robust with respect to the binary representation of unranked trees: Proposition 6. Let r be an R-tree series on T u Σ and let r be the R-tree series on the binary representations. Then r is strongly convergent if and only if r is strongly convergent.

Proof. Let r be an R-tree series on T u Σ and let r be the equivalent series on the binary representations, i.e. ∀t ∈ T u Σ , r(t) = r(t). Let us consider the sequences of partial sums defined by: r n = |t|=n r(t); r n = |t|=n r(t); y n = n • r n ; and y n = n • r n . We have t = 2 |t| -1 and trees in T F @ are binary. Thus, y 2n-1 = (2n -1) |t|=2n-1 r(t) and y n = 0 whenever n ∈ 2N -1.

If the R-tree series r is strongly convergent then y n converges. From Proposition 5, we obtain that r n = r n is convergent. Because r n is convergent and (2n -1)r n is convergent, as the sum of convergent series is convergent, the series ((2n -1)r n + r n ) is convergent. This leads to say that the series 2 • y n is convergent. Thus y n converges, i.e. the R-tree series r is strongly convergent.

Conversely, if the R-tree series r is strongly convergent then y n converges. r n converges and as a consequence (2n -1)r 2n-1 = y n converges. Thus the R-tree series r is strongly convergent.

We will present in the next section a recognizable R + -tree series which is convergent but not strongly convergent.

INRIA 6 Recognizable Stochastic Tree Series

A recognizable stochastic tree series r is a recognizable R-tree series over T F which defines a probability distribution over T F , i.e. ∀t ∈ T F , 0 ≤ r(t) ≤ 1 and t∈T F r(t) = 1. A recognizable tree series is called a recognizable stochastic tree language in papers by Denis et al. For probabilistic context-free grammars, the term consistent was introduced in [START_REF] Wetherell | Probabilistic languages: A review and some open questions[END_REF] for probabilistic context-free grammars defining probability distributions, while Chi et al [START_REF] Chi | Statistical properties of probabilistic context-free grammars[END_REF][START_REF] Chi | Estimation of probabilistic context-free grammars[END_REF] use the term of proper distributions.

Recognizable stochastic tree series can be defined by weighted tree automata over R, or by weighted tree automata over R + , or by probabilistic tree automata. We will compare the corresponding classes of probability distributions in Section 7. First, we consider the question whether a weighted tree automaton defines a stochastic tree series, we present some decidability results and show how to compute sums of series.

Probabilistic Tree Automata and Stochastic Tree Series

In the string case, every probabilistic automaton over Σ defines a probability distribution over Σ * . In the tree case, this property does not hold. Indeed, let us consider the example used in [START_REF] Wetherell | Probabilistic languages: A review and some open questions[END_REF] 1 . Let F @ = {@, a}, and let A α = (F @ , Q, F, δ α ) be a family of probabilistic stepwise automata parameterized by α ∈ [0, 1] and defined by: Q = {q}, F (q) = 1, δ α (a, q) = 1 -α, and δ α (@, q, q, q) = α. Let r α be the recognizable tree series defined by A α . Let s n = height(t)≤n r α (t). It is easy to show: ∀n, s n ≤ min{1, 1-α α } and s n+1 = α × s 2 n + (1 -α). Thus r α is convergent and t∈T F @ r α (t) = 1 if and only if α ≤ 1 2 . In the case α > 1 2 , the limit is strictly lesser than 1 because infinite trees have a non zero weight. Thus, Fact 2. There is a probabilistic tree automaton which does not define a stochastic tree series.

We will consider in the next subsection whether it is decidable that a probabilistic automaton defines a stochastic tree series. But, before we compare the convergence notions. Let us again consider series r α , and let us define

u n = height(t)≤n n × r α (t), algebraic computation allows to show that u n+1 = 2α × s n × u n + α × s 2 n + (1 -α). When α ≤ 1 2
, s n converges to 1, then the limit u of u n must satisfy u = 2α × u + 1. Thus, for α = 1 2 , the series is not strongly convergent. Thus, Fact 3. There is a recognizable stochastic tree series defined by a probabilistic tree automaton which is not strongly convergent. Let us summarize the example. For the series r α defined as above:

For every α < 1 2 , the series r α is stochastic, it is strongly convergent and the sum u is equal to 1 1-2α which is the expected value of the size of trees according to the probability distribution defined by r α ; 1 The original example was given for probabilistic context-free grammars.

RR n°7200

For α = 1 2 , the series r α is stochastic but it is not strongly convergent For every α > 1 2 , as r α = 1-α α × r 1-α , the series r α is strongly convergent but it is not a stochastic series because its sum 1-α α is strictly lower than 1.

Last, we show that

Fact 4. There exists a strongly convergent tree series which is not absolutely convergent.

Indeed, consider a series r such that

r n = |t|=n r(t) = (-1) n n•ln n . Then n • r n = (-1) n
ln n , which is convergent. However,

|r n | = 1 n•ln n is not convergent.
We are not aware of a recognizable strongly convergent tree series which is not absolutely convergent.

Decidability Results

As weighted tree automata (even probabilistic tree automata) do not necessarily define stochastic series, we consider the decision problems:

Nonnegativity problem

Instance: a weighted tree automaton A over R.

Answer: "yes" if and only if the recognizable tree series r A is nonnegative, i.e. ∀t ∈ T F , r A (t) ≥ 0.

Stochasticity problem for weighted tree automata

Instance: a weighted tree automaton A over R.

Answer: "yes" if and only if the recognizable tree series r A is stochastic.

The nonnegativity problem is undecidable. Indeed, the problem is undecidable for weighted string automata. It is immediate from the undecidability of the emptiness problem for (string) probabilistic automata (proof in [START_REF] Paz | Introduction to Probabilistic Automata[END_REF][START_REF] Blondel | Undecidable problems for probabilistic automata of fixed dimension[END_REF]). A consequence, shown in [START_REF] Denis | Rational stochastic languages[END_REF], is that it is undecidable whether a weighted string automaton over R defines a probability distribution. Therefore, the stochasticity problem for weighted tree automata is also undecidable.

Let us now consider the -specific to trees -decision problem:

Stochasticity problem for probabilistic tree automata Instance: a probabilistic tree automaton A.

Answer: "yes" if and only if the recognizable tree series r A is stochastic.

This problem is decidable in polynomial time as a consequence of deciding in polynomial time whether the probability of termination of 1-exit recursive Markov chain is 1, this is proved in [START_REF] Etessami | Recursive markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF] and a decision algorithm for probabilistic context-free grammars is proposed. We adapt it (it is very easy) to probabilistic tree automata. Let A = (F, Q, F, δ) be a probabilistic automaton over F and let us suppose that Q = {q 1 , . . . , q n }. We can view A as a top-down automaton INRIA (equivalently a regular tree grammar): consider the mapping δ as a set ∆ of rules of the following form rule : q rule → f (q rule1 , . . . , q rulen ) (w rule ) , where w rule = δ(f, q rule1 , . . . , q rulen , q rule ); consider states in Q such that F (Q) = 0 as initial states. Let A = (a ij ) 1≤i,j≤n be the matrix defined by

a ij = rule∈∆,q rule =q i w rule × n rule (q j )
where n rule (q j ) is the number of occurrences of state q j in the right-hand side of rule, i.e. in the state sequence (q rule1 , . . . , q rulen ). The spectral radius ρ(A) of a square matrix A is the maximum among the modulus of eigenvalues (real or complex) of A. Moreover, we can suppose that F (q 1 ) = 1. Following [START_REF] Etessami | Recursive markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF], a polynomial time algorithm for the stochasticity problem for probabilistic tree automata is: Input: a probabilistic tree automaton A over F. Output: yes if A defines a probability distribution, no otherwise. 1. Compute accessible states and remove all states unaccessible. 2. Compute productive states. If there is a state which is not productive then return no. 3. For the remaining probabilistic weighted automaton, compute the matrix A and its spectral radius ρ(A). If ρ(A) > 1 then return no, otherwise return yes.

Figure 3: decision algorithm for stochasticity of probabilistic tree automata

The correctness of the algorithm is a direct consequence of the proof of correctness of a similar algorithm for stochastic context-free grammars given in [START_REF] Etessami | Recursive markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF], itself obtained as a consequence of [Theorem 8.1, [START_REF] Etessami | Recursive markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF]] for 1-exit recursive markov chains. First, let us note that computations in steps 1 and 2 can be done with classical algorithms for (non weighted) tree automata. It is because for probabilistic tree automata checking accessibility and productivity of states can be done only with the structure of rules. It is no more true when weights can be negative. Indeed, testing whether a state is productive can not be done only on the structure of rules but sums must be computed and compared with 0. Second, for step 3, it is decidable in polynomial time whether the spectral radius of a square matrix is strictly less than 1. The correctness is related to the polynomial system of equations associated with a probabilistic tree automaton that we discuss in the next subsection.

Example. Let us consider a family of probabilistic automata A α,β parameterized by α, β with state set Q = {q 1 , q 2 }, F = {@, a, b}, F (q 1 ) = 1 3 , F (q 2 ) = 2 3 , and ∆ α,β = {q 1 → a(1 -α); q 1 → @(q 1 , q 2 )(α); q 2 → b(1 -β); q 2 → @(q 2 , q 2 )(β)}. The states q 1 and q 2 are accessible. When α = 1 (respectively β = 1), the state q 1 (respectively q 2 ) is not productive and the automaton does not define a probability distribution. When α = 1 and β = 1, the matrix A α,β is

A α,β = α α 0 2β
, the spectral radius of A α,β is max{α, 2β}, and ρ(A α,β ) > 1 if and only if α > 1 and β > 1 2 . If we summarize, we get that A α,β defines a probability distribution if and only if α < 1 and β ≤ 1 2 . We conclude by a property of strongly convergent tree series. Let us consider a probabilistic tree automaton A and the matrix A, and let us suppose that ρ(A) < 1. Then A n converges to 0 and the expected value for the size of trees is finite and can be computed as C × (I -A) -1 × B where B = (1, . . . , 1) t and C = (F (q 1 ), . . . , F (q n )). This expected value is also equal to t∈T F |t| × r A (t).

Example (continued). When α < 1 and β < 1 2 , we have

(I -A) -1 = 1 1-α α (1-α)(1-2β) 0 1 1-2β
and the expected value for the size of trees is

1 3 1 1-α + α (1-α)(1-2β) + 2 3 1 1-2β .

Computing the Sum of a Tree Series

Let r be a recognizable tree series defined by a weighted tree automaton A. For every state q i , the state probability of q i is the sum of the series for automaton A i obtained from A by modifying F in F i defined by F i (q i ) = 1. For every state q i , we define a variable x i . We can construct a system of polynomial equations x = P ( x) over variables x i . If exist, the state probabilities are solutions of this system of equations. When A is probabilistic, according to [START_REF] Etessami | Recursive markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF], the system has only positive coefficients, there is a least fixed point solution, and the least fixed point solution is the vector of state probabilities. Thus, the system of equations gives rise to an iterative numerical algorithm with which to approximate the least fixed point, thus to compute the sum of a recognizable tree series defined by a probabilistic tree automaton. In the same paper, they also provide an iterative numerical algorithm, based on a decomposed Newton's method.

Example (continued). For our running example, the system of polynomial equations is:

x 1 = α × x 1 × x 2 + (1 -α) x 2 = β × x 2 2 + (1 -β)
It can be solved analytically leading to

x 2 = min{1, 1-β β }, x 1 = 1-α 1-α×x2
. When the automaton is strongly consistent, i.e. when α < 1 and β < 1 2 , then x 1 = x 2 = 1. Let s be the sum of the series r A α,β , we have s = 1 3 × x 1 + 2 3 × x 2 = 1. In general, solutions can be approximated by computing x 1n and x 2n for n large enough where x 11 = 1 -α, x 21 = 1 -β, x 1n+1 = α × x 1n × x 2n + (1 -α), and

x 2n+1 = β × x 2 2n + (1 -β).
We should also note that it is proved (Theorem 3.2 in [START_REF] Etessami | Recursive markov chains, stochastic grammars, and monotone systems of nonlinear equations[END_REF]) that it requires an exponential number of iterations to compute the sum of the series xithin k bits of precision when β = 1 2 .

INRIA 7 Expressiveness

Tree Series and Weighted Automata

A recognizable R-tree series is a series defined by a weighted tree automaton over R. It is said to be nonnegative if ∀t ∈ T F , 0 ≤ r(t). We recall that it is said to be stochastic if ∀t ∈ T F , 0 ≤ r(t) ≤ 1 and t∈T F r(t) = 1. We compare classes of tree series depending on the class of weighted tree automata used to define them. Let us consider tree series defined over T F where F is a ranked alphabet. We use the letter R for recognizable tree series, N for non negative tree series, S for stochastic tree series. We use W T A for weighted tree automata over R, W T A + for weighted tree automata over R + , and P T A for probabilistic weighted tree automata. We precise the class of weighted automata between parenthesis. For instance, N (W T A) is the set of nonnegative recognizable tree series over T F defined by weighted tree automata over R. We have the following inclusions Proposition 7.

R(P

T A) ⊂ R(W T A + ) ⊂ R(W T A) 2. N (P T A) ⊂ N (W T A + ) ⊂ N (W T A) 3. S(P T A) = S(W T A + ) ⊂ S(W T A)

S(P T A) ⊂ N (P T A) = R(P T A)

Proof.

1. obvious considering the series r 2 defined by ∀t ∈ T F , r 2 (t) = 2 which is in R(W T A + ) but not in R(P T A), and the series r -1 defined by ∀t ∈ T F , r -1 (t) = -1 which is in R(W T A) but not in R(W T A + ).

N (P

T A) ⊂ N (W T A + ) using r 2 . More interestingly, N (W T A + ) ⊂ N (W T A)
states that negative weights allows to define more nonnegative recognizable tree series. It is a consequence of the following inclusion.

3. S(W T A + ) ⊂ S(W T A) states that negative weights allow to define stochastic recognizable tree series which can not be defined with nonnegative weights only. This is because this result already holds for string series as shown in [START_REF] Denis | Rational stochastic languages[END_REF]. The equality S(P T A) = S(W T A + ) can be proved in two steps: first show that if a stochastic tree series is defined by a weighted tree automaton with nonnegative weights then there exists a trimmed weighted tree automaton with nonnegative weights computing the series. Then rules can be normalized. It should be noted that we do not know if the stochasticity problem for weighted tree automata with nonnegative weights is decidable. It should also be noted that normalization implies to compute sums of series.

In [START_REF] Denis | Relevant representations for the inference of rational stochastic tree languages[END_REF], the authors introduce normalized weighted tree automata (denoted by W T A n ) for stochastic tree series where all tree series associated with states (for a state q, consider the series defined by the same automaton except that F (q) = 1) are stochastic. They show that S(W T A n ) = S(W T A). It can be deduced that S(P T A) = S(W T A + ).

4. S(P T A) ⊂ N (P T A) because there are tree series defined by probabilistic tree automata for which the sum of weights of all terms is strictly less than 1.

Recognizable Tree Series and Recognizable Tree Languages

The characteristic series r L of a language L ⊆ T F is defined by r L (t) = 1 if t ∈ L, and 0 otherwise. The characteristic series of a recognizable tree language is recognizable. An algebraic is given in [START_REF] Berstel | Recognizable formal power series on trees[END_REF]. Also it is easy to define a weighted tree automaton over R computing the tree series r L given a bottom-up deterministic automaton for L.

The converse is false. Indeed, consider F = {@, a, b} and the weighted tree automaton A a = (F, Q, F, δ) defined by: Q = {q 1 , q 2 }, F (q 1 ) = 0, F (q 2 ) = 1, δ(a, q 1 ) = 1, δ(a, q 2 ) = 1, δ(b, q 1 ) = 1, δ(@, q 1 , q 2 , q 2 ) = 1, δ(a, q 2 , q 1 , q 2 ) = 1, and δ(a, q 1 , q 1 , q 1 ) = 1, otherwise δ is zero. The automaton is non deterministic. It computes the series r a defined by r a (t) is the number of occurrences of a in t because the automaton guesses one occurrence of a and there is one run for each occurrence of a which leads to state q 2 . Now, similarly, the series r b is recognizable. Thus the series r a -r b is recognizable. But the set of trees such that (r a -r b )(t) = 0 (called the support of r a -r b ) is not a recognizable tree language.

Let us also recall that the series height where height(t) is the maximal length of paths in t is not recognizable. this can be proved by using a pumping lemma for recognizable tree series [START_REF] Berstel | Recognizable formal power series on trees[END_REF].

Tree Series and Deterministic Automata

As we have defined recognizable tree series by means of automata, the question of determinism arises. A weighted tree automaton A = (F, Q, F, δ) is said to be (bottom-up) deterministic if for every symbol f ∈ F, for every tuple (q 1 , . . . , q n ), there is a unique sate q such that δ(f, q 1 , . . . , q n , q) = 0. Let us use W DT A for weighted deterministic tree automata over R and P DT A for probabilistic deterministic weighted tree automata. While deterministic and non deterministic tree automata are equivalent, this is no more true for weighted tree automata.

Proposition 8.

R(W DT A) ⊂ R(W T A)

S(P DT A) ⊂ S(P T A)

Proof.

1. R(W DT A) ⊂ R(W T A) because the series size defined by, for every t ∈ T F , size(t) = |t| is recognizable. For instance, when F = {@, a, b}, size = 2(r a + r b ) -1. And, in general size = f ∈F r f , where r f computes the number of occurrences of f in a tree. And r f can be easily shown recognizable. The series size can not be defined by a deterministic weighted tree automaton. This is proved using a Myhill-Nerode theorem for recognizable tree series [START_REF] Borchardt | The myhill-nerode theorem for recognizable tree series[END_REF].

INRIA

2. This inclusion already holds for strings [START_REF] Denis | Relevant representations for the inference of rational stochastic tree languages[END_REF].

A weighted tree automaton A = (F, Q, F, δ) is said to be top-down deterministic if for every state q ∈ Q, for every symbol f ∈ F, there is a unique tuple (q 1 , . . . , q n ) of states such that δ(f, q 1 , . . . , q n , q) = 0. Top-down determinism is a very strong condition. The set of recognizable (stochastic) tree series defined by top-down deterministic automata is strictly included in the set R(W DT A) (R(P DT A)).

8 Implementing Tree Series for Unranked Trees

Size and memory

While it could seem that unranked trees are more efficient in memory than their binary counterpart, this would not be true. Indeed, consider for example that trees are written in a linear memory space of symbols. A binary tree written on such memory with the symbols F = Σ ∪ {@} would only occupy as many symbols as it counts node. Indeed, reading would be unambiguous as the rank of the tree is fixed. Working directly on ranked trees would require to mark the end of a list of children by a special symbol /, which would need to appear exactly once per node. In this context, memory usages are the same.

Example 3. While @ @ abc is unambiguously parsed as @(@(a, b), c), f f ab can be parsed as f (f, a, b), f (f (a, b)), f (f (a(b))), . . . However, if we mark the end of the children lists by /, then, e.g., f f a/b/// can only be parsed as f (f (a, b)).

Algorithmic considerations

In this section, we focus on algorithmic implications of the ranked/unranked correspondence. We show that any stream view algorithm working on unranked trees can be reduced to a stream view algorithm on binary representations.

xml data processing is done either through the stream view or the tree view. The former corresponds to SAX programming and the latter to DOM programming. Even in the latter case, inputs are serialized in a stream and need to be loaded with the former view anyway.

In the stream view processing, operations are realized in prefix, postfix or infix places. Each of these places corresponds to inner positions. We have seen in Section 4 and Figure 2 that inner positions correspond to nodes in the binary representation. Moreover, the order nodes are seen in the stream corresponds to a depth-first left to right traversal which is preserved in the binary representation. Thus operations realized at prefix, postfix or infix places can be interpreted as operations on the binary representation.

For instance, the evaluation of the weight of an unranked tree by a stepwise weighted automaton can be computed in the stream. Actions are performed when entering or leaving a node of the tree (the open and close tags in the stream):

When entering a node labeled f , push on the stack the vector u whose components correspond to states such that the rules for f are f → q [u q ] RR n°7200

When leaving a node, pop w then v from the stack and push u such that u q = q1∈Q q2∈Q M q q1,q2 v q1 w q2 where the rules for @ are @(q1, q 2 ) → q [M q q1,q2 ].

After reading a whole tree, there will be a single vector u on the stack. The weight of the tree is then q∈Q F (q)u q .

Conclusion

We have proved that binary representations of unranked trees are useful. Indeed, we have proved that the notions of recognizable tree series, stochastic tree series, convergence of tree series can be equivalently defined over unranked trees or over their binary representations. Moreover, we have seen that binary representations are rightly usable in streaming algorithms even when only having access to xml files without making the representation explicit.

However, there is still much research to do in this field both on the formal language side and on the machine learning side. For instance, many decision problems for convergence of tree series remain open and must be investigated. We have defined recognizable tree series for unranked trees with weighted tree automata. But defining recognizable tree series for unranked trees with linear representations remains challenging. Also learning tree series for unranked trees must be studied in more details.

INRIA

  Let us note that two inner positions p[m -1] and p.m[n] where n is the rank of position p.m in t are mapped by ψ t , respectively, to the left child and to the right child of ψ t (p[m]) in t. More precisely a triplet of position (p .1, p .2, p ) is in one to one correspondence with a triplet of the form (p[m -1], p.m[n], p[m])

RR n°7200

http://www.inria.fr ISSN 0249-6399

* This work was supported by the ANR Lampada project ANR-09-EMER-007


OCÉANOGRAPHIE BIOLOGIQUE. -Présence de quantités importantes de thiotaurine et d' hypotaurine dans les tissus de Riftia pachyptila (Pogonophore, Vestimentijêre). Note de Patrick Albéric, présentée par Lucien Laubier.

Les tissus (trophosome, branchie) de Riftia pachyptila sont particulièrement riches en thiotaurine et en hypotaurine (200 à 500 µmoles/g de tissu lyophilisè) qui représentent 50 à 75% de la totalité des composés aminés libres détectés.

Il est inhabituel que les liquides physiologiques des organismes vivants contiennent ces composés en quantité importante. Leur présence est peut-être liée au transport, à l'intérieur du corps de l'animal, d'une importante quantité d'ions sulfure nécessaire à l'activité chimiolithoautotrophe des bactéries symbiontes localisées dans le trophosome. BIOLOGICAL OCEANOGRAPHY. -Occurrence of thiotaurine and hypotaurine in the tissues of Riftia pachyptila (Pogonophora, Vestimentifera).

The blood of Riftia pachyptila Jones [START_REF] Jones | [END_REF] -one of the most distinctive and abundant animals of the deep-sea hydrothermal vents-contains a sulfide-binding protein that appears to concentrate sulfide from ambient water [2]. The hemoglobine which occurs in both the vascular blood and the coelomic fluid [3] has been the proposed binding molecule ( [2], [4]). The bounded form of sulfide in the blood would enable the simultaneous transport of both O 2 and H 2 S to the internal chemolithoautotrophic bacterial symbionts within the trophosome organ.

This study concerns the transfer of sulfur from the binding protein to the trophosome cells. The tube worm was collected at a depth of approximately 2,630 m on the East Pacific Rise from the 130 N site (Biocyarise, 1984). Portions of frozen trophosome and plume tissues were lyophilised and samples of powdery tissueswere extracted with bidistilled water and then centrifuged. Free aminoacids contents of subsequent solutions were directly obtained by the use of an automatic analyzer.

Standard procedure shows an important peak -75% of the total free amino acids (Table ) having the retention time of taurine (NH 2 C 2 H 4 SO 3 H).

However, the positive reaction obtained when spraying iodoplatinate reagent [START_REF] Greenstein | Chemistry of the amino acids[END_REF] following paper chromatography, which is significative of the presence of reduced sulfur ( [START_REF] Marco | [END_REF], [7]), does not fit with taurine.

The use of a method combining cyanolysis reaction and column chromatography [8] enabled us to discern that hypotaurine is the abundant sulfur-containing compound present in the plume tissues and that on the contrary thiotaurine is abundant in the trophosome (Fig.). In both cases, taurine accounts for only 20% of the total amount.

In the trophosome, the thiosulfonic form (R-SO 2 SH) may result from the sulfide transfer inside the coelomic fluid from the hemoglobine to the cells.

As the sulfur-containing compounds are present in both regions of the worm, they are probably dissolved in the blood.

At the site of gas exchange with the environment (obturacular plume) the sulfinie form (R-SO 2 H) would remain inactive.

The unloading of sulfide from the blood-protein might be achieved in the trophosome by an enzymatic process like transulfuraT.ion of di-and tri-cysteine derivatives 10 thiosulfonic compounds [9] and by spontaneous transulfuration between thiosulfonic compounds and thiosulfate [START_REF] Marco | [END_REF].

INTRODUCT[ON.
-Riftia pachyptila Jones [START_REF] Jones | [END_REF], est l'un des principaux composants des communautés animales découvertes autour des évents hydrothermaux du système de dorsales du Pacifique oriental.

Ces communautés bénéficient de l'activité chimiolithoautotrophe de bactéries sulfooxydantes et semblent indépendantes des apports trophiques provenant de la surface des océans.

Les fluides hydrothermaux chauds et riches en H 2 S sont très rapidement dilués par l'eau de mer. La température des eaux qui baignent les colonies de Riftia est en moyenne de 10°C. Leur teneur en H 2 S est de l'ordre de 100 à 500 µM [10] en raison de la dilution du fluide et de l'oxydation des sulfures par l'oxygène dissous dans l'eau de mer.

Arp et Childress [2] ont montré l'existence, dans le sang de Riftia, d'une protéine en solution capable de concentrer les sulfures (par rapport à l'eau environnante) au niveau du panache branchial et de les transporter jusqu'au trophosome, organe très vascularisé contenant les bactéries symbiontes. Il est vraisemblable que l'hémoglobine soit la protéine concernée par ce transport puisqu'elle constitue l'essentiel de la fraction protéique du sang [2] et que les quantités d'H 2 S fixées expérimentalement sont proportionnelles aux teneurs en hème [4].

Le site exact de fixation des sulfures par la protéine n'est pas encore établi, mais dans l'hypothèse d'un transport simultané de O 2 et H 2 S par la même molécule d'hémoglobine, seules les chaînes péptidiques seraient en mesure d'assurer la fixation du soufre (Toulmond, comm. pers.).

Au niveau du trophosome, le transport du soufre jusqu'aux bactéries intracellulaires nécessite certainement la mise en oeuvre d'un mécanisme capable de relayer la liaison protéine-sulfures. Des réactions métaboliques permettant le transfert du soufre en évitant l'apparition des ions sulfure toxiques sont connues ( [9], [11], [12]), notamment l'action enzymatique de la rhodanèse dont la présence a été signalée chez Riftia [13]. Ces mécanismes peuvent conduire à la formation de composés thiosulfonés (R-SO 2 SH) capables de réactions de transsulfuration, spontanées et non enzymatiques, avec des composés sulfiniques (R-SO 2 H) ou des anions thiophiles (SO 3 2-, CN -) ([6], [7]). Les composés de ce type dotés d'une fonction métabolique sont le plus souvent aminés en plus d'être soufrés. Cette étude met en évidence leur présence dans les tissus de R. pachyptila. Les acides aminés libres ont été extraits par l'eau ou l'éthanol à 80% (l ml pour 5mg de tissus) pendant quelques minutes dans une cuve à ultra-sons. Après centrifugation ou filtration, 50µL de solution suffisent à l'analyse des acides aminés au moyen d'un analyseur automatique (dans le cas de l'extraction alcoolique, l'alcool est évaporé et remplacé par de l'eau).

MATÉRIEL ET MÉTHODES

Plusieurs tests colorés permettent de caractériser les différentes familles de composés soufrés [7]. Parmi eux, la réaction «iodoplatinique» [START_REF] Greenstein | Chemistry of the amino acids[END_REF] a été appliquée aux extraits chromatographiés sur papier (phase supérieure butanol, acide acétique, eau, 5/1/4). Ce test permet, en particulier, de distinguer les composés sulfiniques et les composés thiosulfonés des composés sulfonés (R-SO 3 H).

Les composés soufrés acides, mal séparés dans les conditions de l'analyse standard des acides aminés au moyen d'un analyseur automatique (pH du premier tampon égal à 3,6), ont été étudiés en utilisant la méthode préconisée par De Marco et coll. [8]. Cette méthode permet de séparer convenablement un certain nombre de composés oxydés dérivés de la cystéine et de caractériser par des réactions spécifiques ceux qui seraient confondus.

EXPLICATIONS DE LA PLANCHE

Chromatographie des composés aminés soufrés extraits des tissus sous forme libre. Éluant: acide citrique 0,1M NaCI 0,2M,30°C, 60ml/mn. Réactif à la ninhydrine: 30ml/mn. Résine Beckman W2, 37 cm. Indice de coloration des composés par rapport à l'acide cystéique (mesuré à 570nm) : taurine (TAU), 0,18; hypotaurine (HYP), 0,25; thiotaurine (THIOT), 0,5. A. Branchie (partie rose). La réaction avec CN-est sans effet sur l'importance du premier pic, ce qui prouve l'absence de composé thiosulfoné. B. Trophosome. L'hypotaurine est absente. C. Trophosome après réaction avec CN -. La quantité d'hypotaurine formée correspond à la disparition d'une quantité égale de thiotaurine.

Chromatography of sulfur-containing amino compounds from tissue extracts (free form). Eluant:

citric acid 0.1 M-NaCI 0.2 M, 30°C, 60 ml/mn. Ninhydrine reagent: 30 ml/mn. Beckman W2 resin, 37 cm. Color constant at 570 nm (taking 1 as the value for cysteic acid): taurine (TAU), 0.18: hypotaurine (HYP), 0.25; thiotaurine (THIDT), 0.5. A. Plume tentacular lamellae. The first peak is unaffected by cyanolysis in accordance with the absence of thiosulfonic compounds. B. Trophosome.

Hypotaurine is absent. C. after cyanolysis. The quantity of created hypotaurine is in good

accordance with an equal quantity of missing thiotaurine.

Dans ces conditions l'hypotaurine (NH2C2H4-S02H) est facilement séparée de la taurine (R-S03H), mais par contre la thiotaurine (R-S02SH), l'homothiotaurine, l'homotaurine et la Ssulfocystéamine forment un pic confondu avec celui de la taurine.

En transformant quantitativement les composés thiosulfonés en leurs homologues sulfiniques (par réaction avec les ions cyanure), il est possible de déduire la part que chacun représentait dans le pic confondu. Le rapport des absorbances à 440 et 570nm révélerait la présence éventuelle de Ssulfocystéamine dans le pic restant après réaction avec CN -.

Par ailleurs, l'analyse de la fraction protéique des tissus a été effectuée après hydrolyse acide des échantillons.

RÉSULTATS. -L'analyse de la fraction libre montre la présence d'un composé 5 à 15 fois plus concentré que l'acide aminé le plus abondant (acide glutamique) et dont le volume de rétention correspond, dans les conditions d'analyse standard, à celui de la taurine. Ce composé représente 50 à 75 %de la totalité des acides aminés libres détectés (tableau).

Dans ces conditions d'analyse, la thiotaurine et la taurine sont confondues en un pic précédé de 1mn par celui de l'hypotaurine. Le temps de rétention de l'hypotaurine variant considérablement en fonction du pH leur séparation n'est pas toujours assurée.

La présence de ce composé, remarquable par son abondance, a également été observée par Felbeck (comm. pers.).

La réaction iodoplatinique appliquée aux fractions libres extraites des tissus est positive et montre qu'il ne s'agit pas de taurine mais vraisemblablement de thiotaurine et/ou d'hypotaurine pour l'essentiel.

L'observation (fig.

) des chromatogrammes obtenus suivant la méthode de De Marco et coll. montre clairement que le composé aminé soufré précédemment détecté apparaît sous la forme d'hypotaurine au niveau de la branchie et sous la forme de thiotaurine dans le trophosome.

Moins d'un quart existe sous la forme de taurine. Une partie de la taurine peut provenir d'une légère oxydation des échantillons pendant leur conservation et leur préparation.

DISCUSSION. -Selon Arp et Childress [3], le liquide coelomique présent au niveau du trophosome contient de l'hémoglobine. La forme thiosulfonée qui prédomine de manière quasi totale dans le trophosome peut être interprétée comme la forme résultant du transfert du soufre réduit entre. la protéine (hémoglobine) et les cellules contenant les bactéries.

Au niveau de la branchie, lieu de fixation des sulfures par la protéine du sang, la forme sulfinique serait inactive. Son action n'entrerait en jeu qu'au débouché du sang dans le trophosome. Là l'hypotaurine, en se chargeant du soufre libéré de sa liaison avec la protéine, se transformerait en thiotaurine.

  . -Les portions d'organisme proviennent d'un spécimen prélevé et congelé en mars 1984 lors de la campagne Biocyarise (plongée 37, Parigo, 2630 m, dorsale du Pacifique oriental vers 13°N). Les prélèvements de lamelles branchiales et de trophosome ont été lyophilisés.