Программное исследование объединения полурешёток на множестве подмножеств гридов языка Ватерлоо
Аннотация
Актуальность. Актуальность рассматриваемой предметной области обусловлена необходимостью исследования множества регулярных языков и, в частности, описания различных их подклассов. Также актуальны задачи, которые могут возникать в некоторых подклассах. Это даст, среди прочего, возможность описания новых алгоритмов эквивалентного преобразования недетерминированных конечных автоматов.
Цель исследования. Целью является исследование множества подмножеств гридов языка Ватерлоо с точки зрения абстрактной алгебры.
Материалы и методы. Исследование проводилось с применением библиотеки для работы с недетерминированными конечными автоматами NFALib, реализованной одним из авторов на языке C#, а также статистических методов анализа алгоритмов.
Результаты. Результатами являются закономерности, полученные при рассмотрении полурешёток на множестве подмножеств гридов языка Ватерлоо.
Выводы. Из полученных результатов следует, что минимальный покрывающий автомат, эквивалентный автомату Ватерлоо, можно получить, добавив к минимальному покрывающему множеству гридов один дополнительный. Проведённые расчёты также показывают, что кроме минимального покрывающего автомата можно получить ещё 4 минимальных покрывающих автомата, эквивалентных исходному автомату Ватерлоо, однако для получения каждого из них необходимо заменить 1 или 2 грида, входящих в минимальное покрывающее множество.
Литература
2. Dolgov V.N., Melnikov B.F., Melnikova A.A. The loops of the basis finite automaton and the connected questions. Proceedings of Voronezh State University. Series: Physics. Mathematics. 2016;(4):95-111. (In Russ., abstract in Eng.) EDN: WYMNXF
3. Polák L. Minimalizations of NFA using the universal automaton. International Journal of Foundation of Computer Science. 2005;16(05):999-1010. https://doi.org/10.1142/S0129054105003431
4. Lombardy S., Sakarovitch J. The Universal Automaton. In: Flum J., Grädel E., Wilke T. (eds.) Logic and Automata: History and Perspectives. Texts in Logic and Games. Vol. 2. Amsterdam University Press; 2007. p. 467-514. Available at: https://perso.telecom-paristech.fr/jsaka/PUB/Files/TUA.pdf (accessed 08.09.2023).
5. Zubova M.A., Melnikov B.F. On algorithm of constructing Conway s universal automaton. Proceedings of Voronezh State University. Series: Physics. Mathematics. 2012;(1):135-137. (In Russ., abstract in Eng.) EDN: NMFEYH
6. Dolgov V.N., Melnikov B.F. Construction of universal finite automaton. II. Examples of algorithms functioning. Proceedings of Voronezh State University. Series: Physics. Mathematics. 2014;(1):78-85. (In Russ., abstract in Eng.) EDN: SBHVZH
7. Melnikov B.F., Melnikova A.A. Edge-minimization of non-deterministic finite automata. Korean Journal of Computational & Applied Mathematics. 2001;8(3):469-479. https://doi.org/10.1007/BF02941980
8. Melnikov B.F., Melnikova A.A. Multi-aspect minimization non-deterministic finite automata (Part I. Supporting facts and algorithms). University proceedings. Volga region. Physical and mathematical sciences. 2011:(4):59-69. (In Russ., abstract in Eng.) EDN: NDWBHK
9. Abramyan M.E., Melnikov B.F., Melnikova E.A. Finite Automata Table: A Science Project for High School Students. Kompjuternye instrumenty v obrazovanii = Computer Tools in Education journal. 2019;(2):87-107. (In Russ., abstract in Eng.) https://doi.org/10.32603/2071-2340-2019-2-86-107
10. Brosalina A., Melnikov B. Commutation in Global Supermonoid of Free Monoids. Informatica. 2000;11(4):353-370. https://doi.org/10.3233/INF-2000-11401
11. Melnikov B.F. Petal (Semi-Flower) Finite Automata: Basic Definitions, Examples and their Relation to Complete Automata. Part I. International Journal of Open Information Technologies. 2022;10(9):1-11. (In Russ., abstract in Eng.) EDN: MARYFR
12. Melnikov B.F. Petal (Semi-Flower) Finite Automata: Basic Definitions, Examples and their Relation to Complete Automata. Part II. International Journal of Open Information Technologies. 2022;10(9):1-11. (In Russ., abstract in Eng.) EDN: CPJNGM
13. Dolgov V.N., Melnikov B.F. On Algorithms of Automatic Construction of Waterloo-Like Finite Automata on the Basis of Full Automata. Heuristic Algorithms and Distributed Computing. 2014;1(4):24-45. (In Russ., abstract in Eng.) EDN: SYEHCT
14. Melnikov B.F., Vakhitova A.A. Some more on the finite automata. Korean Journal of Computational & Applied Mathematics. 1998;5(3):495-505. https://doi.org/10.1007/BF03008877
15. Melnikov B.F., Sciarini-Guryanova N.V. Possible edges of a finite automaton defining a given regular language. Korean Journal of Computational & Applied Mathematics. 2002;9(2):475-485. https://doi.org/10.1007/BF03021555
16. Melnikov B.F. The complete finite automaton. International Journal of Open Information Technologies. 2017;5(10):9-17. EDN: ZISOBN
17. Melnikov B.F., Melnikova E.A. Waterloo-Like Finite Automata and Algorithms for their Automatic Construction. International Journal of Open Information Technologies. 2017;5(12):8-15. EDN: ZWRIED
18. Melnikov B.F., Dolgov V.N. Simplified Regular Languages and a Special Equivalence Relation on the Class of Regular Languages. Part I. International Journal of Open Information Technologies. 2022;10(9):12-20. (In Russ., abstract in Eng.) EDN: WJFXEA
19. Hromkovič J. Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. 2nd ed. Berlin: Springer; 2004. 538 p. https://doi.org/10.1007/978-3-662-05269-3
20. Kameda T., Weiner P. On the State Minimization of Nondeterministic Finite Automata. IEEE Transactions on Computers. 1970;C-19(7):617-627. https://doi.org/10.1109/T-C.1970.222994
21. Li L., Qiu D. On the State Minimization of Fuzzy Automata. IEEE Transactions on Fuzzy Systems. 2015;23(2):434-443. https://doi.org/10.1109/TFUZZ.2014.2315620
22. Maarand H., Tamm H. Yet Another Canonical Nondeterministic Automaton. In: Han Y.S., Vaszil G. (eds.) Descriptional Complexity of Formal Systems. DCFS 2022. Lecture Notes in Computer Science. Vol. 13439. Cham: Springer; 2022. p. 184-196. https://doi.org/10.1007/978-3-031-13257-5_14
23. Melnikov B., Melnikova A. A Polynomial Algorithm for Construction an Automaton for Checking the Equality of Infinite Iterations of Two Finite Languages. In: Silhavy R. (eds.) Artificial Intelligence Trends in Systems. CSOC 2022. Lecture Notes in Networks and Systems. Vol. 502. Cham: Springer; 2022. p. 521-530. https://doi.org/10.1007/978-3-031-09076-9_47
24. 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;(2):46-52. (In Russ., abstract in Eng.) https://doi.org/10.21685/2072-3040-2021-2-4
25. Abramyan M., Melnikov B. 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;11:1459-1470. https://doi.org/10.4236/jamp.2023.115095
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
