Complexity of Equivalence and Learning for Multiplicity Tree Automata
Abstract
We consider the query and computational complexity of learning multiplicity tree automata in Angluin's exact learning model. In this model, there is an oracle, called the Teacher, that can answer membership and equivalence queries posed by the Learner. Motivated by this feature, we first characterise the complexity of the equivalence problem for multiplicity tree automata, showing that it is logspace equivalent to polynomial identity testing.
Cite
Text
Marusic and Worrell. "Complexity of Equivalence and Learning for Multiplicity Tree Automata." Journal of Machine Learning Research, 2015.Markdown
[Marusic and Worrell. "Complexity of Equivalence and Learning for Multiplicity Tree Automata." Journal of Machine Learning Research, 2015.](https://mlanthology.org/jmlr/2015/marusic2015jmlr-complexity/)BibTeX
@article{marusic2015jmlr-complexity,
title = {{Complexity of Equivalence and Learning for Multiplicity Tree Automata}},
author = {Marusic, Ines and Worrell, James},
journal = {Journal of Machine Learning Research},
year = {2015},
pages = {2465-2500},
volume = {16},
url = {https://mlanthology.org/jmlr/2015/marusic2015jmlr-complexity/}
}