Local Search Heuristics for NFA State Minimization Problem


In the present paper we introduce new heuristic methods for the state minimization of nondeterministic finite automata. These methods are based on the classical Kameda-Weiner algorithm joined with local search heuristics, such as stochastic hill climbing and simulated annealing. The description of the proposed methods is given and the results of the numerical experiments are provided.

Share and Cite:

A. V. Tsyganov, "Local Search Heuristics for NFA State Minimization Problem," International Journal of Communications, Network and System Sciences, Vol. 5 No. 9A, 2012, pp. 638-643. doi: 10.4236/ijcns.2012.529074.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] J. E. Hopcroft and J. D. Ullman, “Introduction to Automata Theory, Languages, and Computation,” Adison-Wesley Publishing Company, Reading, 1979.
[2] T. Jiang and B. Ravikumar, “Minimal NFA Problems Are Hard,” SIAM Journal on Computing, Vol. 22, No. 6, 1993, pp. 1117-1141. Hdoi:10.1137/0222067
[3] V. Kell, A. Maier, A. Potthoff, W. Thomas and U. Wermuth, “AMORE: A System for Computing Automata, Monoids and Regular Expressions,” Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science on STACS 89, Springer-Verlag, New York, 1989, pp. 537-538.
[4] M. Mohri, F. Pereira and M. Riley, “AT&T General-Purpose Finite-State Machine Software Tools,” 1997. http://www.research.att.com/sw/tools/fsm
[5] S. Lombardy, R. Poss, Y. Régis-Gianas and J. Sakarovitch, “Introducing VAUCANSON,” In: O. H. Ibarra and Z. Dang, Eds., Implementation and Application of Automata, CIAA 2003, Santa Barbara, 16-18 July 2003, pp. 96-107.
[6] S. H. Rodger, “JFLAP: An Interactive Formal Languages and Automata Package,” Jones and Bartlett Publishers, Inc., USA, 2006.
[7] T. Kameda and P. Weiner, “On the State Minimization of Nondeterministic Finite Automata,” IEEE Transactions on Computers, Vol. C-19, No. 7, 1970, pp. 617-627. Hdoi:10.1109/T-C.1970.222994
[8] J. Hromkovic, “Algorithmics for Hard Problems—Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics,” Springer, Berlin, 2001.
[9] F. Glover and G. A. Kohenberger, “Handbook of Metaheuristics,” Kluwer Academic Publishers, Boston, 2003.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.