@InProceedings{RS89,
  author = 	 { Ronald L. Rivest and Robert E. Schapire },
  title = 	 { Inference of Finite Automata Using Homing Sequences },
  pages = 	 { 411--420 },
  doi =          { 10.1145/73007.73047 },
  acm =          { 71 },                  
  booktitle =    { Proceedings Twenty-First Annual ACM Symposium on Theory of Computation },
  publisher =    { ACM },
  editor = 	 { D. S. Johnson },
  date =         { 1989 },                  
  OPTyear =      { 1989 },                  
  OPTmonth =     { May },                  
  eventdate =    { 1989-05-15/1989-05-17 },
  eventtitle =   { STOC '89 },
  venue =        { Seattle, Washington },                  
  OPTorganization = { ACM },
  abstract =     {
         We present new algorithms for inferring an unknown finite-state
         automaton from its input/output behavior \emph{in the absence of
         a means of resetting the machine to a start state}.  A key
         technique used is inference of a \emph{homing sequence} for
         the unknown automaton.
         \par
         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
         which, 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 which makes use of a diversity-based
         representation of the finite-state system.  \emph{Our algorithms
         are the first which are provably effective for these problems,
         in the absence of a ``reset.''}
         \par
         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 a roughly a factor of $D^3/\log D$.                  
                 },
}