F. Bergadano et S. Varricchio, LEARNING BEHAVIORS OF AUTOMATA FROM MULTIPLICITY AND EQUIVALENCE QUERIES, SIAM journal on computing, 25(6), 1996, pp. 1268-1280
Citations number
18
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
We consider the problem of identifying the behavior of an unknown auto
maton with multiplicity in the field Q of rational numbers (Q-automato
n) from multiplicity and equivalence queries. We provide an algorithm
which is polynomial in the size of the Q-automaton and in the maximum
length of the given counterexamples. As a consequence, we have that Q-
automata are probably approximately correctly learnable (PAC-learnable
) in polynomial time when multiplicity queries are allowed. A corollar
y of this result is that regular languages are polynomially predictabl
e using membership queries with respect to the representation of unamb
iguous nondeterministic automata. This is important since there are un
ambiguous automata such that the equivalent deterministic automaton ha
s an exponentially larger number of states.