TITLE:
Combined Algorithm for Searching Waterloo-Like Automata and First Results of Its Application
AUTHORS:
Mikhail Abramyan, Boris Melnikov
KEYWORDS:
Nondeterministic Finite Automata, Vertex Minimization Algorithms for NFA, Universal Automaton, Covering Automaton, Complete Automaton, The Waterloo Automaton
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.13 No.4,
April
29,
2025
ABSTRACT: The paper continues the research on algorithms for generating nondeterministic finite automata possessing the following property (the so-called walibad property): among their covering automata, there exist automata that are not equivalent to the original automaton. The Waterloo automaton has this property; it plays an important role in vertex minimization algorithms. In this paper, we describe a combined algorithm for generating automata with the walibad property and present the first results of its numerical study.