Программное исследование полурешеток, связанных с автоматом Ватерлоо

Михаил Эдуардович Абрамян

Аннотация


Статья посвящена исследованию полурешеток, содержащих покрывающие автоматы для автомата Ватерлоо. В начальных разделах статьи описывается процесс построения покрывающих автоматов на основе подмножеств гридов исходного автомата (каждый грид представляет собой некоторое множество дуг, связанных с исходным автоматом), а также рассматриваются свойства полурешеток, образуемых покрывающими автоматами. Основным результатом статьи является полное описание полученных полурешеток с точки зрения эквивалентности входящих в них покрывающих автоматов исходному автомату Ватерлоо. Выделены три класса полурешеток, каждый из которых имеет особые свойства. Для полурешетки, построенной на базе минимального покрывающего автомата, получено графическое представление, которое позволяет наглядно отразить соотношения между ее наборами, состоящими из попарно эквивалентных автоматов. Кроме того, сформулирован критерий эквивалентности покрывающего автомата автомату Ватерлоо в терминах свойств подмножества гридов, определяющего покрывающий автомат. Исследование проводилось с применением библиотеки NFALib для анализа недетерминированных конечных автоматов, реализованной автором на языке C#. Актуальность изучения автомата Ватерлоо связана с его ролью в исследовании задачи вершинной минимизации недетерминированных конечных автоматов и разработке эвристических алгоритмов реального времени, используемых для ее решения.

Ключевые слова


недетерминированные конечные автоматы; универсальный автомат; грид; покрывающий автомат; алгоритмы эквивалентного преобразования; автомат Ватерлоо

Полный текст:

PDF

Литература


Ginsburg S. The mathematical theory of context-free languages. Moscow: Mir Publ., 1973. 301 p. (in Russian)

Brauer W. Introduction in the Finite Automata Theory. Moscow: Radio I Svyaz Publ., 1987. 390 p. (in Russian)

Melnikov B. Regular languages and nondeterministic finite automata: a monograph. Moscow: RGSU Publ., 2018. 179 p. (in Russian)

Dolgov V., Melnikov B., Melnikova A. The loops of the basis finite automaton and the connected questions. Bulletin of the Voronezh State University. Series: Physics. Mathematics. 2016. No. 4. P. 95–111. (in Russian)

Dolgov V., Malnikov B. Construction of universal finite automaton. II. Examples of algorithms functioning. Bulletin of the Voronezh State University. Series: Physics. Mathematics. 2014. No. 1. P. 78–85. (in Russian)

Melnikov B., 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. DOI: 10.1007/bf02941980.

Jiang T., Ravikumar B. Minimal NFA problems are hard. SIAM Journal on Computing. 1993. Vol. 22, no. 6. P. 1117–1141. DOI: 10.1137/0222067.

Melnikov B.F. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part I. Extracting the root from the language. International Journal of Open Information Technologies. 2022. Vol. 10, no. 4. P. 1–9. (in Russian)

Melnikov B.F. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part II. Constructing an inverse morphism. International Journal of Open Information Technologies. 2022. Vol. 10, no. 5. P. 1–8. (in Russian)

Melnikov B.F. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part III. The condition for the existence of a lattice. International Journal of Open Information Technologies. 2022. Vol. 10, no. 7. P. 1–9. (in Russian)

Zyablitceva L.V., Korabelshchikova S.Yu., Abramyan M.E. Semilattice graphs, matrix representations of idempotent semigroups andWaterloo automaton semilattices. International Journal of Open Information Technologies. 2023. Vol. 11, no. 7. P. 69–76. (in Russian)

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 T., 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.

Abramyan M.E. Computing the weight of subtasks in state minimization of nondeterministic finite automata by the branch and bound method. University proceedings. Volga region. Physical and mathematical sciences. 2021. No. 2 (58). P. 46–52. (in Russian). DOI: 10.21685/2072-3040-2021-2-4.

Melnikov B. 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.




DOI: http://dx.doi.org/10.14529/cmse240101