Local Search Heuristics for NFA State Minimization Problem - International Journal of Communications, Network and System Sciences

IJCNS > Vol.5 No.9, September 2012

International Journal of Communications, Network and System Sciences

Volume 5, Issue 9 (September 2012)

ISSN Print: 1913-3715 ISSN Online: 1913-3723

Google-based Impact Factor: 0.66 Citations h5-index & Ranking

Local Search Heuristics for NFA State Minimization Problem ()

HTML

Download as PDF (Size: 89KB) PP. 638-643

DOI: 10.4236/ijcns.2012.529074 4,792 Downloads 7,366 Views Citations

Author(s)

Andrey V. Tsyganov

Affiliation(s)

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

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

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.

Cited by

[1]	Pattern Matching auf FPGAs
	2016

[2]	ГРАФИЧЕСКИЙ ИНТЕРФЕЙС ПОЛЬЗОВАТЕЛЯ ДЛЯ ПРОГРАММЫ МИНИМИЗАЦИИ НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ ReFaM
	2015

[3]	LR Rotation Rule for Creating Minimal NFA
	2015

[4]	A New NFA Reduction Algorithm for State Minimization Problem
	2015