@Article{RS93a,
  author = 	 { Ronald L. Rivest and Robert E. Schapire },
  title = 	 { Inference of Finite Automata Using Homing Sequences },
  journal = 	 { Information and Computation },
  publisher =    { Academic Press },                  
  issn =         { 0890-5401 },
  OPTyear = 	 { 1993 },
  OPTmonth = 	 { April },
  date =         { 1993-04 },                  
  volume = 	 { 103 },
  number = 	 { 2 },
  pages = 	 { 299--347 },
  doi =          { 10.1006/inco.1993.1021 },
  url =          { http://www.sciencedirect.com/science/article/pii/S0890540183710217 },
  abstract =     {
        We present new algorithms for inferring an unknown finite-state automaton from its
        input/output behavior, even in the absence of a means of resetting the machine to a start 
        state. A key technique used is inference of a homing sequence for the unknown automaton.
        Our inference procedures experiment with the unknown machine, and from time to time require
        a teacher to supply counterexamples to incorrect conjectures about the structure of the 
        unknown automaton. In this setting, we describe a learning algorithm that, with probability
        $1 - \delta$, outputs a correct description of the unknown machine in time polynomial 
        in the automaton's size, the length of the longest counterexample, and $\log(1/\delta)$. 
        We present an analogous algorithm that makes use of a diversity-based representation of 
        the finite-state system. Our algorithms are the first which are provably effective for 
        these problems, in the absence of a ``reset.'' We also present probabilistic algorithms
        for permutation automata which do not require a teacher to supply counterexamples. 
        For inferring a permutation automaton of diversity $D$, we improve the best previous
        time bound by roughly a factor of $D^3/\log D$.
                 },
}