Amaury Habrard
email: amaury.habrard@lif.univ-mrs.fr

Jose Oncina
email: oncina@dlsi.ua.es

Learning Multiplicity Tree Automata

Keywords: multiplicity tree automata, recognizable tree series, learning from equivalence and membership queries

In this paper, we present a theoretical approach for the problem of learning multiplicity tree automata. These automata allows one to define functions which compute a number for each tree. They can be seen as a strict generalization of stochastic tree automata since they allow to define functions over any field K. A multiplicity automaton admits a support which is a non deterministic automaton. From a grammatical inference point of view, this paper presents a contribution which is original due to the combination of two important aspects. This is the first time, as far as we now, that a learning method focuses on non deterministic tree automata which computes functions over a field. The algorithm proposed in this paper stands in Angluin's exact model where a learner is allowed to use membership and equivalence queries. We show that this algorithm is polynomial in time in function of the size of the representation.

Introduction

Trees are natural candidates for modeling a hierarchy in data, and for example they are particularly relevant to model a web page. Recently, due to the potential applications in the web, a lot of machine learning approaches devoted to trees have been proposed. From a grammatical inference standpoint, the natural objects for dealing with tree-structured data are tree automata and tree languages [START_REF] Gécseg | Tree Automata[END_REF][START_REF] Comon | Tree Automata Techniques and Applications[END_REF]. These objects are natural extensions of finite automata on strings, except that the alphabet is constituted of functional symbols representing labels of tree nodes. Several learning algorithms has been proposed in the literature for learning tree automata. Among them we can cite those of Knuutila et al. [START_REF] Knuutila | Inference of tree languages from a finite sample: an algebraic approach[END_REF], Garcia et al. [START_REF] Garcia | Inference of recognizable tree sets[END_REF] and Kosala et al. [START_REF] Kosala | Information extraction from web documents based on local unranked tree automaton inference[END_REF] for dealing with an unranked alphabet. Besombes et al. [START_REF] Besombes | Learning tree languages from positive examples and membership queries[END_REF] have studied the learning of regular tree languages using positive examples and membership queries. Carme et al. [START_REF] Carme | Interactive learning of node selecting tree transducer[END_REF] have proposed to learn specific tree transducers for information extraction applications. In the probabilistic case, we can cite Carrasco et al. [START_REF] Carrasco | Stochastic inference of regular tree languages[END_REF] and Rico et al. [START_REF] Rico-Juan | Probabilistic k-testable tree-languages[END_REF]. An important remark has to be made here: In general, these approaches have focused on learning deterministic models which may imply the construction of models with a high complexity.

In this paper, we propose to study the learnability of multiplicity tree automata. Informally, a multiplicity tree automaton defines a function allowing one to associate to any tree a value in a field K (for example IR or Q). We call such an automaton a K-multiplicity tree automaton. For example, stochastic tree automata are then particular cases of multiplicity automata where K = [0, 1]. However, multiplicity automata do not compute stochastic distribution in general. For example, you can define multiplicity tree automata that represent a function which computes the number of occurrences of a given symbol in a tree. There exists a notion of support for a multiplicity automaton which corresponds to a non deterministic finite tree automaton. This non determinism characterize a greater expressiveness than deterministic models. Another crucial point has to be made here. For defining a multiplicity automaton, we define functions which compute the value of a subtree when a transition is applied to analyse the subtree. In the case of a multiplicity automaton these functions are multilinear (e.g. for symbol of arity p we define a p-linear function) and offer a good expressiveness for defining the global function computed by a multiplicity automaton. In fact, the function computed by multiplicity automata are usually referred as recognizable formal power series on trees [START_REF] Berstel | Recognizable formal power series on trees[END_REF][START_REF] Esik | Formal tree series[END_REF].

Hence, this article combines two main improvements for learning tree automata. The method we present allows us to learn tree automata with a non deterministic support that compute functions from a set of trees to a field K. This is, as far as we know, the first time that a learning method is proposed for multiplicity tree automata. We think that this research direction can be very promising due to the potential applications notably in information extraction from the web.

In the case of strings, some learning methods of multiplicity automata have already been published: [START_REF] Beimel | Learning functions represented as multiplicity automata[END_REF]. But, there exists no similar work for trees. The adaptation to trees is not trivial since the use of multilinear mappings for transitions are a real improvement in comparison with the string case.

We propose a learning algorithm for multiplicity tree automata which stands in Angluin's exact learning model [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF]. In this framework, the learning algorithm is allowed to ask queries to an oracle. The algorithm can ask equivalence queries to know if he found the correct hypothesis. In the opposite case, a counterexample is returned by the oracle. Membership queries are also available to have information about one example. The algorithm we present runs in polynomial time in the size of the target and needs a number of queries also polynomial in the size of the target. This algorithm exploits a result showing that the number of states of a minimal multiplicity tree automaton is exactly the rank (which is finite) of the Hankel matrix of the power tree series it represents. The underlying principle of our approach is to find a hierarchical basis which allows to generate all the element of the target multiplicity automaton. This basis is then used for building the tree automaton which is minimal since a basis is a minimal representation by definition.

The paper is organised as follows. In Section 2, we introduce some background about recognizable formal tree series and multiplicity automata. The Hankel Matrix associated to a recognizable series is defined in Section 3. In this section, we also characterize recognizable tree series in terms of the dimension of their associated Hankel Matrix. The learning algorithm is presented in Section 4.

Background

To begin with, we introduce the alphabet for defining trees and the concept of free magma which is an equivalent to the free monoid Σ * over strings.

Following [START_REF] Berstel | Recognizable formal power series on trees[END_REF], Let F be a finite set of function symbols, that is a ranked alphabet

F = F 0 ∪ F 1 ∪ • • • ∪ F p .
The elements in F p are the function symbols of arity p. We denote by M (F ) the free magma generated by F . The elements in M (F ) are called trees. If t is a tree and t ∈ F 0 then there exists an integer p ≥ 0, a symbol function f ∈ F p , and trees t 1 , . . . , t p such that t = f (t 1 , . . . , t p ). Definition 1. Let K be a commutative field. A formal power tree series (TS) on M (F ) with coefficients in K is a mapping

S : M (F ) → K
The set of all TS on M (F ) with coefficients in K is denoted by K{{F }}.

Recognizable Formal Power Tree Series (RTS)

Let V be a finite dimensional vector space over the field K, let dim(V ) be the dimension of V and let x ∈ V , we denote by [x] i the ith coordinate of the vector x. In the following, the vector V will represent intermediate values used in a non deterministic analysis of a tree by a multiplicity automaton. Each dimension of V will correspond to the result associated to a state of the multiplicity tree automaton.

We denote by L(V p ; V ) the set of p-linear mappings from V p to V . Let L = ∪ p≥0 L(V p ; V ). The vector space V is an L-magma with L(V p ; V ) as the function set with arity p. Thus any mapping µ :

F → L which maps F p into L(V p ; V ) converts V into an F -magma.
Intuitively, µ will correspond to a transition in the automaton that defines the next states used during the analysis of a tree. Definition 2. A linear representation of the free magma M (F ) is a couple (V, µ), where V is a finite dimensional vector space over K, and where µ :

F → L maps F p into L(V p ; V ) for each p ≥ 0. Thus for each f ∈ F p , µ(f ) : V p → V is p-linear, and since M (F ) is free, µ extends uniquely to a morphism µ : M (F ) → V by the formula µ(f (t 1 , . . . , t p )) = µ(f )(µ(t 1 ), . . . , µ(t p )).
(1) Definition 3. let S be a TS on M (F ), then S is a recognizable TS (RTS) if there exists a triple (V, µ, λ), where (V, µ) is a linear representation of M (F ), and λ : V → K is a linear form, such that S(t) = λ(µ(t)) for all t in M (F ).

(V, µ, λ) is called a Multiplicity Tree Automaton (MTA) and we say that (V, µ, λ) is a representation of S. Intuitively, if we try to make the link between these automata and classical automata in language theory, the states of a multiplicity automaton correspond to a basis of V . The transitions are defined by µ and the final states by λ. According to this definition, multiplicity tree automata can be seen as an extension of bottom-up tree automata.

In order to illustrate these objects, we provide an example introduced in [START_REF] Berstel | Recognizable formal power series on trees[END_REF]. We consider a recognizable tree series S (i.e. a multiplicity tree automaton) computing the number of occurrences of a symbol f in a tree.

We define a MTA (V, λ, µ) where V = Q 2 and (e 1 , e 2 ) a canonical basis of V (i.e. e 1 = (1, 0) and e 2 = (1, 0)). We define µ and λ such that:

∀g ∈ F q , g = f : µ(g)(e i1 , . . . , e iq ) =    e 1 if e i1 = • • • = e iq =
f ∈ F p : µ(f )(e i1 , . . . , e ip ) =    e 1 + e 2 if e i1 = • • • = e ip = e 1 e 2 if there exists exactly one e ij s.t. e ij = e 2 0 otherwise ∀a ∈ F 0 : µ(a) =    e 1 if a = f e 1 + e 2 if a = f ∈ F 0 0 otherwise
Finally λ(e 1 ) = 0 and λ(e 2 ) = 1.

It can be shown that µ(t) = e 1 + S(t)e 2 , then λ(µ(t)) = S(t). Let's see an example of a computation of S(t). Consider t = f (a, g(f (a, a))) over the ranked alphabet

F 0 = {a}, F 1 = {g(•)} F 2 = { f (•, •) }. µ(f (a, g(f (a, a)))) = µ(f )(µ(a), µ(g(f (a, a)))) = µ(f )(e 1 , µ(g)(µ(f (a, a)))) = µ(f )(e 1 , µ(g)(µ(f )(µ(a), µ(a)))) = µ(f )(e 1 , µ(g)(µ(f )(e 1 , e 1 ))) = µ(f )(e 1 , µ(g)(e 1 + e 2 )) = µ(f )(e 1 , µ(g)(e 1 )) + µ(f )(e 1 , µ(g)(e 2 )) = µ(f )(e 1 , µ(g)(e 1 )) + µ(f )(e 1 , µ(g)(e 2 )) = µ(f )(e 1 , e 1 ) + µ(f )(e 1 , e 2 ) = e 1 + e 2 + e 2 = e 1 + 2e 2 Hence λ(µ(t)) = 2.

Contexts

We introduce contexts which allow us to define an equivalent notion of concatenation for trees. Let $ be a zero arity function symbol not in F 0 , a context is an element of the free-magma M (F ∪ {$}) such that the symbol $ appears exactly one time. We denote by M ($, F ) such set.

Let c = $ be a context, then, there exists two integers p and n (n ≤ p), a symbol function f ∈ F p , trees t 1 , . . . , t p-1 and a context c such that c = f (t 1 , . . . , t n-1 , c , t n , . . . , t p-1 ). Let t be a tree and let c be a context, t • c denotes the tree obtained by substituting the symbol $ in the context c by the tree t.

The µ function can be extended to work over contexts (µ : M ($, F ) → L(V ; V )) recursively on the following way:

µ($)(x) = x µ(f (t1, . . . , tn-1, c, tn, . . . , tp))(x) = µ(f )(µ(t1), . . . , µ(tn-1), µ(c)(x), µ(tn), . . . , µ(tp))
It is easy to see that µ(t • c) = µ(c)(µ(t)). Let t be a tree we define Suf(t) = {c : ∃t , t • c = t}.

Multilinear Functions

Let V = K d , let f : V p → V be a p-linear function, such that f (x 1 , . . . x p ) = y then f can be expressed as:

[y] i = 1≤j i ≤d i=1,...,p f i,j1,...,jp [x 1 ] j1 . . . [x p ] jp ( 2
)
where f i,j1,...,jp are the d p+1 parameters that define the function f . Note that in order to fully specify an MTA (V, µ, λ) (V = K r ), we need:

d parameters to specify λ i:|Fi| =0 |F i |d i+1 parameters to specify the multilinear functions.

Let (V, µ, λ) a MTA, as λ : V → K is a linear function it can be represented as a vector (λ = (λ 1 , . . . , λ d )).

In the same way, when applied over contexts, µ gives a linear function over vectors in V (µ : M ($, F ) → L(V ; V )), this linear function can be represented as a d × d matrix. For example, Using this notation, the equation λ(µ(t

• c)) = λ(µ(c)(µ(t))) can be written clearly as µ(t • c)λ = µ(t)µ(c)λ.

Hankel Matrix and Recognizable Tree Series

The Hankel Matrix

Informally, the Hankel Matrix of a TS S is an infinite matrix that represents all the possible values for S. The rows of the matrix are indexed by trees and the columns by contexts. A value in this matrix corresponds to the value in the series S for the tree built by the concatenation of the tree on the row and the context on the column. An example is drawn on Figure 1. Let t be a tree, a row of the Hankel Matrix is defined by

Definition 4. The Hankel matrix (HM ) of a TS S ∈ K{{F }} (HM (S)) is an infinite matrix

H : M (F ) × M ($, F ) → K such that H t,c = S(t • c) ∀t ∈ M (F ), c ∈ M ($, F ). $ f ($, a) f ($, b) f (a, $) • • • a S(a) S(f (a, a)) S(f (a, b)) S(f (a, a)) • • • b S(b) S(f (b, a)) S(f (b, b)) S(f (a, b)) • • • f (a, a) S(f (a, a)) S(f (f (a, a), a)) S(f (f (a, a), b)) S(f (a, f (a, a))) • • • . . . . . . . . . . . . . . . . . .
H t , then H t (c) = H t,c . Lemma 1. Let (V, µ, λ) an MTA of a TS S ∈ K{{F }}, let H the Hankel Matrix of S, then rank(H) ≤ dim(V ). Proof. Let d = dim(V ), define a ∞ × d matrix R such that R(t, i) = [µ(t)]

Recognizable Tree Series

We are going to show that a TS is recognizable if an only if its HM has a finite rank. For this purpose, we will introduce the notion of hierarchical generator and show that this generator allows us to generate all the entries of the HM. Given any HM H, note that the previous definition does not imply that any HG for H should be a basis for the HM. A HG can be easily extracted from an HM following Algorithm 1 HG. In order to eliminate any ambiguity, we should fix an arbitrary order on trees, any order can be chosen.

Algorithm 2 describes the algorithm MTAB to extract an MTA from an HM. Although in the present version it works on infinite HM (then it is not really an algorithm) we are going to use it later with finite size portions of the HM. Now we present a series of lemma necessary to show that the multiplicity automaton extracted by algorithm MTAB represents the TS defined by its HM. Let δ ij representing a function that returns always 0 except when i = j it returns 1.

Lemma 2. Let H be the Hankel matrix of a RTS

S ∈ {{K}}. Let (V, µ, λ) = MTAB(H), then [µ(e i )] j = δ ij .
Proof. Note that as e i are elements of the generator and let e i = f (e i1 , . . . , e ip ), using the algorithm, f k,i1,...,ip = δ ik . We prove the result by induction in the height of the trees in the generator. Let e i ∈ F 0 , then p = 0 and f k = δ ik , in such case, [µ(e i )] j = f j = δ ij as required.

Proof. Then, S(t) = µ(t)λ.

ˆµ(f (ej 1 , . . . , ej p )) ˜i = ˆ(µf )(µ(ej 1 ), . . . µ(ej p )) ˜i by Equation 1 = X 1≤k i ≤p f i,k 1 ,...,kp [µ(ej 1 ) k 1 ] . . . [µ(ej p ) kp ] b yE q u a t i o n2 = X 1≤k i ≤p f i,k 1 ,...,kp δ j 1 ,k 1 . . .
Proof. Let B = {e 1 , . . . , e d } = HG(H). Note that for f ∈ F 0 H f (c) = d i=1 f i H ei (c) by Algorithm MTAB = d i=1 f i µ(e i )µ(c)λ by Lemma 4 = d i=1 f i d j=1 [µ(e i )] j [µ(c)λ] j = d i=1 f i d j=1 δ ij [µ(c)λ] j by Lemma 2 = d i=1 f i [µ(c)λ] i = d i=1 µ(f ) i [µ(c)λ] i by Equation 2 = µ(f )µ(c)λ = µ(f • c)λ
And we have what we wanted because for any tree t, it exists an f ∈ F 0 and a context c such that t = a • c . Then,

S(t) = H f (c) = µ(f • c)λ = µ(t)λ.
Corollary 1. Let H be the Hankel Matrix of a RTS S ∈ {{K}}. Then, the MTA (V, µ, λ) that represents S with a smaller dim(V ) satisfies that rank(H) = dim(V ).

Proof. By Lemma 1 we have that rank(H) ≤ dim(V ), and by Theorem 1 we have shown that, using algorithm MTAB, we can build a representation (V, µ, λ) consistent with H such that dim(V ) ≤ rank(H). Proof. Sketch. A similar technique used in the proof of Theorem 1 allows to prove the result. Note that since some proofs of lemmas needed to show Theorem 1 use induction over trees and contexts, C should be suffix complete in order to guarantee its correctness. Lemma 6. Let M = (C, T, Ĥ) be a closed table with C suffix complete and let

(V, µ, λ) = MTAB(M ). Consider t ∈ T and c ∈ C such that µ(t • c)λ = Ĥt,c , we can decompose t•c = f •c where f ∈ F 0 . Let M = (T , C , Ĥ ) = closed((T, C ∪ Suf(f • c ), Ĥ)); then µ (f • c )λ = Ĥ f,c . Moreover, rank( Ĥ ) > rank( Ĥ). Proof. Sketch. A direct application of Lemma 5 ensures that µ (f • c )λ = Ĥ f,c .
On the other hand, all the trees of the HG(M) are linearly independent. By adding new contexts in C, those trees remain linearly independent and then they will be a part of HG.

Let A = MTAB(M ) and A = MTAB(M ). Clearly all the trees in HG(M ) are also in HG(M ) but new trees should appear in HG(M ), otherwise, by construction, A = A and this is impossible because µ

(f • c )λ = µ (f • c )λ.
Thus, rank( Ĥ ) > rank( Ĥ). generator HG of this MTA has strictly more trees than the previous one. As the number of trees in HG can not be bigger than the rank of the HM for the target MTA, then the process should finish and gives the correct hypothesis. Now, looking at the time complexity, since all the steps of the algorithm can be done in polynomial time with respect to the size of the target MTA (linear independence of a set of vector, Algorithms HG, MTAB, close and consistent), it is evident that algorithm LearnMTA runs in polynomial time.

With respect to the queries, it is easy to see that the number of Equivalence Queries can no be larger than r (at most one for each tree added to HG).

Moreover, note that the all the results of the membership queries are stored in the equivalence table or were used to calculate the λ vector (of size r). It is easy to see that |T | = i:Fi =0 |F i |r i and that |C| ≤ r.m since for a tree t we can define no more than |t| contexts. Reminding that |A| = i:Fi =0 |F i |r i+1 + r then, the number of Membership Queries is lower that |T ||C| + r ≤ |A|m.

Conclusion

In this paper we proposed a learning algorithm for identifying multiplicity tree automata that define functions associating a number to any tree. We showed that the size of a minimal multiplicity tree automaton is function of the finite rank of its Hankel matrix. Our algorithm is able to identify the minimal automata in polynomial time in the exact learning model of Angluin. The originality of our approach is to find a hierarchical basis that permits to generate all the elements of the target series.

We think that multiplicity tree automata can offer a wide range of potential applications, especially for extraction information from the web. We showed that this class of automata is identifiable and our perspective is to find efficient approaches in other learning paradigms. We have begin to study a possible ex-tension of the approach presented in [START_REF] Denis | Learning rational stochastic languages[END_REF][START_REF] Denis | Rational stochastic language[END_REF], which allows to learn stochastic languages on strings represented by multiplicity automata, to trees.

Fig. 1 :

 1 Fig. 1: An example of the Hankel Matrix of a tree series S.

  i and define a d × ∞ matrix C such that C(i, c) = [µ(c)λ] i . Clearly, H = RC, but as rank(C) ≤ d and rank(R) ≤ d, then rank(H) ≤ d.

Lemma 3 .

 3 Now let e i = f (e i1 , . . . , e ip ) and suppose, by induction, that [µ(e ij )] k = δ ij k , j = 1, . . . , p. Then, [µ(e i )] j = [µ(f (e i1 , . . . , e ip ))] j = [µ(f )(µ(e i1 ), . . . , µ(e ip ))] j by Equation1=j l f j,j1,...,jp [µ(e i1 )] j1 . . . [µ(e ip )] jp µ(f ) is a multilinear function = j l f j,j1,...,jp δ i1j1 . . . δ ipjp induction step = f j,i1,...,ip = δ ij by Algorithm MTAB Note that as a consequence of the Lemma 2, µ(e i )λ = H(e i ), i = 1, . . . , r. Let H be the HM of a RTS S ∈ {{K}}. Let (V, µ, λ) = MTAB(H). Let B = {e 1 , . . . , e d } = HG(H). then, µ(f (e j1 , . . . , e jp )) = r j=1 f j,j1,...,jp µ(e j ).

δ jp,kp by Lemma 2 =Lemma 4 . 3 =Theorem 1 .

 2431 fi,j 1 ,...,jp Let H be the HM of a RTS S ∈ {{K}}. Let (V, µ, λ) = MTAB(H). Let B = {e 1 , . . . , e d } = HG(H). Then, for all context c H ei (c) = µ(e i )µ(c)λ. Proof. By induction, the base case (c = $) is evident since µ(e i )λ = H ei ($). Let us show that H f (ej 1 ,...,ej p ) (c) = µ(f (e j1 , . . . , e jp ) • c)λ. H f (ej 1 ,...,ej p ) (c) = d j=1 f j,j1,...,jp H ej (c) by algorithm MTAB = d j=1 f j,j1,...,jp µ(e j )µ(c)λ by induction step = µ(f (e j1 , . . . , e jp ))µ(c)λ by Lemma µ(f (e j1 , . . . , e jp ) • c)λ Let H be the HM of a RTS S ∈ {{K}}. Let (V, µ, λ) = MTAB(H).

  e 1 e 2 if there exists exactly one e ij s.t. e ij = e 2 0 otherwise

  ej ) 2. ∀e i = f (e i1 , . . . , e ip ) ∈ B then e ij ∈ B, j = 1, . . . , p. 3. There is no tree t = f (e i1 , . . . , e ip ), t ∈ B, e ij ∈ B, j = 1, . . . , d, such that t is LI of B. {}, i = 1 2. search for the smaller tree ei = f (ei 1 , . . . , ei p ) such that ei j ∈ B, j = 1, . . . , p and He i is not a linear combination of {He 1 , . . . , He i-1 }. 3. if not found then halt. if found then add it to B and increment i. 4. go to 2 Algo. 1: Algorithm HG to obtain a Hierarchical Generator from a Hankel Matrix. Obtain a hierarchical generator e1, . . . , e d from H. 2. Set dim(V ) = d. 3. Set λi = H(ei), i = 1, . . . , d 4. ∀p, ∀f ∈ Fp, ∀i1, . . . , ip, 1 ≤ ij ≤ d, let αi such that: H f (e i 1 ,...,e ip ) = P r i=1 αiHe i . Then fix fi,i 1 ,...,ip = αi. Algo. 2: Algorithm MTAB that builds representation from a Hankel Matrix.

	Algorithm HG(H)
	input: Hankel matrix H
	output: a hierarchical generator B
	1. initialize B = Algorithm MTAB(H)
	input: a Hankel matrix H
	output: a representation (V, µ, λ)
	1.

Definition 5. Let H be an HM, we say that

B = {e 1 , . . . , e d } is a hierarchical generator (HG) in H if 1. each e i ∈ B is linearly independent (LI) of the rest ( α j ∈ K : H ei = 1≤j≤d, i =j α i H

  In the same way as Lemma 6, it can be shown that the counterexample acts in a similar way as when a non consistency is found in the ET. In any case, after the consistent call (after step 4 of LearnMTA) a new MTA compatible with all the data in the ET is obtained. As shown in Lemma 6, the hierarchical T = {}, C = {}, A = an empty MTA, M = (T, C, Ĥ) an empty ET.2. Ask an equivalence query EQ(A).

	Algorithm LearnMTA(EQ, MS)
	input: an equivalence oracle EQ
	input: a membership oracle MS
	output: a MTA A
	1. Initialize: If the answer is YES then halt with output A.
	Otherwise the answer is NO and z is a counterexample.
	3. Add Suf(z) to C.
	4. M ← consistent(M )
	5. A ← MTAB(M )
	6. go to 2
	Algo. 5: inference algorithm LearnMTA

Theorem 2. Let MQ and EQ respectively membership and equivalence oracles of a RTS S with an associated Hankel matrix H. Let r = rank(H) LearnMTA(M Q, EQ) returns the minimal representation compatible with the target in polynomial time making at most r equivalence queries and |A|m membership queries, where m is the length of the longest counterexample returned by the Equivalence Queries.

Proof.

This work was supported in part by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002-506778. This publication only reflects the authors' views. This work is part of the ARA marmota french projet. This work was done when the second author was visiting the LIF Marseille.

Corollary 2. Let H be the HM of a RTS S ∈ {{K}}, HG(H) is a basis, i.e. HG(H) can generate all the Hankel Matrix H.

Corollary 3. Let H be the Hankel Matrix of a RTS S ∈ {{K}}. The MTA (V, µ, λ) = MTAB(H) is the representation of S that minimizes dim(V ).

Inference algorithm

The learning model we use is the exact learning model of Angluin [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF]. Let f be a target function. At each step of the inference procedure, the learning algorithm can propose an hypothesis function h by making an equivalence query (EQ) to an oracle. This oracle answers YES if h is equivalent to f on all input assignments. In this case the target is identified, the learning algorithm succeeds and halts.

Otherwise, the answer to the equivalence query is NO and the algorithm receives a counterexample, that is an assignment z such that f (z) = h(z). Moreover, the learning algorithm is also allowed to query an oracle for the value of the function f on a particular assignment z by making a membership query (MQ) on z. The response to such a query is the value f (z). We say that the learner identifies a class of functions F , if, for every function f ∈ F , the learner outputs an hypothesis h that is equivalent to f and does so in polynomial time in the "size" of a shortest representation of f and the length of the longest counterexample.

To begin with, we define an experimental table which corresponds to a submatrix of the Hankel Matrix of a the target series S.

In the following, we will maintain this table filled such that Ĥt,c = S(t • c). Next definition will allows us to apply algorithm MTAB to any Experiment Table .   Definition 7. Let M = (T, C, Ĥ) be an ET and let B = HG( Ĥ). M is closed if ∀p, ∀f ∈ F p , ∀e i1 , . . . , e ip ∈ B, f (e i1 , . . . , e ip ) ∈ T Algorithm 3 close is able to close any ET. Note that any call to close will include all the symbols in F 0 .

The following definition will ensure that any extracted MTA by MTAB is consistent with the data in the Experiment Table.