@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.)
},
}