A Program Study of the Union of Semilattices on a Set of Subsets of Grids of the Waterloo Language
Abstract
Relevance. The relevance of the subject area under consideration is due to the need to study the set of regular languages, in particular to describe their various sub-classes. Also rel-evant are the tasks that may arise in some such subclasses. This will give, among other things, the possibility of describing some new algorithms for equivalent transformation of nondeter-ministic finite automata.
Purpose of the study. The aim is to study the set of subsets of grids of the Waterloo language from the point of view of abstract algebra.
Materials and methods. The study was conducted using the library for working with nondeterministic finite automata NFALib implemented by one of the authors in C#, as well as statistical methods for analyzing algorithms.
Results. The results are regularities obtained when considering semilattices on a set of subsets of grids of the Waterloo language.
Conclusions. It follows from the results obtained that the minimum covering automa-ton equivalent to the Waterloo automaton can be obtained by adding one additional to the minimum covering set of grids. The calculations also show that in addition to the minimum covering automaton, it is possible to obtain 4 more minimum covering automata equivalent to the original Waterloo automaton, however, to obtain each of them, it is necessary to replace 1 or 2 grids included in the minimum covering set.
References
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
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
