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