@Article{RS94a,
author = { Ronald L. Rivest and Robert E. Schapire },
title = { Diversity-based inference of finite automata },
pages = { 555--589 },
url = { http://doi.acm.org/10.1145/176584.176589 },
doi = { 10.1145/176584.176589 },
acmid = { 176589 },
acm = { 89672 },
journal = { Journal of the ACM },
issn = { 0004-5411 },
publisher = { ACM },
OPTyear = { 1994 },
OPTmonth = { May },
date = { 1994-05 },
volume = { 41 },
number = { 3 },
keywords = { diversity-based representation, finite automata, inductive inference,
learning theory, permutation automata},
abstract = {
We present new procedures 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 procedures use a new representation for finite automata, based on the notion of equivalence
between tests. We call the number of such equivalence classes the diversity of the automaton; the
diversity may be as small as the logarithm of the number of states of the automaton. For the special
class of permutation automata, we describe an inference procedure that runs in time polynomial
in the diversity and $\log(1/\delta)$, where $\delta$ 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.)
We also discuss techniques for handling more general automata.
\par
We present 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 MicroVax.
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.)
\par
Finally, we present a new procedure for inferring automata of a special type in which
the global state is composed of a vector of binary local state variables,
all of which are observable (or visible) to the experimenter. Our inference procedure
runs provably in time polynomial in the size of this vector (which happens to be the
diversity of the automaton), even though the global state space may be exponentially larger.
The procedure plans and executes experiments on the unknown automaton; we show that the
number of input symbols given to the automaton during this process is (to within
a constant factor) the best possible.
},
}