Inference of finite automata using homing sequences

Ronald L. Rivest, Robert E. Schapire

Research output: Contribution to journalArticle

196 Scopus citations

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 - δ, 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/δ). 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 D3/log D.

Original languageEnglish (US)
Pages (from-to)299-347
Number of pages49
JournalInformation and Computation
Volume103
Issue number2
DOIs
StatePublished - Apr 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Inference of finite automata using homing sequences'. Together they form a unique fingerprint.

  • Cite this