Research ArticleOpen AccessGoogle Scholar indexed
Local Search Heuristics for NFA State Minimization Problem
Department of Higher Mathematics, Ulyanovsk State Pedagogical University, Ulyanovsk, Russia
- 1 Department of Higher Mathematics, Ulyanovsk State Pedagogical University, Ulyanovsk, Russia
International Journal of Communications, Network and System Sciences·Volume 05 (2012)·Pages 638–643·Published 18 September 2012·DOI10.4236/ijcns.2012.529074
Copy link · social · email
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.
KeywordsNondeterministic Finite AutomataState MinimizationHeuristicsLocal SearchParallelism
- J. E. Hopcroft and J. D. Ullman, “Introduction to Automata Theory, Languages, and Computation,” Adison-Wesley Publishing Company, Reading, 1979.
- 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
- 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.
- 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
- 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.
- S. H. Rodger, “JFLAP: An Interactive Formal Languages and Automata Package,” Jones and Bartlett Publishers, Inc., USA, 2006.
- 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
- J. Hromkovic, “Algorithmics for Hard Problems—Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics,” Springer, Berlin, 2001.
- F. Glover and G. A. Kohenberger, “Handbook of Metaheuristics,” Kluwer Academic Publishers, Boston, 2003.