Inference of finite automata using homing sequences

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-&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 D3/logD.

REFERENCES

• 1: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• 2: Dana Angluin. A note on the number of queries needed to identify regular languages. Injformation and Control, 51:76-87, 1981.
• 3: Dana Angluin. On the complexity of minimum inference of regular sets. Information and Control, 39:337- 350, 1978.
• 4: E. Mark Gold. Complexity of automaton identification from given data. Information and Control, 37'302-320, 1978.
• 5: E. Mark Gold. System identification via state characterization. Automatica, 8:621-636, 1972.
• 6: M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
• 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.
• 8: Zvi Kohavi , Richard W. Hamming , Edward A. Feigenbaum, Switching and Finite Automata Theory: Computer Science Series, McGraw-Hill Higher Education, 1990
• 9: L. Pitt , M. K. Warmuth, The minimum consistent DFA problem cannot be approximated within and polynomial, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.421-432, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73048]
• 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.
• 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.
• 12: R. E. Schapire, DIVERSITY-BASED INFERENCE OF FINITE AUTOMATA, Massachusetts Institute of Technology, Cambridge, MA, 1988

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

General Terms:
Algorithms, Experimentation, Theory