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