Regular Languages meet Prefix Sorting. Indexing strings via prefix (or suffix) sorting is, arguably, one of the most successful algorithmic techniques developed in the last decades. Can indexing be extended to languages? The main contribution of this paper is to initiate the study of the subclass of regular languages accepted by an automaton whose states can be prefixsorted. Starting from the recent notion of Wheeler graph Gagie et al., TCS 2017which extends naturally the concept of prefix sorting to labeled graphswe investigate the properties of Wheeler languages, that is, regular languages admitting an accepting Wheeler finite automaton. Interestingly, we characterize this family as the natural extension of regular languages endowed with the colexicographic ordering: when sorted, the strings belonging to a Wheeler language are partitioned into a finite number of colexicographic intervals, each formed by elements from a single MyhillNerode equivalence class. Moreover: (i) We show that every Wheeler NFA (WNFA) with n states admits an equivalent Wheeler DFA (WDFA) with at most 2n1Sigma states that can be computed in O(n3) time. This is in sharp contrast with general NFAs. (ii) We describe a quadratic algorithm to prefixsort a proper superset of the WDFAs, a O(nlog n)time online algorithm to sort acyclic WDFAs, and an optimal lineartime offline algorithm to sort general WDFAs. By contribution (i), our algorithms can also be used to index any WNFA at the moderate price of doubling the automatonu0027s size. (iii) We provide a minimization theorem that characterizes the smallest WDFA recognizing the same language of any input WDFA. The corresponding constructive algorithm runs in optimal linear time in the acyclic case, and in O(nlog n) time in the general case. (iv) We show how to compute the smallest WDFA equivalent to any acyclic DFA in nearlyoptimal time.

Complexity of SuffixFree Regular Languages A sequence ((L_k,L_k1 dots )) of regular languages in some class (mathcal C), where n is the state complexity of (L_n), is called a stream. A stream is most complex in class (mathcal C) if its languages together with their dialects (that is, languages that differ only very slightly from the languages in the stream) meet the state complexity bounds for boolean operations, product (concatenation), star, and reversal, have the largest syntactic semigroups, and have the maximal numbers of atoms, each of which has maximal state complexity. It is known that there exist such most complex streams in the class of regular languages, and also in the classes of right, left, and twosided ideals. In contrast to this, we prove that there does not exist a most complex stream in the class of suffixfree regular languages. However, we do exhibit one ternary suffixfree stream that meets the bound for product and whose restrictions to binary alphabets meet the bounds for star and boolean operations. We also exhibit a quinary stream that meets the bounds for boolean operations, reversal, size of syntactic semigroup, and atom complexities. Moreover, we solve an open problem about the bound for the product of two languages of state complexities m and n in the binary case by showing that it can be met for infinitely many m and n.