Diversity-based inference of finite automata

ABSTRACT

We present new procedures for inferring the structure of a finite-state automaton (FSA) from its input/output behavior, using access to the automaton to perform experiments. Our procedures use a new representation for finite automata, based on the notion of equivalence between tests. We call the number of such equivalence classes the diversity of the automaton; the diversity may be as small as the logarithm of the number of states of the automaton. For the special class of permutation automata, we describe an inference procedure that runs in time polynomial in the diversity and log(1/&dgr;), where &dgr; is a given upper bound on the probability that our procedure returns an incorrect result. (Since our procedure uses randomization to perform experiments, there is a certain controllable chance that it will return an erroneous result.) We also discuss techniques for handling more general automata. We present evidence for the practical efficiency of our approach. For example, our procedure is able to infer the structure of an automaton based on Rubik's Cube (which has approximately 1019 states) in about 2 minutes on a DEC MicroVax. This automaton is many orders of magnitude larger than possible with previous techniques, which would require time proportional at least to the number of global states. (Note that in this example, only a small fraction (10-14) of the global states were even visited.) Finally, we present a new procedure for inferring automata of a special type in which the global state is composed of a vector of binary local state variables, all of which are observable (or visible) to the experimenter. Our inference procedure runs provably in time polynomial in the size of this vector (which happens to be the diversity of the automaton), even though the global state space may be exponentially larger. The procedure plans and executes experiments on the unknown automaton; we show that the number of input symbols given to the automaton during this process is (to within a constant factor) the best possible.

REFERENCES

• 1: ~ANGLUIN, D. 1978. On the complexity of mlmmum inference of regular sets. Inf. Cont. 39, ~337-350.
• 2: Dana Angluin, Inference of Reversible Languages, Journal of the ACM (JACM), v.29 n.3, p.741-765, July 1982 [doi>10.1145/322326.322334]
• 3: 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]
• 4: ~ANGLUIN, m. 1987b. A note on diversity. Unpublished manuscript.
• 5: ~BAINBR1DGE, E. S. 1977. The fundamental duality of system theory. In Systems: .4pproaches, ~Theones, Apphcattons, W. E. Hartnett, Ed. Reidel, Dordrecht, Holland, pp. 45-61
• 6: ~BERMAN, A. AND PLEMMONS, R. J. 1979. Nonnegatwe 3lattices m the Mathematical Sciences. ~Academic Press, Orlando, Fla.
• 7: ~CORMEN, T. H., LEiSERSON, C. E., AND RIVEST, R. L. 1990. hztroductton to/t{gortthms. MIT ~Press, Cambridge, Mass.
• 8: ~DEAN, T., ANGLUIN, D., BASYE, K., ENGELSON, S., KAELBLING, L., KOKKEVIS, E., AND MARON, O. ~1992. Inferring finite automata with stochastic output functions and an application to map ~learning. In Proceedings of the lOth Natzoua/ Confereuce on ,4rtificial bztelhgence (July). MIT ~Press, Cambridge, Mass., pp. 208-214.
• 9: Gary L. Drescher, Genetic AI: Translating Piaget into LISP, Massachusetts Institute of Technology, Cambridge, MA, 1986
• 10: ~DRESCHER, G. L. 1987. A mechanism for early Piagetian learning. In Proceedings of AAAI-87.' ~Sixth National Conference on Artificial Intelligence (Seattle, Wash., July). Morgan-Kaufmann, San ~Mateo, Calif., pp. 290-294.
• 11: ~FIEDLER, M. 1972. Bounds for eigenvalues of doubly stochastic matrices. Lin..4lg Appl. 5, 3 ~(July), 299-310.
• 12: ~F1LL, J. A. 1991. Eigenvalue bounds on convergence to stationarity for nonreversible Markov ~ chains, with an apphcation to the exclusion process. Ann Applied Prob. l, 1, 62-87.
• 13: ~FRANKLIN, J. N. 1968. Matrix Theory. Prentice-Hall, Englewood Cliffs, N.J.
• 14: ~GOLD, E. M. 1967. Language identification in the limit, h~f. Cont. 10, 447-474.
• 15: ~GOLD, E. M. 1972. System identification via state characterization. Autornattca, 8, 621 636.
• 16: ~GOLD, E. M. 1978. Complexity of automaton identification from given data. Inf. Cont. 37, ~302-320.
• 17: Juris Hartmanis, Algebraic structure theory of sequential machines (Prentice-Hall international series in applied mathematics), Prentice-Hall, Inc., Upper Saddle River, NJ, 1966
• 18: Michael Kearns , Leslie Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM (JACM), v.41 n.1, p.67-95, Jan. 1994 [doi>10.1145/174644.174647]
• 19: ~KOHAVL Z. 1978. Swztchzng and Fintte Automata Theoo,. McGraw-Hill, New York.
• 20: ~LOV/SZ, L. 1979. Combbmtorial Problems and Exercises. North-Holland, Amsterdam, The ~Netherlands.
• 21: Leonard Pitt, Inductive Inference, DFAs, and Computational Complexity, Proceedings of the International Workshop on Analogical and Inductive Inference, p.18-44, October 01-06, 1989
• 22: Leonard Pitt , Manfred K. Warmuth, The minimum consistent DFA problem cannot be approximated within any polynomial, Journal of the ACM (JACM), v.40 n.1, p.95-142, Jan. 1993 [doi>10.1145/138027.138042]
• 23: Leonard Pitt , Manfred K. Warmuth, Prediction-preserving reducibility, Journal of Computer and System Sciences, v.41 n.3, p.430-467, Dec. 1990 [doi>10.1016/0022-0000(90)90028-J]
• 24: R. L. Rivest , R. E. Schapire, Inference of finite automata using homing sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.411-420, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73047]
• 25: ~ DE SAINT-EXUPERY, A. 1943. The Little Prfi~ce. Harcourt, Brace, & World, New York.
• 26: Robert E. Schapire, The design and analysis of efficient learning algorithms, MIT Press, Cambridge, MA, 1992
• 27: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 28: ~TRAKHTENBROT, B. A., AND BARZDIN', YA. M. 1973. Finite Automata: Behacior and Synthesis. ~North-Holland, Amsterdam, The Netherlands.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction; Concept learning

General Terms:
Algorithms, Experimentation, Theory

Keywords:
diversity-based representation, finite automata, inductive inference, learning theory, permutation automata