Программное исследование полурешеток, связанных с автоматом Ватерлоо
Автор: Абрамян М.Э.
Статья в выпуске: 1 т.13, 2024 года.
Бесплатный доступ
Статья посвящена исследованию полурешеток, содержащих покрывающие автоматы для автомата Ватерлоо. В начальных разделах статьи описывается процесс построения покрывающих автоматов на основе подмножеств гридов исходного автомата (каждый грид представляет собой некоторое множество дуг, связанных с исходным автоматом), а также рассматриваются свойства полурешеток, образуемых покрывающими автоматами. Основным результатом статьи является полное описание полученных полурешеток с точки зрения эквивалентности входящих в них покрывающих автоматов исходному автомату Ватерлоо. Выделены три класса полурешеток, каждый из которых имеет особые свойства. Для полурешетки, построенной на базе минимального покрывающего автомата, получено графическое представление, которое позволяет наглядно отразить соотношения между ее наборами, состоящими из попарно эквивалентных автоматов. Кроме того, сформулирован критерий эквивалентности покрывающего автомата автомату Ватерлоо в терминах свойств подмножества гридов, определяющего покрывающий автомат. Исследование проводилось с применением библиотеки NFALib для анализа недетерминированных конечных автоматов, реализованной автором на языке C#. Актуальность изучения автомата Ватерлоо связана с его ролью в исследовании задачи вершинной минимизации недетерминированных конечных автоматов и разработке эвристических алгоритмов реального времени, используемых для ее решения.
Недетерминированные конечные автоматы, универсальный автомат, грид, покрывающий автомат, алгоритмы эквивалентного преобразования, автомат ватерлоо
Короткий адрес: https://sciup.org/147243208
IDR: 147243208 | УДК: 004.021, | DOI: 10.14529/cmse240101
A program study of semilattices connected with the Waterloo automaton
The paper is devoted to the study of semilattices containing covering automata for the Waterloo automaton. In the initial sections of the paper, the process of constructing covering automata on the basis of subsets of the grids of the original automaton is described (each grid represents some set of arcs associated with the original automaton), and also the properties of semilattices formed by covering automata are considered. The main result of the paper is a complete description of the obtained semilattices from the point of view of equivalence of the covering automata included in them to the original Waterloo automaton. Three classes of semilattices are distinguished, each of which has special properties. For the semilattice constructed on the basis of a minimal covering automaton, a graphical representation is obtained, which allows us to visualize the relations between its sets consisting of pairwise equivalent automata. In addition, a criterion of equivalence of the covering automaton to the Waterloo automaton is formulated in terms of the properties of the subset of grids defining the covering automaton. The study was carried out using the NFALib library for analysis of nondeterministic finite automata, implemented by the author in the C# language. The relevance of the study of the Waterloo automaton is connected with its role in the study of the problem of vertex minimization of nondeterministic finite automata and the development of real-time heuristic algorithms used for its solution.
Список литературы Программное исследование полурешеток, связанных с автоматом Ватерлоо
- Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 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.
