Complexity of Equivalence and Learning for Multiplicity Tree Automata

Ines Marusic ( University of Oxford )

We consider the complexity of equivalence and learning for multiplicity tree automata, i.e., weighted tree automata with weights in a field. We first characterise the complexity of equivalence testing as being logspace equivalent to polynomial identity testing. Secondly, we consider the problem of learning multiplicity tree automata in Angluin's exact learning model. Here we give lower bounds on the number of queries, both for the case of an arbitrary and a fixed underlying field. We also present a learning algorithm in which counterexamples use succinct representations of trees as DAGs. Assuming a Teacher that represents counterexamples as succinctly as possible, our algorithm uses exponentially fewer queries than the best previously known procedure, leaving only a polynomial gap with the above-mentioned lower bound.