Testing Wheelerness of Regular Languages

A regular language is said to be Wheeler if it is accepted by some finite automaton whose states admit a total Wheeler order, which reflects the co-lexicographic order of the prefixes of the strings accepted by the automaton. As Wheeler automata provide useful properties for many applications related to pattern matching and indexing, it is important to check if a given regular language is Wheeler to know if we can benefit from them. In this paper, we present an algorithm to decide whether a regular language represented as a deterministic finite automaton is Wheeler in quadratic time, which also matches the lower bound unless the strong exponential time hypothesis fails. Our method can also be extended to decide if there exists a p-width DFA that accepts the language of the input DFA.