Learning Unary Output Two-Tape Automata from Multiplicity and Equivalence Queries Queries

Authors: 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 Krat<<x>>. We provide an algorithm which is polynomial in the size of this automaton.

©Copyright 1998 Springer