ПОСТРОЕНИЕ БАЗИСНЫХ И ПОЛНЫХ АВТОМАТОВ В ПРОГРАММЕ ReFaM

  • Андрей Владимирович Цыганов
Ключевые слова: недетерминированные конечные автоматы, вершинная минимизация, базисный автомат, полный автомат, параллелизм, OpenMP, MPI

Аннотация

Базисный и полный автоматы являются инвариантами регулярного языка, применяющимися в алгоритмах минимизации недетерминированных конечных автоматов. В данной статье рассматриваются алгоритмы построения базисных и полных автоматов, реализованные в программе для минимизации недетерминированных конечных автоматов ReFaM. Приводятся описания алгоритмов и результаты численных экспериментов.

Литература

1. Мельников Б.Ф. Недетерминированные конечные автоматы. Тольятти: Изд-во ТГУ, 2009. 160 с.
2. Polák L., Minimalizations of NFA using the universal automaton // Int. J. Found. Comput. Sci., vol. 16, no. 5, pp. 999–1010, 2005.
3. Kell V., Maier A., Potthoff A. et al. AMORE: a system for computing automata, monoids and regular expressions // Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science on STACS 89. New York, NY, USA: Springer-Verlag New York, Inc., 1989. Pp. 537–538.
4. Mohri M., Pereira F., Riley M. AT&T General-purpose finite-state machine software tools.
5. Raymond D.,Wood D. Grail: Engineering Automata in C++: Tech. Rep. HKUST-CS96-24: Hong Kong University of Science and Technology, 1996.
6. Lombardy S., Poss R., Régis-Gianas Y., Sakarovitch J. Introducing VAUCANSON // Implementation and Application of Automata, 8th International Conference, CIAA 2003, Santa Barbara, California, USA, July 16-18, 2003, Proceedings / Ed. by O. H. Ibarra, Z. Dang. Vol. 2759 of Lecture Notes in Computer Science. Springer, 2003. Pp. 96–107.
7. Rodger S.H. JFLAP: An Interactive Formal Languages and Automata Package. USA: Jones and Bartlett Publishers, Inc., 2006. ISBN: 0763738344.
8. Гергель В.П. Высокопроизводительные вычисления дл многоядерных многопроцессорных систем. Учебное пособие. Нижний Новгород: Изд-во ННГУ им. Н. И. Лоба¬чевского, 2010.
9. Гергель В.П. Теория и практика параллельных вычислений. Изд-во Бином. Лаборатория знаний, Интернет-университет информационных технологий, 2007. 424 с.
10. Цыганов А.В., Булычов О.И. HeO: библиотека метаэвристик для задач дискретной оптимизации // Программные продукты и системы. 2009. № 4. С. 148–151.
11. Chase P.J. Algorithm 382: Combinations of M out of N Objects [G6] // Communications of the Association for Computing Machinery 13:6:368, 1970.
Выпуск
Раздел
Естественные науки

Наиболее читаемые статьи этого автора (авторов)