Программное исследование полурешеток, связанных с автоматом Ватерлоо
Автор: Абрамян М.Э.
Статья в выпуске: 1 т.13, 2024 года.
Бесплатный доступ
Статья посвящена исследованию полурешеток, содержащих покрывающие автоматы для автомата Ватерлоо. В начальных разделах статьи описывается процесс построения покрывающих автоматов на основе подмножеств гридов исходного автомата (каждый грид представляет собой некоторое множество дуг, связанных с исходным автоматом), а также рассматриваются свойства полурешеток, образуемых покрывающими автоматами. Основным результатом статьи является полное описание полученных полурешеток с точки зрения эквивалентности входящих в них покрывающих автоматов исходному автомату Ватерлоо. Выделены три класса полурешеток, каждый из которых имеет особые свойства. Для полурешетки, построенной на базе минимального покрывающего автомата, получено графическое представление, которое позволяет наглядно отразить соотношения между ее наборами, состоящими из попарно эквивалентных автоматов. Кроме того, сформулирован критерий эквивалентности покрывающего автомата автомату Ватерлоо в терминах свойств подмножества гридов, определяющего покрывающий автомат. Исследование проводилось с применением библиотеки NFALib для анализа недетерминированных конечных автоматов, реализованной автором на языке C#. Актуальность изучения автомата Ватерлоо связана с его ролью в исследовании задачи вершинной минимизации недетерминированных конечных автоматов и разработке эвристических алгоритмов реального времени, используемых для ее решения.
Недетерминированные конечные автоматы, универсальный автомат, грид, покрывающий автомат, алгоритмы эквивалентного преобразования, автомат ватерлоо
Короткий адрес: https://sciup.org/147243208
IDR: 147243208 | DOI: 10.14529/cmse240101
Список литературы Программное исследование полурешеток, связанных с автоматом Ватерлоо
- Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1973. 301 с.
- Брауэр В. Введение в теорию конечных автоматов. М.: Радио и связь, 1987. 390 с.
- Мельников Б. Регулярные языки и недетерминированные конечные автоматы. М.: Изд-во Российского государственного социального университета, 2018. 179 с.
- Долгов В., Мельников Б., Мельникова А. Циклы графа переходов базисного конечного автомата и связанные вопросы // Вестник Воронежского государственного университета. Серия: Физика. Математика. 2016. № 4. С. 95-111.
- Долгов В., Мельников Б. Построение универсального конечного автомата. II. Примеры работы алгоритмов // Вестник Воронежского государственного университета. Серия: Физика. Математика. 2014. № 1. С. 78-85.
- Melnikov В., Melnikova A. Edge-minimization of non-deterministic finite automata // The Korean Journal of Computational and Applied Mathematics (Journal of Computational and Applied Mathematics). 2001. Vol. 8, no. 3. P. 469-479.
- Jiang Т., Ravikumar B. Minimal NFA problems are hard // SIAM Journal on Computing. 1993. Vol. 22, no. 6. P. 1117-1141. DOI: 10.1137/0222067.
- Мельников Б.Ф. Полурешетки подмножеств потенциальных корней в задачах теории формальных языков. Часть I. Извлечение корня из языка // International Journal of Open Information Technologies. 2022. T. 10, № 4. C. 1-9.
- Мельников Б.Ф. Полурешетки подмножеств потенциальных корней в задачах теории формальных языков. Часть II. Построение инверсного морфизма // International Journal of Open Information Technologies. 2022. T. 10, № 5. C. 1-8.
- Мельников Б.Ф. Полурешетки подмножеств потенциальных корней в задачах теории формальных языков. Часть III. Условие существования решетки // International Journal of Open Information Technologies. 2022. T. 10, № 7. C. 1-9.
- Зяблицева JI.В., Корабелыцикова С.Ю., Абрамян М.Э. Графы полурешеток, матричные представления полугрупп идемпотентов и полурешетки автомата Ватерлоо / / International Journal of Open Information Technologies. 2023. T. 11, № 7. C. 69-76.
- Abramyan M.E., Melnikov B.F. A Program Study of the Union of Semilattices on the Set of Subsets of Grids of Waterloo Language // Journal of Applied Mathematics and Physics. 2023. Vol. 11. P. 1459-1470. DOI: 10.4236/jamp.2023.115095.
- Kameda Т., Weiner P. On the state minimization of nondeterministic finite automata // IEEE Transactions on Computers. 1970. Vol. C-19, no. 7. P. 617-627. DOI: 10.1109/t-c.1970.222994.
- Абрамян М.Э. О вычислении веса подзадач при вершинной минимизации недетерминированных конечных автоматов методом ветвей и границ // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. 2021. № 2 (58). С. 46-52. DOI: 10.21685/2072-3040-2021-2-4.
- Melnikov В. The complete finite automaton // International Journal of Open Information Technologies. 2017. Vol. 5, no. 10. P. 9-17.
- Polak L. Minimalizations of NFA using the universal automaton // International Journal of Foundation of Computer Science. 2005. Vol. 16, no. 5. P. 999-1010. DOI: 10.1142/s0129054105003431.
