Universally Wheeler Languages

The notion of Wheeler languages is rooted in the Burrows-Wheeler transform (BWT), one of the most central concepts in data compression and indexing. The BWT has been generalized to finite automata, the so-called Wheeler automata, by Gagie, Manzini, and Sirén. Wheeler languages have subsequently been defined as the class of regular languages for which there exists a Wheeler automaton accepting them. Besides their advantages in data indexing, these Wheeler languages also satisfy many interesting properties from a language theoretic point of view. A characteristic yet unsatisfying feature of Wheeler languages however is that their definition depends on a fixed order of the alphabet. In this paper we introduce the Universally Wheeler languagesUW, i.e., the regular languages that are Wheeler with respect to all orders of a given alphabet. Our first main contribution is to relate UW to some very well known regular language classes. We first show that the Strictly Locally Testable languages are strictly included in UW. After noticing that UW is not closed under taking the complement, we prove that the class of languages for which both the language and its complement are in UW exactly coincides with those languages that are Definite or Reverse Definite. Secondly, we prove that deciding if a regular language given by a DFA is in UW can be done in quadratic time. We also show that this is optimal unless the Strong Exponential Time Hypothesis fails.