inference of finite automata using homing sequences
We present new algorithms for inferring an unknown finite-state automaton from its input/output behavior 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 which, with probability 1-&dgr;, 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/ &dgr; ). We present an analogous algorithm which 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 .
inference finite automata automata use sequence algorithm input behavior procedure experience timing structure learning probability polynomial size log diversity representation systems effect probabilistic algorithm permutation factor