{'fraction_non_alphanumeric': 0.05139120870167434, 'fraction_numerical': 0.014237992422699311, 'mean_word_length': 3.781359563693027, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 32, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Complexity of Equivalence and Learning for Multiplicity Tree Automata

We consider the complexity of equivalence and learning for multiplicity tree automata, i.e., weighted tree automata over a field. We first show that the equivalence problem is logspace equivalent to polynomial identity testing, the complexity of which is a longstanding open problem. Secondly, we derive lower bounds on the number of queries needed to learn multiplicity tree automata in Angluin's exact learning model, over both arbitrary and fixed fields. Habrard and Oncina (2006) give an exact learning algorithm for multiplicity tree automata, in which the number of queries is proportional to the size of the target automaton and the size of a largest counterexample, represented as a tree, that is returned by the Teacher. However, the smallest tree-counterexample may be exponential in the size of the target automaton. Thus the above algorithm does not run in time polynomial in the size of the target automaton, and has query complexity exponential in the lower bound. Assuming a Teacher that returns minimal DAG representations of counterexamples, we give a new exact learning algorithm whose query complexity is quadratic in the target automaton size, almost matching the lower bound, and improving the best previously-known algorithm by an exponential factor.


Introduction
Trees are a natural model of structured data, including syntactic structures in natural language processing, web information extraction, and XML data on the web. Many of those applications require representing functions from trees into the real numbers. A broad class of such functions can be defined by multiplicity tree automata, which generalise probabilistic tree automata.
Multiplicity tree automata were introduced by Berstel and Reutenauer (1982) under the terminology of linear representations of tree series. They generalise classical finite tree automata by having transitions labelled by values in a field. They also generalise multiplicity word automata, introduced by Schützenberger (1961), since words are a special case of trees. Multiplicity tree automata define many natural structural properties of trees and can be used to model probabilistic processes running on trees.
Multiplicity word and tree automata have been applied to a wide variety of learning problems, including speech recognition, image processing, character recognition, and grammatical inference; see the paper of Balle and Mohri (2012) for references. A variety of methods have been employed for learning such automata, including matrix completion and spectral methods (Balle and Mohri, 2012; and principal components analysis (Bailly et al., 2009).
A fundamental problem concerning multiplicity tree automata is equivalence: given two automata, do they define the same function on trees. Seidl (1990) proved that equivalence of multiplicity tree automata is decidable in polynomial time assuming unit-cost arithmetic, and in randomised polynomial time in the usual bit-cost model. No finer analysis of the complexity of this problem exists to date. In contrast, the complexity of equivalence for classical nondeterministic word and tree automata has been completely characterised: PSPACE-complete over words (Aho et al., 1974) and EXPTIME-complete over trees (Seidl, 1990).
Our first contribution, in Section 3, is to show that the equivalence problem for multiplicity tree automata is logspace equivalent to polynomial identity testing, i.e., the problem of deciding whether a polynomial given as an arithmetic circuit is zero. The latter is known to be solvable in randomised polynomial time (DeMillo and Lipton, 1978;Schwartz, 1980;Zippel, 1979), whereas solving it in deterministic polynomial time is a well-studied and longstanding open problem (see Arora and Barak, 2009).
Equivalence is closely connected to the problem of learning in the exact learning model of Angluin (1988). In this model, a Learner actively collects information about the target function from a Teacher through membership queries, which ask for the value of the function on a specific input, and equivalence queries, which suggest a hypothesis to which the Teacher provides a counterexample if one exists. A class of functions C is exactly learnable if there exists an exact learning algorithm such that for any function f ∈ C , the Learner identifies f using polynomially many membership and equivalence queries in the size of a shortest representation of f and the size of a largest counterexample returned by the Teacher during the execution of the algorithm. The exact learning model is an important theoretical model of the learning process. It is well-known that learnability in the exact learning model also implies learnability in the PAC model with membership queries (Valiant, 1985).
One of the earliest results about the exact learning model was the proof of Angluin (1987) that deterministic finite automata are learnable. This result was generalised by Drewes and Högberg (2003) to show exact learnability of deterministic finite tree automata, generalising also a result of Sakakibara (1990) on the exact learnability of context-free grammars from structural data.
Exact learnability of multiplicity automata has also been extensively studied. Beimel et al. (2000) show that multiplicity word automata can be learned efficiently, and apply this to learn various classes of DNF formulae and polynomials. These results were generalised by Klivans and Shpilka (2006) to show exact learnability of restricted algebraic branching programs and noncommutative set-multilinear arithmetic formulae. Bisht et al. (2006) give an almost tight (up to a log factor) lower bound for the number of queries made by any exact learning algorithm for the class of multiplicity word automata. Finally, Habrard and Oncina (2006) give an algorithm for learning multiplicity tree automata in the exact model.
Our first contribution on learning multiplicity tree automata, in Section 5, is to give lower bounds on the number of queries needed to learn multiplicity tree automata in the exact learning model, both for the case of an arbitrary and a fixed underlying field. The bound in the latter case is proportional to the automaton size for trees of a fixed maximal branching degree. To the best of our knowledge, these are the first lower bounds on the query complexity of exactly learning of multiplicity tree automata.
Consider a target multiplicity tree automaton whose minimal representation A has n states. The algorithm of Habrard and Oncina (2006) makes at most n equivalence queries and number of membership queries proportional to |A| · s, where |A| is the size of A and s is the size of a largest counterexample returned by the Teacher. Since this algorithm assumes that the Teacher returns counterexamples represented explicitly as trees, s can be exponential in |A|, even for a Teacher that returns counterexamples of minimal size (see Example 1). This observation reveals an exponential gap between the query complexity of the algorithm of Habrard and Oncina (2006) and our above-mentioned lower bound, which is only linear in |A|. Another consequence is that the worst-case time complexity of this algorithm is exponential in the size of the target automaton.
Given two inequivalent multiplicity tree automata with n states in total, the algorithm of Seidl (1990) produces a subtree-closed set of trees of cardinality at most n that contains a tree on which the automata differ. It follows that the counterexample contained in this set has at most n subtrees, and hence can be represented as a DAG with at most n vertices. Thus in the context of exact learning it is natural to consider a Teacher that can return succinctly represented counterexamples, i.e., trees represented as DAGs.
Tree automata that run on DAG representations of finite trees were first introduced by Charatonik (1999) as extensions of ordinary tree automata, and were further studied by Anantharaman et al. (2005). The automata considered by Charatonik (1999) and Anantharaman et al. (2005) run on fully-compressed DAGs. Fila and Anantharaman (2006) extended this definition by introducing tree automata that run on DAGs that may be partially compressed. In this paper, we employ the latter framework in the context of learning multiplicity automata.
In Section 4, we present a new exact learning algorithm for multiplicity tree automata that achieves the same bound in the number of equivalence queries as the algorithm of Habrard and Oncina (2006), while using number of membership queries quadratic in the target automaton size and linear in the counterexample size, even when counterexamples are given succinctly. Assuming that the Teacher provides minimal DAG representations of counterexamples, our algorithm therefore makes quadratically many queries in the target size. This is exponentially fewer queries than the best previously-known algorithm (Habrard and Oncina, 2006) and within a linear factor of the above-mentioned lower bound. Furthermore, our algorithm performs a quadratic number of arithmetic operations in the size of the target automaton, and can be implemented in randomised polynomial time in the Turing model.
Like the algorithm of Habrard and Oncina (2006), our algorithm constructs a Hankel matrix of the target automaton. However on receiving a counterexample tree z, the former algorithm adds a new column to the Hankel matrix for every suffix of z, while our algorithm adds (at most) one new row for each subtree of z. Crucially the number of suffixes may be exponential in the size of a DAG representation of z, whereas the number of subtrees is only linear in the size of a DAG representation.
An extended abstract (Marusic and Worrell, 2014) of this work appeared in the proceedings of MFCS 2014. The current paper contains full proofs of all results reported there, the formal definition of multiplicity tree automata running on DAGs, and a refined complexity analysis of the learning algorithm.

Preliminaries
Let N and N 0 denote the set of all positive and non-negative integers, respectively. Let n ∈ N. We write [n] for the set {1, 2, . . . , n} and I n for the identity matrix of order n. For every i ∈ [n], we write e i for the i th n-dimensional coordinate row vector.
For any matrix A, we write A i for its i th row, A j for its j th column, and A i,j for its (i, j) th entry. Given non-empty subsets I and J of the rows and columns of A, respectively, we write A I,J for the submatrix (A i,j ) i∈I,j∈J of A. For singletons, we write simply A i,J := A {i},J and A I,j := A I,{j} . Let n 1 , . . . , n k ∈ N, and let A be a matrix with n 1 · . . . · n k rows. For every Given a set V , we denote by V * the set of all finite ordered tuples of elements from V . For any subset S ⊆ V , the characteristic function of S (relative to V ) is the function χ S : V → {0, 1} such that χ S (x) = 1 if x ∈ S, and χ S (x) = 0 otherwise.

Kronecker Product
Let A be a matrix of dimension m 1 × n 1 and B a matrix of dimension m 2 × n 2 . The The Kronecker product is bilinear, associative, and has the following mixed-product property: For any matrices A, B, C, D such that products A · C and B · D are defined, it holds that (A ⊗ B) · (C ⊗ D) = (A · C) ⊗ (B · D).
Let k ∈ N and A 1 , . . . , A k be matrices such that for every l ∈ [k], A l has n l rows. It can easily be shown using induction on k that for every (i 1 , . . . , i k ) ∈ [n 1 ] × · · · × [n k ], it holds that We write k l=1 A l := A 1 ⊗ · · · ⊗ A k . For every k ∈ N 0 we define the k-fold Kronecker power of a matrix A, written as A ⊗k , inductively by A ⊗0 = I 1 and A ⊗k = A ⊗(k−1) ⊗ A for k ≥ 1.
Let k ∈ N 0 . For any matrices A, B of appropriate dimensions, we have For any matrices A 1 , . . . , A k and B 1 , . . . , B k where product A l ·B l is defined for every l ∈ [k], we have Equations (2) and (3) follow easily from the mixed-product property by induction on k.

Finite Trees
A ranked alphabet is a tuple (Σ, rk ) where Σ is a nonempty finite set of symbols and rk : Σ → N 0 is a function. Ranked alphabet (Σ, rk ) is often written Σ for short. For every k ∈ N 0 , we define the set of all k-ary symbols Σ k := rk −1 ({k}). If σ ∈ Σ k then we say that σ has rank (or arity) k. We say that Σ has rank m if m = max {rk (σ) : σ ∈ Σ}. The set of Σ-trees (trees for short), written as T Σ , is the smallest set T satisfying the following two conditions: (i) Σ 0 ⊆ T ; and (ii) if k ≥ 1, σ ∈ Σ k , t 1 , . . . , t k ∈ T then σ(t 1 , . . . , t k ) ∈ T . Given a Σ-tree t, a subtree of t is a Σ-tree consisting of a node in t and all of its descendants in t. The set of all subtrees of t is denoted by Sub(t).
Let Σ be a ranked alphabet and F be a field. A tree series over Σ with coefficients in F is a function f : T Σ → F. For every t ∈ T Σ , we call f (t) the coefficient of t in f . The set of all tree series over Σ with coefficients in F is denoted by F T Σ .
We define the tree series height, size, # σ ∈ Q T Σ where σ ∈ Σ, as follows: , respectively. For every n ∈ N 0 , we define the sets T <n Σ := {t ∈ T Σ : height (t) < n}, T n Σ := {t ∈ T Σ : height(t) = n}, and T ≤n Σ := T <n Σ ∪ T n Σ . Let ✷ be a nullary symbol not contained in Σ. The set C Σ of Σ-contexts (contexts for short) is the set of ({✷} ∪ Σ)-trees in which ✷ occurs exactly once. The concatenation of c ∈ C Σ and t ∈ T Σ∪ C Σ , written as c[t], is the tree obtained by substituting t for ✷ in c.
for every t ∈ T Σ and c ∈ C Σ .

Multiplicity Tree Automata
Let F be a field. An F-multiplicity tree automaton (F-MTA) is a quadruple A = (n, Σ, µ, γ) which consists of the dimension n ∈ N 0 representing the number of states, a ranked alphabet Σ, the tree representation µ = {µ(σ) : σ ∈ Σ} where for every symbol σ ∈ Σ, matrix µ(σ) ∈ F n rk(σ) ×n represents the transition matrix associated to σ, and the final weight vector γ ∈ F n×1 . The size of the automaton A, written as |A|, is defined as That is, the size of A is the total number of entries in all transition matrices and the final weight vector. 1 We extend the tree representation µ from Σ to T Σ by defining µ(σ(t 1 , . . . , t k )) := (µ(t 1 ) ⊗ · · · ⊗ µ(t k )) · µ(σ) for every σ ∈ Σ k and t 1 , . . . , t k ∈ T Σ . The tree series A ∈ F T Σ recognised by A is defined by A (t) = µ(t) · γ for every t ∈ T Σ . Note that a 0-dimensional automaton 1. We measure size assuming explicit rather than sparse representations of the transition matrices and final weight vector because minimal automata are only unique up to change of basis (see Theorem 4).
Then, E 1 and E 2 are two bases of the vector space F 1×n 1 n 2 . Therefore, P k is well-defined as an invertible matrix mapping basis E 1 to basis E 2 .
Essentially the same product construction as in the proof of the first part of the following proposition is given by Berstel and Reutenauer (1982, Proposition 5.1) in the language of linear representations of tree series rather than multiplicity tree automata.
Proposition 2 Let A 1 and A 2 be Q-multiplicity tree automata over a ranked alphabet Σ. Then, for every t ∈ T Σ it holds that A 1 × A 2 (t) = A 1 (t) · A 2 (t). Furthermore, automaton A 1 × A 2 can be computed from A 1 and A 2 in logarithmic space.
Proof Let A 1 = (n 1 , Σ, µ 1 , γ 1 ), A 2 = (n 2 , Σ, µ 2 , γ 2 ), and A 1 × A 2 = (n, Σ, µ, γ). First we show that for any t ∈ T Σ , We prove that Equation (5) holds for all t ∈ T Σ using induction on height(t). The base case t = σ ∈ Σ 0 holds immediately by definition since P 0 = I 1 . For the induction step, let h ∈ N 0 and assume that Equation (5) holds for every t ∈ T ≤h Σ . Take any t ∈ T h+1 Σ . Then t = σ(t 1 , . . . , t k ) for some k ≥ 1, σ ∈ Σ k , and t 1 , . . . , t k ∈ T ≤h Σ . By induction hypothesis, Equation (4), and the mixed-product property of Kronecker product we now have This completes the proof of Equation (5) for all t ∈ T Σ by induction. For every t ∈ T Σ , we now have We conclude by noting that automaton A 1 × A 2 can be computed from A 1 and A 2 by an algorithm that maintains a constant number of pointers, therefore requiring only logarithmic space.
A tree series f is called recognisable if it is recognised by some multiplicity tree automaton; such an automaton is called an MTA-representation of f . An MTA-representation of f that has the smallest dimension is called minimal. The set of all recognisable tree series in F T Σ is denoted by Rec(Σ, F).
The following result was first shown by Bozapalidis and Louscou-Bozapalidou (1983); an essentially equivalent result was later shown by Habrard and Oncina (2006).
Theorem 3 (Bozapalidis and Louscou-Bozapalidou, 1983) Let Σ be a ranked alphabet and F be a field. Let f ∈ F T Σ and let H be the Hankel matrix of f . It holds that f ∈ Rec(Σ, F) if and only if H has finite rank over F. In case f ∈ Rec(Σ, F), the dimension of a minimal MTA-representation of f is rank (H) over F.
The following result by Bozapalidis and Alexandrakis (1989, Proposition 4) states that for any recognisable tree series, its minimal MTA-representation is unique up to change of basis.

DAG Representations of Finite Trees
Let Σ be a ranked alphabet. A DAG representation of a Σ-tree (Σ-DAG or DAG for short) is a rooted directed acyclic ordered multigraph whose nodes are labelled with symbols from Σ such that the outdegree of each node is equal to the rank of the symbol it is labelled with. Formally a Σ-DAG consists of a set of nodes V , for each node v ∈ V a list of successors succ(v) ∈ V * , and a node labelling λ : V → Σ where for each node v ∈ V it holds that λ(v) ∈ Σ |succ(v)| . Note that Σ-trees are a subclass of Σ-DAGs.
Let G be a Σ-DAG. The size of G, denoted by size(G), is the number of nodes in G. The height of G, denoted by height(G), is the length of a longest directed path in G. For any node v in G, the sub-DAG of G rooted at v, denoted by G| v , is the Σ-DAG consisting of the node v and all of its descendants in G. Clearly, if a node v 0 is the root of G then For any Σ-DAG G, we define its unfolding into a Σ-tree, denoted by unfold (G), inductively as follows: If the root of G is labelled with a symbol σ and has the list of successors v 1 , . . . , v k , then It is easy to see that the following proposition holds.
Because a context has exactly one occurrence of the symbol ✷, any DAG representation of a Σ-context is a ({✷} ∪ Σ)-DAG that has a unique path from the root to the (unique) ✷-labelled node. The concatenation of a DAG K, representing a Σ-context, and a Σ-DAG G, denoted by K[G], is the Σ-DAG obtained by substituting the root of G for ✷ in K.
Proposition 6 Let K be a DAG representation of a Σ-context, and let G be a Σ-DAG.
Proof The proof is by induction on height(K). For the base case height (K) = 0, we have that K = ✷ and therefore unfold ( For the induction step, let h ∈ N 0 and assume that the proposition holds if height (K) ≤ h. Let K be a DAG representation of a Σ-context such that height(K) = h + 1. Let the root of K have label σ and list of successors v 1 , . . . , v k . By definition, there is a unique path in K going from the root to the ✷-labelled node. Without loss of generality, we can assume that the ✷-labelled node is a successor of v 1 . Take an arbitrary Σ-DAG G. Since height(K| v 1 ) ≤ h, we have by the induction hypothesis that This completes the proof.

Multiplicity Tree Automata on DAGs
In this section, we introduce the notion of a multiplicity tree automaton on DAGs. To the best of our knowledge, this notion has not been studied before.
Let F be a field, and A = (n, Σ, µ, γ) be an F-multiplicity tree automaton. The computation of the automaton A on a Σ-DAG G = (V, E) is defined as follows: A run of A on G is a mapping ρ : Sub(G) → F n such that for every node v ∈ V , if v is labelled with σ and has the list of successors succ( In the following proposition, we show that the weight assigned by a multiplicity tree automaton to a DAG is equal to the weight assigned to its tree unfolding. Proposition 7 Let F be a field, and A = (n, Σ, µ, γ) be an F-multiplicity tree automaton. For any Σ-DAG G, it holds that ρ(G) = µ(unfold (G)) and A (G) = A (unfold (G)).
Proof Let V be the set of nodes of G. First we show that for every v ∈ V , The proof is by induction on height (G| v ). For the base case, let height(G| v ) = 0. This implies that G| v = σ ∈ Σ 0 . Therefore, by definition we have that For the induction step, let h ∈ N 0 and assume that Equation (6) holds for every v ∈ V such that height (G| v ) ≤ h. Take any v ∈ V such that height(G| v ) = h + 1. Let the root of G| v be labelled with a symbol σ and have list of successors succ(v) = v 1 , . . . , v k . Then for every j ∈ [k], we have that height(G| v j ) ≤ h and thus ρ(G| v j ) = µ(unfold (G| v j )) holds by the induction hypothesis. This implies that which completes the proof of Equation (6) for all v ∈ V by induction.
. Suppose we were to check whether automata A and B are equivalent. Then the only counterexample to their equivalence, namely the tree t n , has size O(2 n ). Note, however, that t n has an exponentially more succinct DAG representation G n , given in Figure 2.

Arithmetic Circuits
An arithmetic circuit is a finite directed acyclic vertex-labelled multigraph whose vertices, called gates, have indegree 0 or 2. Vertices of indegree 0 are called input gates and are labelled with a constant 0 or 1, or a variable from the set {x i : i ∈ N}. Vertices of indegree 2 are called internal gates and are labelled with an arithmetic operation +, ×, or −. We assume that there is a unique gate with outdegree 0 called the output gate. An arithmetic circuit is called variable-free if all input gates are labelled with 0 or 1.
Given two gates u and v of an arithmetic circuit C, we call u a child of v if (u, v) is a directed edge in C. The size of C is the number of gates in C. The height of a gate v in C, written as height(v), is the length of a longest directed path from an input gate to v. The height of C is the maximal height of a gate in C.
An arithmetic circuit C computes a polynomial over the integers as follows: An input gate of C labelled with α ∈ {0, 1} ∪ {x i : i ∈ N} computes the polynomial α. An internal gate of C labelled with * ∈ {+, ×, −} computes the polynomial p 1 * p 2 where p 1 and p 2 are the polynomials computed by its children. For any gate v in C, we write f v for the polynomial computed by v. The output of C, written f C , is the polynomial computed by the output gate of C. The Arithmetic Circuit Identity Testing (ACIT) problem asks whether the output of a given arithmetic circuit is equal to the zero polynomial.

The Learning Model
In this paper we work with the exact learning model of Angluin (1988): Let f be a target function. A Learner (learning algorithm) may, in each step, propose a hypothesis function h by making an equivalence query to a Teacher. If h is equivalent to f , then the Teacher returns YES and the Learner succeeds and halts. Otherwise, the Teacher returns NO with a counterexample, which is an assignment x such that h(x) = f (x). Moreover, the Learner may query the Teacher for the value of the function f on a particular assignment x by making a membership query on x. The Teacher returns the value f (x).
We say that a class of functions C is exactly learnable if there is a Learner that for any target function f ∈ C , outputs a hypothesis h ∈ C such that h(x) = f (x) for all assignments x, and does so in time polynomial in the size of a shortest representation of f and the size of a largest counterexample returned by the Teacher. We moreover say that the class C is exactly learnable in (randomised) polynomial time if the learning algorithm can be implemented to run in (randomised) polynomial time in the Turing model.

MTA Equivalence is interreducible with ACIT
In this section, we show that the equivalence problem for Q-multiplicity tree automata is logspace interreducible with ACIT. A related result, characterising equivalence of probabilistic visibly pushdown automata on words in terms of polynomial identity testing, was shown by Kiefer et al. (2013). On several occasions in this section, we will implicitly make use of the fact that a composition of two logspace reductions is again a logspace reduction (Arora and Barak, 2009, Lemma 4.17).

From MTA Equivalence to ACIT
In this section, we present a logspace reduction from the equivalence problem for Q-MTAs to ACIT. We start with the following lemma.
Lemma 8 Given an integer n ∈ N and a Q-multiplicity tree automaton A over a ranked alphabet Σ, one can compute, in logarithmic space in |A| and n, a variable-free arithmetic circuit that has output t∈T <n Σ A (t).
Proof Let A = (r, Σ, µ, γ), and let m be the rank of Σ. By definition, it holds that We have t∈T <1 Σ µ(t) = σ∈Σ 0 µ(σ). For every i ∈ N, it holds that and thus by bilinearity of Kronecker product, In the following we define a variable-free arithmetic circuit Φ that has output t∈T <n Σ A (t). First, let us denote G(i) := t∈T <i Σ µ(t) for every i ∈ N. Then by Equation (8) we have . . , m}. In coordinate notation, for every j ∈ [r] we have by Equation (1) that We present Φ as a straight-line program, with built-in constants representing the entries of the transition matrices and the final weight vector of A, internal variables {s k (l 1 ,...,l k ),j : k ∈ {0, . . . , m}, (l 1 , . . . , l k ) ∈ [r] k , j ∈ [r]} and {g i,j : i ∈ [n], j ∈ [r]} evaluating the entries of matrices S(k) and vectors G(i) respectively, and the final internal variable f computing the value of Φ.
Formally, the straight-line program Φ is given in Table 1. Here the statements are given in indexed-sum and indexed-product notation, which can easily be expanded in terms of the corresponding binary operations. It follows from Equations (7) and (9) The input gates of Φ are labelled with rational numbers. By separately encoding numerators and denominators, we can in logarithmic space reduce Φ to an arithmetic circuit where all input gates are labelled with integers. Moreover, without loss of generality we can assume that every input gate of Φ is labelled with 0 or 1. Any other integer label given in binary can be encoded as an arithmetic circuit.
Recalling that a composition of two logspace reductions is again a logspace reduction, we conclude that the entire computation takes logarithmic space in |A| and n.
Before presenting the reduction in Proposition 10, we recall the following characterisation (Seidl, 1990, Theorem 4.2) of equivalence of two multiplicity tree automata over an arbitrary field.
Proposition 9 (Seidl, 1990) Suppose A and B are multiplicity tree automata of dimension n 1 and n 2 , respectively, and over a ranked alphabet Σ. Then, A and B are equivalent if and only if A (t) = B (t) for every t ∈ T <n 1 +n 2 Σ .
Proposition 10 The equivalence problem for Q-multiplicity tree automata is logspace reducible to ACIT. Proof Let A and B be Q-multiplicity tree automata over a ranked alphabet Σ, and let n be the sum of their dimensions. Proposition 2 implies that

For
Thus by Proposition 9, automata A and B are equivalent if and only if We know from Proposition 2 that automata A×A, B ×B, and A×B can be computed in logarithmic space. Thus by Lemma 8 one can compute, in logarithmic space in |A| and |B|, variable-free arithmetic circuits that have outputs t∈T <n and t∈T <n Σ A × B (t) respectively. Using Equation (10), we can now easily construct a variable-free arithmetic circuit that has output 0 if and only if A and B are equivalent.

From ACIT to MTA Equivalence
We now present a converse reduction: from ACIT to the equivalence problem for Q-MTAs. Allender et al. (2009, Proposition 2.2) give a logspace reduction of the general ACIT problem to the special case of ACIT for variable-free circuits. The latter can, by representing arbitrary integers as differences of two non-negative integers, be reformulated as the problem of deciding whether two variable-free arithmetic circuits with only + and ×-internal gates compute the same number.
Proposition 11 ACIT is logspace reducible to the equivalence problem for Q-multiplicity tree automata.
Proof Let C 1 and C 2 be two variable-free arithmetic circuits whose internal gates are labelled with + or ×. By padding with extra gates, without loss of generality we can assume that in each circuit the children of a height-i gate both have height i − 1, +-gates have even height, ×-gates have odd height, and the output gate has an even height h.
In the following we define two Q-MTAs, A 1 and A 2 , that are equivalent if and only if circuits C 1 and C 2 have the same output. Automata A 1 and A 2 are both defined over a ranked alphabet Σ = {σ 0 , σ 1 , σ 2 } where σ 0 is a nullary, σ 1 a unary, and σ 2 a binary symbol. Intuitively, automata A 1 and A 2 both recognise the common 'tree-unfolding' of C 1 and C 2 .
We now derive A 1 from C 1 ; A 2 is analogously derived from C 2 . Let {v 1 , . . . , v r } be the set of gates of C 1 where v r is the output gate. Automaton A 1 has a state q i for every gate v i of C 1 . Formally, A 1 = (r, Σ, µ, e r ) where for every i ∈ [r]: • If v i is an input gate with label 1 then µ(σ 0 ) i = 1, otherwise µ(σ 0 ) i = 0.
Define a sequence of trees (t n ) n∈N 0 ⊆ T Σ by t 0 = σ 0 , t n+1 = σ 1 (t n ) for n odd, and t n+1 = σ 2 (t n , t n ) for n even. In the following, we show that A 1 (t h ) = f C 1 . For every gate v of C 1 , by assumption it holds that all paths from v to the output gate have equal length. We now prove that for every i ∈ [r], where h i := height(v i ). We use induction on h i ∈ {0, . . . , h}. For the base case, let h i = 0. Then, v i is an input gate and thus by definition of automaton A 1 we have For the induction step, let n ∈ [h] and assume that Equation (11) holds for every gate v i of height less than n. Take an arbitrary gate v i of C 1 such that h i = n. Let gates v j 1 and v j 2 be the children of v i . Then h j 1 = h j 2 = h i − 1 = n − 1 by assumption. The induction hypothesis now implies that µ(t h i −1 ) j 1 = f v j 1 and µ(t h i −1 ) j 2 = f v j 2 . Depending on the label of v i , there are two possible cases as follows: (i) If v i is a +-gate, then h i is even and thus by definition of A 1 we have If v i is a ×-gate, then h i is odd and thus by definition of A 1 and Equation (1) we have This completes the proof of Equation (11) by induction. Now for the output gate v r of C 1 , we get from Equation (11) that µ(t h ) r = f vr since h r = h. Therefore, Analogously, it holds that A 2 (t h ) = f C 2 . It is moreover clear by construction that A 1 (t) = 0 and A 2 (t) = 0 for every t ∈ T Σ \ {t h }. Therefore, automata A 1 and A 2 are equivalent if and only if arithmetic circuits C 1 and C 2 have the same output.

The Learning Algorithm
In this section, we give an exact learning algorithm for multiplicity tree automata. Our algorithm is polynomial in the size of a minimal automaton equivalent to the target and the size of a largest counterexample given as a DAG. As seen in Example 1, DAG counterexamples can be exponentially more succinct than tree counterexamples. Therefore, achieving a polynomial bound in the context of DAG representations is a more exacting criterion.
Over an arbitrary field F, the algorithm can be seen as running on a Blum-Shub-Smale machine that can write and read field elements to and from its memory at unit cost and that can also perform arithmetic operations and equality tests on field elements at unit cost (see Arora and Barak, 2009). Over Q, the algorithm can be implemented in randomised polynomial time by representing rationals as arithmetic circuits and using a coRP algorithm for equality testing of such circuits (see Allender et al., 2009).
This section is organised as follows: In Section 4.1 we present the algorithm. In Section 4.2 we prove correctness on trees, and then argue in Section 4.3 that the algorithm can be faithfully implemented using a DAG representation of trees. Finally, in Section 4.4 we give a complexity analysis of the algorithm assuming the DAG representation.

The Algorithm
Let f ∈ Rec(Σ, F) be the target function. The algorithm learns an MTA-representation of f using its Hankel matrix H, which has finite rank over F by Theorem 3. At each stage, the algorithm maintains the following data: • An integer n ∈ N.
• A submatrix H X,Y of H that has full row rank.
These data determine a hypothesis automaton A of dimension n, whose states correspond to the rows of H X,Y , with the i th row being the state reached after reading the tree t i . The Learner makes an equivalence query on hypothesis A. In case the Teacher answers NO, the Learner receives a counterexample z. The Learner then parses z bottom-up to find a minimal subtree of z that is also a counterexample, and uses that subtree to augment the sets of rows and columns.

Correctness Proof
In this section, we prove the correctness of the exact learning algorithm LMTA. Specifically, we show that, given a target f ∈ Rec(Σ, F), algorithm LMTA outputs a minimal MTArepresentation of f after at most rank (H) iterations of the main loop.
The correctness proof naturally breaks down into several lemmas. First, we show that matrix H X,Y has full row rank.
Lemma 12 Linear independence of the set of vectors {H t 1 ,Y , . . . , H tn,Y } is an invariant of the loop consisting of Step 2 and Step 3.
Proof We argue inductively on the number of iterations of the loop. The base case n = 1 clearly holds since f (z) = 0.
For the induction step, suppose that the set {H t 1 ,Y , . . . , H tn,Y } is linearly independent at the start of an iteration of the loop. If a tree t ∈ T Σ is added to X during Step 2.1, then H t,Y is not a linear combination of H t 1 ,Y , . . . , H tn,Y , and therefore H t 1 ,Y , . . . , H tn,Y , H t,Y are linearly independent vectors. Hence, set {H t 1 ,Y , . . . , H tn,Y } is linearly independent at the start of Step 3.
Unless the algorithm halts in Step 3.1, it proceeds to Step 3.2 where the set of columns Y is increased, which clearly preserves linear independence of vectors H t 1 ,Y , . . . , H tn,Y . If a tree τ j is added to X in Step 3.3, then H τ j ,Y is not a linear combination of H t 1 ,Y , . . . , H tn,Y which implies that the vectors H t 1 ,Y , . . . , H tn,Y , H τ j ,Y are linearly independent. Hence, the set {H t 1 ,Y , . . . , H tn,Y } is linearly independent at the start of the next iteration of the loop.
Secondly, we show that Step 2.2 of LMTA can always be performed.
Algorithm LMTA Target: f ∈ Rec(Σ, F), where Σ has rank m and F is a field 1. Make an equivalence query on the 0-dimensional F-MTA over Σ.
If the answer is YES then output the 0-dimensional F-MTA over Σ and halt. Otherwise the answer is NO and z is a counterexample. Initialise: 2.2. Define an F-MTA A = (n, Σ, µ, γ) as follows: • γ = H X,✷ .

For every j ∈ [k]:
If H τ j ,Y is not a linear combination of H t 1 ,Y , . . . , H tn,Y then n ← n + 1, t n ← τ j , X ← X ∪ {t n }.
Equation (13) which yields a contradiction since z is a counterexample for the hypothesis A.
Finally, we show that the row set X grows by at least 1 in each iteration of the main loop.
Lemma 15 Every complete iteration of the Step 2 -3 loop strictly increases the cardinality of X.
Putting together Lemmas 12 -15, we conclude the following.
Proposition 16 Let Σ be a ranked alphabet and F be a field. Let f ∈ Rec(Σ, F), let H be the Hankel matrix of f , and r be the rank (over F) of H. On target f , the algorithm LMTA outputs a minimal MTA-representation of f after at most r iterations of the loop consisting of Step 2 and Step 3.
Proof Lemmas 13 and 14 show that every step of the algorithm LMTA can be performed. Theorem 3 implies that r is finite. From Lemma 12 we know that whenever Step 2 starts, H X,Y is a full row rank matrix and thus n ≤ r. Lemma 15 implies that n increases by at least 1 in each iteration of the Step 2 -3 loop. Therefore, the number of iterations of the loop is at most r.
The proof follows by observing that LMTA halts only upon receiving the answer YES to an equivalence query.

Succinct Representations
We now explain how algorithm LMTA can be correctly implemented using a DAG representation of trees. In particular, we assume that membership queries are made on Σ-DAGs, that the counterexamples are given as Σ-DAGs, the elements of X are Σ-DAGs, and the elements of Y are DAG representations of Σ-contexts, i.e., ({✷} ∪ Σ)-DAGs.
As shown in Section 2.5, multiplicity tree automata can run directly on DAGs and, moreover, they assign equal weight to a DAG and to its tree unfolding. Crucially also, as explained in the proof of Theorem 17, Step 3.1 can be run directly on a DAG representation of the counterexample, without unfolding. In particular, Step 3.1 involves multiple executions of the hypothesis automaton on trees. By Proposition 7, we can faithfully carry out this step using DAG representations of trees.
Step 3.1 also involves considering all subtrees of a given counterexample. However, by Proposition 5 this is equivalent to looking at all sub-DAGs of a DAG representation of the counterexample. At various points in the algorithm, we take c ∈ Y , t ∈ X and compute their concatenation c[t] in order to determine the corresponding entry H t,c of the Hankel matrix by a membership query. Proposition 6 implies that this can be done faithfully using DAG representations of Σ-trees and Σ-contexts.

Complexity Analysis
In this section we give a complexity analysis of our algorithm, and compare it to the best previously-known exact learning algorithm for multiplicity tree automata (Habrard and Oncina, 2006) showing in particular an exponential improvement on the query complexity and the running time in the worst case.
Theorem 17 Let f ∈ Rec(Σ, F) where Σ has rank m and F is a field. Let A be a minimal MTA-representation of f , and let r be the dimension of A. Then, f is learnable by the algorithm LMTA, making r + 1 equivalence queries, |A| 2 + |A| · s membership queries, and O(|A| 2 +|A|·r·s) arithmetic operations, where s denotes the size of a largest counterexample z, represented as a DAG, that is obtained during the execution of the algorithm.
Proof Proposition 16 implies that, on target f , algorithm LMTA outputs a minimal MTArepresentation of f after at most r iterations of the Step 2 -3 loop, thereby making at most r + 1 equivalence queries.
Let H be the Hankel matrix of f . From Lemma 12 we know that matrix H X,Y has full row rank, which implies that |X| ≤ r. As for the cardinality of the column set Y , at the end of Step 1 we have |Y | = 1. Furthermore, in each iteration of Step 3.2 the number of columns added to Y is at most where k and n are as defined in Step 3.2. Since the number of iterations of Step 3.2 is at most r − 1, we have |Y | ≤ r m . The number of membership queries made in Step 2 over the whole algorithm is σ∈Σ |σ(X, . . . , X)| + |X| · |Y | because the Learner needs to ask for the values of the entries of matrices H X,Y and H σ(X,...,X),Y for every σ ∈ Σ.
To analyse the number of membership queries made in Step 3, we now detail the procedure by which an appropriate sub-DAG of the counterexample z is found in Step 3.1. By Lemma 14, there exists a sub-DAG τ of z such that H τ,Y = µ(τ ) · H X,Y . Thus given a counterexample z in Step 3.1, the procedure for finding a required sub-DAG of z is as follows: Check if H τ,Y = µ(τ ) · H X,Y for every sub-DAG τ of z in a nondecreasing order of height; stop when a sub-DAG τ is found such that H τ,Y = µ(τ ) · H X,Y .
As for the arithmetic complexity, in Step 2.1 one can determine if a vector H σ(t i 1 ,...,t i k ),Y is a linear combination of H t 1 ,Y , . . . , H tn,Y via Gaussian elimination using O(n 2 · |Y |) arithmetic operations (see Cohen, 1993, Section 2.3). Analogously, in Step 3.3 one can determine if H τ j ,Y is a linear combination of H t 1 ,Y , . . . , H tn,Y via Gaussian elimination using O(n 2 ·|Y |) arithmetic operations. Since |X| ≤ r and |Y | ≤ r m , all together Step 2.1 and Step 3.3 require at most O(|A| 2 ) arithmetic operations.
Lemma 13 implies that in each iteration of Step 2.2, for any σ ∈ Σ there exists a unique matrix µ(σ) ∈ F n rk(σ) ×n that satisfies Equation (12). To perform an iteration of Step 2.2, we first put matrix H X,Y in echelon form and then, for each σ ∈ Σ, solve Equation (12) for µ(σ) by back substitution. It follows from standard complexity bounds on the conversion of matrices to echelon form (Cohen, 1993, Section 2.3) that the total operation count for Step 2.2 can be bounded above by O(|A| 2 ).
Finally, we consider the arithmetic complexity of Step 3.1. In every iteration, for each sub-DAG τ of the counterexample z the Learner needs to compute the vector µ(τ ) and the product µ(τ ) · H X,Y . Note that µ(τ ) can be computed bottom-up from the sub-DAGs of τ . Since z has at most s sub-DAGs, Step 3.1 requires at most O(|A| · r · s) arithmetic operations. All together, the algorithm requires at most O(|A| 2 +|A|·r·s) arithmetic operations.
Algorithm LMTA can be used to show that over Q, multiplicity tree automata are exactly learnable in randomised polynomial time. The key idea is to represent numbers as arithmetic circuits. In executing LMTA, the Learner need only perform arithmetic operations on circuits (addition, subtraction, multiplication, and division), which can be done in constant time, and equality testing, which can be done in coRP (see Arora and Barak, 2009). These suffice for all the operations detailed in the proof of Theorem 17; in particular they suffice for Gaussian elimination, which can be used to implement the linear independence checks in LMTA.
The complexity of algorithm LMTA should be compared to the complexity of the algorithm of Habrard and Oncina (2006), which learns multiplicity tree automata by making r + 1 equivalence queries, |A| · s membership queries, and a number of arithmetic operations polynomial in |A| and s, where s is the size of the largest counterexample given as a tree. Note that the algorithm of Habrard and Oncina (2006) cannot be straightforwardly adapted to work directly with DAG representations of trees since when given a counterexample z, every suffix of z is added to the set of columns. However, the tree unfolding of a DAG can have exponentially many different suffixes in the size of the DAG. For example, the DAG in Figure 2 has size n, and its tree unfolding, shown in Figure 1, has O(2 n ) different suffixes.

Lower Bounds on Query Complexity of Learning MTA
In this section, we study lower bounds on the query complexity of learning multiplicity tree automata in the exact learning model. Our results generalise the corresponding lower bounds for learning multiplicity word automata by Bisht et al. (2006), and make no assumption about the computational model of the learning algorithm.
First, we give a lower bound on the query complexity of learning multiplicity tree automata over an arbitrary field, which is the situation of our algorithm in Section 4.
Theorem 18 Any exact learning algorithm that learns the class of multiplicity tree automata of dimension at most r, over a ranked alphabet (Σ, rk ) and any field, must make at least σ∈Σ r rk(σ)+1 − r 2 queries.
Proof Take an arbitrary exact learning algorithm L that learns the class of multiplicity tree automata of dimension at most r, over a ranked alphabet (Σ, rk ) and over any field. Let F be any field. Let } is algebraically independent over F. Let us define a 'generic' K-multiplicity tree automaton A := (r, Σ, µ, γ) where γ = e 1 ∈ F r×1 and µ(σ) = [z σ i,j ] i,j ∈ K r rk(σ) ×r for every σ ∈ Σ. Define a tree series f := A . Since every F-multiplicity tree automaton can be obtained from A by substituting values from F for the variables z σ i,j , if the Hankel matrix of f had rank less than r then every r-dimensional F-multiplicity tree automaton would have Hankel matrix of rank less than r. Therefore, the Hankel matrix of f has rank r.
We run algorithm L on the target function f . By assumption, the output of L is an MTA A ′ = (r, Σ, µ ′ , γ ′ ) such that A ′ ≡ f . Let n be the number of queries made by L on target f . Let t 1 , . . . , t n ∈ T Σ be the trees on which L either made a membership query, or which were received as counterexample to an equivalence query. Then for every l ∈ [n], there exists a multivariate polynomial p l ∈ F[(z σ i,j ) i,j,σ ] such that f (t l ) = p l . Note that A and A ′ are both minimal MTA-representations of f . Thus by Theorem 4, there exists an invertible matrix U ∈ K r×r such that γ = U ·γ ′ and µ(σ) = U ⊗rk (σ) ·µ ′ (σ)·U −1 for every σ ∈ Σ. This implies that the entries of matrices µ(σ), σ ∈ Σ, lie in an extension of F generated by the entries of U and {p l : l ∈ [n]}. Since the entries of matrices µ(σ), σ ∈ Σ, form an algebraically independent set over F, their number is at most r 2 + n.
One may wonder whether a learning algorithm could do better over a fixed field F by exploiting particular features of the field. In this setting, we have the following lower bound.
Theorem 19 Let F be an arbitrary field. Any exact learning algorithm that learns the class of F-multiplicity tree automata of dimension at most r, over a ranked alphabet (Σ, rk ) with at least one unary symbol and rank m, must make number of queries at least 1 2 m+1 · σ∈Σ r rk(σ)+1 − r 2 − r .
Proof Without loss of generality, we can assume that r is even and define n := r/2. Let L be an exact learning algorithm for the class of F-multiplicity tree automata of dimension at most r, over a ranked alphabet (Σ, rk ) with rk −1 ({1}) = ∅. We will identify a class of functions C such that L has to make at least σ∈Σ n rk (σ)+1 − n 2 − n queries to distinguish between the members of C.
In Lemma 20 we state some properties of the functions in C. More precisely, we show that the coefficient of a tree t ∈ T Σ in any series f ∈ C fundamentally depends on whether t has 0, 1, or at least 2 nodes whose label is not σ 0 or σ 1 . Here for every i ∈ N 0 and t ∈ T Σ , we use σ i 1 (t) to denote the tree σ 1 (σ 1 (. . . σ 1 ( i t) . . .)).
Run L on a target f ∈ C. Lemma 20 (i), (iii) and Remark 21 imply that when L makes a membership query on t ∈ T Σ such that σ∈Σ\{σ 0 ,σ 1 } # σ (t) ≥ 2, the Teacher returns 0, while when L makes a membership query on t = σ j 1 (σ 0 ), the Teacher returns 1 if j mod n = 0 and returns 0 otherwise. In these cases, L does not gain any new information about f since every function in C is consistent with the values returned by the Teacher.
The lower bounds of Theorems 18 and 19 are both linear in the target automaton size. Note that when the alphabet rank is fixed, the lower bound for learning over a fixed field (Theorem 19) is the same up to a constant factor as for learning over an arbitrary field (Theorem 18).
Assuming a Teacher that represents counterexamples as succinctly as possible, e.g, using the algorithm of Seidl (1990), the upper bound of algorithm LMTA from Theorem 17 is quadratic in the target automaton size, i.e., quadratically greater than the lower bound of Theorem 18. Beimel et al. (2000) apply their exact learning algorithm for multiplicity word automata to show exact learnability of certain classes of polynomials over both finite and infinite fields. They also prove the learnability of disjoint DNF formulae (i.e., DNF formulae in which each assignment satisfies at most one term) and, more generally, disjoint unions of geometric boxes over finite domains.

Future Work
The learning framework considered in this paper involves tree automata, which are more expressive than word automata. Moreover, our result on the complexity of equivalence of multiplicity tree automata shows that, through equivalence queries, the Learner essentially has an oracle for polynomial identity testing. Thus a natural direction for future work is to seek to apply our algorithm to derive new results on exact learning of other concept classes, such as propositional formulae and polynomials (both in the commutative and noncommutative cases). In this direction, we would like to examine the relationship of our work with that of Klivans and Shpilka (2006) on exact learning of algebraic branching programs and arithmetic circuits and formulae. The latter paper relies on rank bounds for Hankel matrices of polynomials in noncommuting variables, obtained by considering a generalised notion of partial derivative. Here we would like to determine whether the extra expressiveness of Hankel matrices over tree series can be used to show learnability of more expressive classes of formulae and circuits. Sakakibara (1990) showed that context-free grammars (CFGs) can be learned efficiently in the exact learning model using membership queries and counterexamples based on parse trees. Given the important role of weighted and probabilistic CFGs across a range of applications including linguistics, another natural next step would be to apply our algorithm to learn weighted CFGs similarly using queries and counterexamples involving parse trees.