Parallel Algorithms for NFA State Minimization Problem

This talk will start with an introduction, where we present the Laboratory of Mathematical Modeling which was recently established in Ulyanovsk State Pedagogical University. The report will cover its hardware and software facilities and main areas of conducted research: cosmology, molecular biology, combinatorial optimization, parameter identification. Then we will switch to the main subject of the talk. We consider the state minimization problem for nondeterministic finite automata (NFA) which is known to be computationally hard (PSPACE-complete) and introduce ReFaM – a software tool for its solution. This software tool provides a number of parallel algorithms: parallel versions of exact Kameda- Weiner and Melnikov methods as well as their hybrids with popular metaheurstics (genetic algorithm, simulated annealing, etc.). All parallel algorithms are implemented using MPI and OpenMP techniques. We discuss the implementation details and provide the results of numerical experiments