Статья

Название статьи ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ МИНИМИЗАЦИИ КОНЕЧНЫХ АВТОМАТОВ ДЛЯ СУБРЕГУЛЯРНЫХ ЯЗЫКОВ
Автор Н.И. Крайнюков
Рубрика РАЗДЕЛ V. ВЫСОКОПРОИЗВОДИТЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ
Месяц, год 06, 2012
Индекс УДК 519.713.4
DOI
Аннотация Субрегулярные языки – это подклассы регулярных языков, обладающие определенными свойствами, например к наиболее важным, с точки зрения приложений относятся конечные языки, языки замкнутые относительно взятия префиксов, суффиксов и подслов – префиксные суффиксные, факториальные регулярные языки. Конечные автоматы, распознающие эти языки, представляют более узкий класс автоматов, состояния, таких конечных автоматов обладают определенными свойствами. Рассматриваются параллельные алгоритмы минимизации конечных автоматов для таких языков. Распараллеливание достигается применением функции перехода для каждого класса эквивалентных состояний. Для исследования возможностей параллельных алгоритмов используется технология MPI – параллельные процессы с передачей сообщений – наиболее распространенная технология параллельного программирования.

Скачать в PDF

Ключевые слова Субрегулярные языки; параллельные алгоритмы минимизации; конечные автоматы; технологии параллельного программирования.
Библиографический список 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.