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