  A Wheeler automaton is a finite state automaton whose states admit a total
Wheeler order, reflecting the co-lexicographic order of the strings labeling
source-to-node paths. A Wheeler language is a regular language admitting an
accepting Wheeler automaton. Wheeler languages admit efficient and elegant
solutions to hard problems such as automata compression and regular expression
matching, therefore deciding whether a regular language is Wheeler is relevant
in applications requiring efficient solutions to those problems. In this paper,
we show that it is possible to decide whether a DFA with n states and m
transitions recognizes a Wheeler language in $O(mn)$ time. This is a
significant improvement over the running time $O(n^{13} + m\log n)$ of the
previous polynomial-time algorithm (Alanko et al., Information and Computation
2021). A proof-of-concept implementation of this algorithm is available in a
public repository. We complement this upper bound with a conditional matching
lower bound stating that, unless the strong exponential time hypothesis (SETH)
fails, the problem cannot be solved in strongly subquadratic time. The same
problem is known to be PSPACE-complete when the input is an NFA (D'Agostino et
al., Theoretical Computer Science 2023). Together with that result, our paper
essentially closes the algorithmic problem of Wheeler language recognition.
