@InProceedings{RS87c, replaced-by = { RS94a }, author = { Ronald L. Rivest and Robert E. Schapire }, title = { Diversity-based inference of finite automata }, pages = { 78--87 }, doi = { 10.1109/SFCS.1987.21 }, booktitle = { Proceedings Twenth-Eighth IEEE Annual Symposium on Foundations of Computer Science }, date = { 1987 }, issn = { 0272-5428 }, publisher = { IEEE Computer Society }, editor = { Tom Leighton }, OPTyear = { 1987 }, OPTmonth = { October 12--14, }, eventdate = { 1987-10-12/1987-10-14 }, eventtitle = { FOCS '87 }, venue = { Los Angeles, California }, OPTorganization = { IEEE }, abstract = { We present a new procedure for inferring the structure of a finite-state automaton (FSA) from its input/output behavior, using access to the automaton to perform experiments. \par Our procedure uses a new representation for FSA's, based on the notion of equivalence between \emph{tests}. We call the number of such equivalence classes the \emph{diversity} of the automaton; the diversity may be as small as the logarithm of the number of states of the automaton. The size of our representation of the FSA, and the running time of our procedure (in some case provably, in others conjecturally) is polynomial in the diversity and $\ln(1/\epsilon)$, where $\epsilon$ is a given upper bound on the probability that our procedure returns an incorrect result. (Since our procedure uses randomization to perform experiments, there is a certain controllable chance that it will return an erroneous result.) \par We also present some evidence for the practical efficiency of our approach. For example, our procedure is able to infer the structure of an automaton based on Rubik's Cube (which has approximately $10^{19}$ states) in about 2 minutes on a DEC Micro Vax. This automaton is many orders of magnitude larger than possible with previous techniques, which would require time proportional at least to the number of global states. (Note that in this example, only a small fraction ($10^{-14}$) of the global states were even visited.) }, }