Local Search Heuristics for NFA State Minimization Problem

Andrey V. Tsyganov

Department of Higher Mathematics, Ulyanovsk State Pedagogical University, Ulyanovsk, Russia.

DOI: 10.4236/ijcns.2012.529074                

Abstract

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.

Keywords

Nondeterministic Finite Automata; State Minimization; Heuristics; Local Search; Parallelism

Conflicts of Interest

The authors declare no conflicts of interest.

References

[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.