A Program Study of Semilattices Connected with the Waterloo Automaton
DOI:
https://doi.org/10.14529/cmse240101Keywords:
недетерминированные конечные автоматы, универсальный автомат, грид, покрывающий автомат, алгоритмы эквивалентного преобразования, автомат ВатерлооAbstract
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.References
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.
