2024/10/07 by Becker, Ruben, Cenzato, Davide, Kim, Sung-Hwan +4
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2410.04771
Co-lex partial orders were recently introduced in (Cotumaccio et al., SODA 2021 and JACM 2023) as a powerful tool to index finite state automata, with applications to regular expression matching. They generalize Wheeler orders (Gagie et al., Theoretical Computer Science 2017) and naturally reflect the co-lexicographic order of the strings labeling source-to-node paths in the automaton. Briefly, the co-lex width p of a finite-state automaton measures how sortable its states are with respect to the co-lex order among the strings they accept. Automata of co-lex width p can be compressed to O(log p) bits per edge and admit regular expression matching algorithms running in time proportional to p2 per matched character. The deterministic co-lex width of a regular language \mathcal L is the smallest width of such a co-lex order, among all DFAs recognizing \mathcal L. Since languages of small co-lex width admit efficient solutions to automata compression and pattern matching, computing the co-lex width of a language is relevant in these applications. The paper introducing co-lex orders determined that the deterministic co-lex width p of a language \mathcal L can be computed in time proportional to mO(p), given as input any DFA \mathcal A for \mathcal L, of size (number of transitions) m =|\mathcal A|. In this paper, using new techniques, we show that it is possible to decide in O(mp) time if the deterministic co-lex width of the language recognized by a given minimum DFA is strictly smaller than some integer p≥ 2. We complement this upper bound with a matching conditional lower bound based on the Strong Exponential Time Hypothesis. The problem is known to be PSPACE-complete when the input is an NFA (D'Agostino et al., Theoretical Computer Science 2023); thus, together with that result, our paper essentially settles the complexity of the problem.