Abstract
This work describes algorithms for the inference of minimum size deterministic automata consistent with a labeled training set. The algorithms presented represent the state of the art for this problem, known to be computationally very hard.
In particular, we analyze the performance of algorithms that use implicit enumeration of solutions and algorithms that perform explicit search but incorporate a set of techniques known as dependency directed backtracking to prune the search tree effectively.
We present empirical results that show the comparative efficiency of the methods studied and discuss alternative approaches to this problem, evaluating their advantages and drawbacks.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Angluin, D. (1978). On the complexity of minimum inference of regular sets. Inform. Control, 39:3, 337–350.
Angluin, D. (1987). Learning regular sets from queries and counterexamples. Inform. Comput., 75:2, 87–106.
Biermann, A.W.,& Feldman, J. A. (1972). On the synthesis of finite-state machines from samples of their behavior. IEEE Transactions on Computers, 21, 592–597.
Biermann, A. W.,& Petry, F. E. (1975). Speeding up the synthesis of programs from traces. IEEE Trans. on Computers, C-24, 122–136.
Blumer, A., Ehrenfeucht, A., Haussler, D.,& Warmuth, M. K. (1986). Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension. In Proc. 19th Annu. ACM Sympos. Theory Comput. (pp. 273–282).
Blumer, A., Ehrenfeucht, A., Haussler, D.,& Warmuth, M. K. (1987). Occam's razor. Inform. Proc. Lett., 24, 377–380.
Bryant, R. E. (1986). Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 35, 677–691.
Carraghan, R.,& Pardalos, P. M. (1990). An exact algorithm for the maximum clique problem. Operations Research Letters, 9, 375–382.
Coste, F.,& Nicolas, J. (1998). How considering incompatible state mergings may reduce the DFA induction search tree. In Fourth International Colloquium on Grammatical Inference (ICGI-98) (pp. 199–210). volume. 1433 of Lecture Notes in Computer Science.
Coudert, O., Berthet, C.,& Madre, J. C. (1989).Verification of synchronous sequential machines based on symbolic execution. In Sifakis, J., (Ed.), Proceedings of the Workshop on Automatic Verification Methods for Finite State Systems (pp. 365–373). Springer-Verlag, volume 407 of Lecture Notes in Computer Science.
Davis, M.,& Putnam, H. (1960). A computing procedure for quantification theory. Journal of the Association for Computing Machinery, 7:3, 201–215.
de Kleer, J. (1986). An assumption-based TMS. Artificial Intelligence, 28:2, 127–162.
Garey, M.,& Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York.
Giles, C. L., Miller, C. B., Chen, D., Chen, H. H., Sun, G. Z.,& Lee, Y. C. (1992). Learning and extracting finite state automata with second-order recurrent neural networks. Neural Computation, 4, 393–405.
Gold, E. M. (1972). System identification via state characterization. Automatica, 8, 621–636.
Gold, E. M. (1978). Complexity of automaton identification from given data. Inform. Control, 37, 302–320.
Horne, B. G.,& Giles, C. L. (1995). Advances in Neural Information Processing Systems (Vol. 7) (pp. 697–704). MIT Press.
Juillé, H.,& Pollack, J. B. (1998). A stochastic search approach for grammar induction. In Proceedings of the 1998 International Colloquium on Grammatical Inference (ICGI-98) (pp. 126–137). Lecture Notes in Computer Science.
Kam, T.,& Brayton, R. K. (1990). Multi-valued decision diagrams. Tech. Report No. UCB/ERL M90/125.
Kam, T., Villa, T., Brayton, R.,& Sangiovanni-Vincentelli, A. (1994). A fully implicit algorithm for exact state minimization. In Proc. of the ACM/IEEE Design Automation Conference (pp. 684–690). ACM Press.
Kunz, M. H.,& Pradhan, D. K. (1992). Recursive learning: an attractive alternative to the decision tree for test generation in digital circuits. In Proceedings of the International Test Conference (pp. 816–825).
Lang, K. J. (1992). Random DFA's can be approximately learned from sparse uniform examples. In Proc. 5th Annu. Workshop on Comput. Learning Theory (pp. 45–52). New York, NY: ACM Press.
Lang, K. J., Pearlmutter, B. A.,& Price, R. (1998). Results of the Abbadingo One DFA learning competition and a new evidence driven state merging algorithm. In Fourth International Colloquium on Grammatical Inference (ICGI-98) (pp. 1–12). volume 1433 of Lecture Notes in Computer Science.
Li, M.,& Vitányi, P. M. B. (1994). An Introduction to Kolmogorov Complexity. Addison-Wesley, MA.
Oliveira, A. L., Carloni, L., Villa, T., and Vincentelli, A. S. (1998). Exact minimization of binary decision diagrams using implicit techniques. IEEE Transactions on Computers, 47:11, 1282–1296.
Oliveira, A. L.,& Edwards, S. (1996). Limits of exact algorithms for inference of minimum size finite state machines. In Proceedings of the Seventh Workshop on Algorithmic Learning Theory (pp. 59–66). Sydney, Australia: Springer-Verlag. number 1160 in Lecture Notes in Artificial Intelligence.
Oliveira, A. L.,& Silva, J. P. M. (1998). Efficient search techniques for the inference of minimum size finite automata. In Proceedings of the Fifth String Processing and Information Retrieval Symposium (pp. 81–89). IEEE Computer Press.
Oncina, J.,& Garcia, P. (1992). Inferring regular languages in polynomial update time. In Pattern recognition and image analysis (pp. 49–61). World Scientific.
Pearl, J. (1978). On the connection between the complexity and credibility of inferred models. Journal of General Systems, 4, 255–264.
Pena, J. G.,& Oliveira, A. L. (1998). A new algorithm for the reduction of incompletely specified finite state machines. In Proc. of the ACM/IEEE International Conference on Computer Aided Design (pp. 482–489), San Jose: IEEE Computer Society Press.
Pfleeger, C. F. (1973). State reduction in incompletely specified finite state machines. IEEE Trans. Computers, C-22, 1099–1102.
Pitt, L.,& Warmuth, M. (1993). The minimum consistent DFA problem cannot be approximated within any polynomial. J. ACM, 40:1, 95–142.
Pollack, J. B. (1991). The induction of dynamical recognizers. Machine Learning, 7, 123–148.
Porat, S.,& Feldman, J. A. (1988). Learning automata from ordered examples. In Proc. 1st Annu. Workshop on Comput. Learning Theory (pp. 386–396). San Mateo, CA: Morgan Kaufmann.
Russel, S.,& Norvig, P. (1996). Artificial Intelligence: A Modern Approach. Prentice-Hall.
Schapire, R. E. (1992). The Design and Analysis of Efficient Learning Algorithms. Cambridge, MA: MIT Press.
Silva, J. P. M. (1995). Search Algorithms for Satisfiability Problems in Combinational Switching Circuits. PhD thesis, University of Michigan.
Silva, J. P. M.,& Sakallah, K. (1996).GRASP—A new search algorithm for satisfiability. In Proc. of the ACM/IEEE International Conference on Computer Aided Design (pp. 220–227). IEEE Computer Society Press.
Stallman, R. M.,& Sussman, G. J. (1977). Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis. Artificial Intelligence, 9, 135–196.
Trakhtenbrot, B. A.,& Barzdin, Y. M. (1973). Finite Automata. Amsterdam: North-Holland.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Oliveira, A.L., Silva, J.P. Efficient Algorithms for the Inference of Minimum Size DFAs. Machine Learning 44, 93–119 (2001). https://doi.org/10.1023/A:1010828029885
Issue Date:
DOI: https://doi.org/10.1023/A:1010828029885