LEARNING BEHAVIORS OF AUTOMATA FROM MULTIPLICITY AND EQUIVALENCE QUERIES

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.