Learning Unary Output Two-Tape Automata from Multiplicity and Equivalence Queries
Abstract
We investigate the learning problem of unary output two-tape non deterministic finite automata (unary output 2-tape NFAs) from multiplicity and equivalence queries. Given an alphabet A and a unary alphabet x , a unary output 2-tape NFA accepts a subset of A A ^*x x ^*. In [ 6 ] Bergadano and Varricchio proved that the behavior of an unknown automaton with multiplicity in a field K ( K -automaton) is exactly identifiable when multiplicity and equivalence queries are allowed. In this paper multiplicity automata are used to prove the learnability of unary output 2-tape NFA’s. We shall identify the behavior of a unary output 2-tape NFA using an automaton with multiplicity in K ^rat 〈〈 x 〉〉. We provide an algorithm which is polynomial in the size of this automaton.
Cite
Text
Melideo and Varricchio. "Learning Unary Output Two-Tape Automata from Multiplicity and Equivalence Queries." International Conference on Algorithmic Learning Theory, 1998. doi:10.1007/3-540-49730-7_7Markdown
[Melideo and Varricchio. "Learning Unary Output Two-Tape Automata from Multiplicity and Equivalence Queries." International Conference on Algorithmic Learning Theory, 1998.](https://mlanthology.org/alt/1998/melideo1998alt-learning/) doi:10.1007/3-540-49730-7_7BibTeX
@inproceedings{melideo1998alt-learning,
title = {{Learning Unary Output Two-Tape Automata from Multiplicity and Equivalence Queries}},
author = {Melideo, Giovanna and Varricchio, Stefano},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1998},
pages = {87-102},
doi = {10.1007/3-540-49730-7_7},
url = {https://mlanthology.org/alt/1998/melideo1998alt-learning/}
}