# Subpath Queries on Compressed Graphs: A Survey
## 3 Indexing Labeled Graphs and Regular Languages
### Wheeler Graphs
#### 3.7.4 Wheeler Languages  
Since we are talking about finite automata, one question should arise naturally: what languages are recognized by Wheeler NFAs? Let us call _Wheeler languages_ this class. First of all, Wheeler languages are clearly regular since, by definition, they are accepted by finite state automata. Moreover, all finite languages are Wheeler because they can be recognized by a tree-shaped automaton, which (as seen in Section 3.5) is always prefix-sortable. Additionally, as observed by [PERSON] et al. [50] not all regular languages are Wheeler: \((ax^{*}b)|(cx^{*}d)\) is an example. Interestingly, Wheeler languages can be defined both in terms of DFAs and NFAs: [PERSON] et al. proved in Reference [65] that Wheeler NFAs and Wheeler DFs recognize the same class of languages. Another powerful language-theoretic result that can be transferred from regular to Wheeler languages is their neat algebraic characterization based on Myhill-Nerode equivalence classes [66]. We recall that two strings \(\alpha\) and \(\beta\) are Myhill-Nerode equivalent with respect to a given regular language \(\mathcal{L}\) if and only if, for any string \(\gamma\), we have that \(a\gamma\in\mathcal{L}\Leftrightarrow\beta\gamma\in\mathcal{L}\). The Myhill-Nerode theorem states that \(\mathcal{L}\) is regular if and only if the Myhill-Nerode equivalence relation has finite index (i.e., it has a finite number of equivalence classes). In the Wheeler case, the Myhill-Nerode equivalence relation is slightly modified by requiring that equivalence classes of prefixes of the language are also intervals in co-lexicographic order and contain words ending with the same letter. After this modification, the Myhill-Nerode theorem can be transferred to Wheeler languages: \(\mathcal{L}\) is Wheeler if and only if the modified Myhill-Nerode equivalence relation has finite index [65; 88]. See [PERSON] et al. [88] for a comprehensive study of the elegant properties of Wheeler languages (including closure properties and complexity of the recognition problem). From the algorithmic point of view (which is the most relevant to this survey), these results permit to define and build efficiently the _minimum_ Wheeler DFA (that is, with the smallest number of states) recognizing the same language of a given input Wheeler DFA, thus optimizing the space of the resulting index [65]. After this introduction to Wheeler languages, let us consider the question: can we index Wheeler languages efficiently? Interestingly, [PERSON] and [PERSON]'s NP-completeness proof [86] requires that the automaton's topology is fixed so it does not rule out the possibility that we can index in polynomial time an equivalent automaton. After all, in many situations, we are actually interested in indexing a language rather than a fixed graph topology. Surprisingly, the answer to the above question is yes: it is easier to index Wheeler languages, rather than Wheeler automata. Since recognizing and sorting Wheeler DFAs is an easy problem, a first idea could be to turn the input NFA into an equivalent DFA. While it is well-known that, in the worst case, this conversion (via the powerset algorithm) could result in an exponential blow-up of the number of states, [PERSON] et al. [65] proved that a Wheeler NFA always admits an equivalent Wheeler DFA of linear size (the number of states doubles at most). This has an interesting consequence: if the input NFA is Wheeler, then we can index its language in linear time (in the size of the input NFA) after converting it to a DFA (which requires polynomial time). We can actually do better: if the input NFA \(\mathcal{A}\) is Wheeler, then in polynomial time we can build a Wheeler NFA \(\mathcal{A}^{\prime}\) that (i) is never larger than \(\mathcal{A}\), (ii) recognizes the same language as \(\mathcal{A}\), and (iii) can be sorted in polynomial time [88].