The state minimization problem for nondeterministic finite automata: the parallel implementation of the truncated branch and bound method

被引：1
作者：
Melnikov, Boris [1 ]
Tsyganov, Andrey [2 ]
机构：
[1] Togliatti State Univ, Tolyatti, Russia
[2] Ulyanovsk State Pedag Univ, Ulyanovsk, Russia
来源：
2012 FIFTH INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES, ALGORITHMS AND PROGRAMMING (PAAP) | 2012年
关键词：
finite automata; nondeterminisitc automata; state minimization; parallelism; OpenMP; MPI;
D O I：
10.1109/PAAP.2012.36
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper we present an approach to the parallel implementation of the state minimization problem for nondeterministic finite automata. This approach is based on the truncated branch and bound method and also on the usage of basis and COM automata for the given language. Minimum state automata are searched as sub-automata of the COM automaton. Some sufficient conditions for their equivalence to the given nondeterministic automaton are proved in terms of the loops of the basis automaton. We suggest exact and heuristic state minimization algorithms, discuss their implementation details and provide some experimental results.
引用
收藏
页码：194 / 201
页数：8
相关论文
共 11 条
  • [1] Alba Enrique, 2007, International Journal of Innovative Computing and Applications, V1, P74, DOI 10.1504/IJICA.2007.013403
  • [2] Almeida M., 2007, TECH REP
  • [3] Gamma E., 1995, DESIGN PATTERNS ELEM
  • [4] GAP - Groups, 2008, ALG PROGR VERS 44 12
  • [5] Harary F., 1969, Graph Theory
  • [6] Melnikov B., 2005, HPC ASIA 05, P73
  • [7] Melnikov B., 2002, KOREAN J COMPUTATION, V9, P131
  • [8] Melnikov B., 2002, KOREAN J COMPUTATION, V9, P475
  • [9] Once More on the Edge-Minimization of Nondeterministic Finite Automata and the Connected Problems
    Melnikov, Boris
    [J]. FUNDAMENTA INFORMATICAE, 2010, 104 (03) : 267 - 283
  • [10] Extended Nondeterministic Finite Automata
    Melnikov, Boris
    [J]. FUNDAMENTA INFORMATICAE, 2010, 104 (03) : 255 - 265
12