Local Search Heuristics for NFA State Minimization Problem

• 作者: Andrey V. Tsyganov
• 来源期刊: 通讯、网络与系统学国际期刊(英文)
• 学科: 工学
• 关键词: Nondeterministic Finite AUTOMATA STATE MINIMIZATION HEURISTICS Local Search PARALLELISM
• 年，卷（期）: 2012,（9）
• 页码范围: 638-643
• 页数: 6页
• 分类号: TP39

摘要

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.