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 [email:
This email address is being protected from spambots. You need JavaScript enabled to view it.
]A. Tsyganov


Parallel Algorithm for Constructing Comautomaton Using Techniques Openmp and Mpi
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 COMautomaton is to use parallelism. In the present paper, the author considers
the parallel algorithm for constructing COMautomaton 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.

