R. L. Rivest
R. E. Schapire
ABSTRACT
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-δ, 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 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 D3/logD.
- 1.Dana Angluin. Learning regular sets from queries and coun terexamples. J njformation and Computation, 75:87-106, November 1987. Google Scholar
Digital Library
- 2.Dana Angluin. A note on the number of queries needed to identify regular languages. Injformation and Control, 51:76-87, 1981.Google ScholarCross Ref
- 3.Dana Angluin. On the complexity of minimum inference of regular sets. Information and Control, 39:337- 350, 1978.Google ScholarCross Ref
- 4.E. Mark Gold. Complexity of automaton identification from given data. Information and Control, 37'302-320, 1978.Google Scholar
- 5.E. Mark Gold. System identification via state characterization. Automatica, 8:621-636, 1972.Google ScholarDigital Library
- 6.Michael Kearns and Leslie G. Valiant. Cryptographic limitations on learning boolean formulae and finite automata, in Proceedings of the Twenty-First Annual A CM Symposium on Theory of Computing, Seattle, Washington, May 1989. Google ScholarDigital Library
- 7.Michael K earns and Leslie G. Vahant. Learning Boolean Formulae or Finite Automata is as Hard as Factoring. Technical Report TR 14-88, Harvard University Aiken Computation Laboratory, 1988.Google Scholar
- 8.Zvi Kohavi. Switching and Finite Automata Theory. McGraw-Hill, second edition, 1978. Google ScholarDigital Library
- 9.Leonard Pitt and M.~nfred K. Warmuth. The minimum DFA consistency problem cannot be approximated within any polynomial. In Proceedings of the Twenty-First Annual A CM Symposium on Theory of Computing, Seattle, Washington, May 1989. Google ScholarDigital Library
- 10.Leonard Pitt and Manfred K. Warmuth. Reductions among prediction problems: on the difficulty of predicting automata (extended abstract). In 3rd IEEE Conference on Structure in Commplexity Theory, pages 60-69, Washington, DC, June 1988.Google Scholar
- 11.Ronald L. Rivest and Robert E. Schapire. Diversitybased inference of finite automata. In Proceeding of the Twenty-Eighth Annual Symposium on Foundations of Computer Science, pages 78-87, Los Angeles, California, October 1987.Google Scholar
- 12.Robert E. Schapire. Diversity-Based Inference of Finite Automata. Master's thesis, MIT Lab. for Computer Science, May 1988. Technical Report MIT/LCS/TR-413. Google ScholarDigital Library
Index Terms
- Inference of finite automata using homing sequences
Recommendations
Oblivious two-way finite automata: Decidability and complexity
We investigate the descriptional complexity and decidability of obliviousness for two-way finite automata. In particular, we consider the simulation of two-way deterministic finite automata (2DFAs) by oblivious 2DFAs, the simulation of oblivious 2DFAs ...
Complementing two-way finite automata
We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, for a given automaton (2dfa) with n states, we build an automaton accepting the complement with at most 4n states, ...
Comments