Completing Wheeler Automata
Giuseppa Castiglione, Antonio Restivo · Theoretical Computer Science · 2025
• Weconsider the problem of completing a Wheeler Deterministic Finite Automaton (WDFA) A, that is, of embedding A into an equivalent complete WDFA. • WedefineWheeler-complete automata and prove that there exists a unique minimal Wheeler complete DFA containing A: it is called the minimal Wheeler-completion of A. • Wegive an algorithm that, given as input a WDFA, returns its minimal Wheeler-completion. • We derive some interesting applications of this algorithm concerning the construction of a WDFA for the union and a WDFA for the complement of Wheeler languages. We consider the problem of embedding a Wheeler Deterministic Finite Automaton (WDFA, in short) into an equivalent complete WDFA, preserving the order of states and the accepted language. In some cases, such a complete WDFA does not exist. We say that a WDFA is Wheeler-complete (W-complete, in short) if it cannot be properly embedded into an equivalent WDFA. We give an algorithm that, given as input a WDFA A , returns the smallest W-complete DFA containing A : it is called the minimal W-completion of A . We derive some interesting applications of this algorithm concerning the construction of a WDFA for the union and a WDFA for the complement of Wheeler languages.