Geodesic
A program study of semilattices connected with the Waterloo automaton
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 13 (2024) no. 1, pp. 5-21

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: nondeterministic finite automata, universal automaton, grid, covering automaton, the Waterloo automaton.
Mots-clés : equivalent transformation algorithms 
@article{VYURV_2024_13_1_a0,
     author = {M.E. Abramyan},
     title = {A program study of semilattices connected with the {Waterloo} automaton},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {5--21},
     publisher = {mathdoc},
     volume = {13},
     number = {1},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2024_13_1_a0/}
}
TY  - JOUR
AU  - M.E. Abramyan
TI  - A program study of semilattices connected with the Waterloo automaton
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2024
SP  - 5
EP  - 21
VL  - 13
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VYURV_2024_13_1_a0/
LA  - ru
ID  - VYURV_2024_13_1_a0
ER  - 
%0 Journal Article
%A M.E. Abramyan
%T A program study of semilattices connected with the Waterloo automaton
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2024
%P 5-21
%V 13
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VYURV_2024_13_1_a0/
%G ru
%F VYURV_2024_13_1_a0
M.E. Abramyan. A program study of semilattices connected with the Waterloo automaton. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 13 (2024) no. 1, pp. 5-21. http://geodesic.mathdoc.fr/item/VYURV_2024_13_1_a0/