A program study of semilattices connected with the Waterloo automaton

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.