Learning Unary Output Two-Tape Automata from Multiplicity and Equivalence Queries QueriesAuthors: Gionanna Melideo and Stefano Varricchio Source: Lecture Notes in Artificial Intelligence Vol. 1501, 1998, 87 - 102. 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^{*} × {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. ©Copyright 1998 Springer |