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.