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

DOI10.1016/J.JCSS.2026.103759MaRDI QIDQ6845959zbMATH OpenFDO

Authors Ruben Becker, Davide Cenzato, SungHwan Kim, Tomasz Kociumaka, Bojana Kodric, Alberto Policriti, Nicola Prezza

Publication date 12 March 2026

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2026.103759

zbMATH Keywords

indexingparameterized complexityregular languagessortingWheeler automata

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• Co-lexicographically ordering automata and regular languages. I
• Computing the LCP array of a labeled graph
• Efficient randomized pattern-matching algorithms
• Faster prefix-sorting algorithms for deterministic finite automata
• scientific article; zbMATH DE number 177800 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 7788491 (Why is no real title available?)
• Linear Automaton Transformations
• On the complexity of recognizing Wheeler graphs
• Optimal Wheeler language recognition
• Ordering regular languages and automata: complexity
• Polynomial hash functions are reliable (extended abstract)
• Prefix sorting DFAs: a recursive algorithm
• Sorting finite automata via partition refinement
• The rational construction of a Wheeler DFA
• Wheeler graphs: a framework for BWT-based data structures
• Wheeler languages
• Which problems have strongly exponential complexity?

This page was built for publication: On the complexity of computing the co-lexicographic width of a regular language

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6845959)