# Complexity of Equivalence and Learning for Multiplicity Tree Automata

Ines Marusic ( University of Oxford )

- 11:00 30th April 2014 ( week 1, Trinity Term 2014 )051

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.