On the complexity of computing the co-lexicographic width of a regular language

Co-lex partial orders (Cotumaccio and Prezza (2021) [9] and Cotumaccio et al. (2023) [8]) are a powerful tool to index finite automata generalizing Wheeler orders (Gagie et al. (2017) [14]). The co-lex width p of an automaton measures how sortable its states are w.r.t. the co-lexicographic order among its accepted strings. Automata of co-lex width p can be compressed to O(log⁡p) bits per edge and admit regular expression matching in time proportional to p2 per matched character. The deterministic co-lex width of a regular language L is the smallest width of such a co-lex order, among all DFAs recognizing L. Since languages of small co-lex width admit efficient solutions to hard computational problems, computing the co-lex width is relevant in applications. Previous work showed that the deterministic co-lex width p of a language L can be computed in mO(p) for a DFA A with m transitions accepting L. For constant p (in particular Wheeler languages, where p=1), the constant in the exponent is large and the exact complexity remains unknown. In this work, we show that one can decide in O(mp) if the deterministic co-lex width of the language recognized by a given minimum DFA is strictly smaller than p≥2. We complement this with a matching conditional lower bound based on the Strong Exponential Time Hypothesis. Hence, our paper essentially settles the complexity of the problem.