ISSN 1991-2927
 

ACP № 1 (59) 2020

Parallel Algorithm for Constructing Com-automaton Using Techniques Openmp and Mpi

Andrey Vladimirovich Tsyganov, Ulyanovsk State Pedagogical University named after Ilya N. Ulyanov, Candidate of Physics and Mathematics; Associate Professor at the Chair of Higher Mathematics of Ulyanovsk State Pedagogical University named after Ilya N. Ulyanov; author of scientific publications, a monograph, teaching guides and certificates of program registration in the fields of parallel heuristic algorithms and algorithms for minimizing nondeterministic finite automata [e-mail: This email address is being protected from spambots. You need JavaScript enabled to view it. ]A. Tsyganov

Parallel Algorithm for Constructing Com-automaton Using Techniques Openmp and Mpi 30_15.pdf

Complete (COM) automaton which is one of the regular language invariants, is used in nondeterministic finite automata minimization algorithms, but the algorithm for its construction from canonical automata has an exponential complexity. One of the ways to speed up the construction of a COM-automaton is to use parallelism. In the present paper, the author considers the parallel algorithm for constructing COM-automaton using parallel programming techniques OpenMP and MPI, which is implemented in a software tool for minimizing nondeterministic finite automata called ReFaM. The author also provides a description of the algorithm and its implementation as well as the results of numerical experiments.

Nondeterministic finite automata, state minimization, complete automaton, parallelism, openmp, mpi.

© FRPC JSC 'RPA 'Mars', 2009-2018 The web-site runs on Joomla!