On the Complexity of Computing the Co-lexicographic Width of a Regular Language

Ruben Becker, Davide Cenzato, Sung-Hwan Kim +4

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 expre…