DIVERSITY-BASED INFERENCE OF FINITE AUTOMATA.

A novel procedure is presented for inferring the structure of a finite-state automaton (FSA) from its input/output behavior, using access to the automaton to perform experiments. The procedure uses a novel representation for FSAs that is based on the notion of equivalence between tests. The number of such equivalence classes is called the diversity of the automaton; the diversity may be as small as the logarithm of the number of states of the automaton. The size of the representation of the FSA, and the running time of the procedure is polynomial in the diversity and ln(1/ epsilon ), where epsilon is a given upper bound on the probability that the procedure returns an incorrect result. Some evidence for the practical efficiency of the approach is presented.