Article

Article title A PARALLEL ALGORITHMS FOR MINIMIZATION OF FINITE AUTOMATA FOR SUBREGULARY LANGUAGES
Authors N.I. Krayinyukov
Section SECTION V. HIGH-EFFICIENCY COMPUTING ALGORITHMS
Month, Year 06, 2012 @en
Index UDC 519.713.4
DOI
Abstract Subregular languages are a subclass of regular languages with certain properties, the most important from the point of view of applications are finite languages, the languages are closed under taking prefixes, suffixes and subwords – prefix suffix, factorial regular languages. Finite automata that recognize these languages, representing a subclass of automata, the states of finite automata have certain properties. We consider parallel algorithms for the minimization of finite automata for these languages. Parallelization is achieved by using the transition functions for each class of equivalent states. To investigate the possibilities of parallel algorithms uses a technology called MPI – Parallel processes with message passing – the most common parallel programming technology.

Download PDF

Keywords Subregular languages; parallel algorithms for minimization; finite state machines; parallel programming technologies.
References 1. Moore E.F. Gedanked-expiriments on Sequential Circuits Automata Studies // Princeton University Press. – 1956. № J. – P. 129-153.
2. Hopckoft J. An n log(n) Algorithm for Minimizing States in a Finite Automaton nа, Theory of Machines and Computations, Academic Press. – 1971. – P. 189-196.
3. Хорпкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов. Языков и исчислений. – М.: Вильямс, 2008. – 528 с.
4. Лаллеман Ж. Полугруппы и комбинаторные приложения. – М.: Мир, 1985. – 440 с.

Comments are closed.