Encoding co-lex orders of finite-state automata in linear space

DOI10.4230/LIPICS.CPM.2025.15MaRDI QIDQ7299450zbMATH OpenFDO

Authors Ruben Becker, SungHwan Kim, Nicola Prezza, Carlo Tosoni

Publication date 17 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CPM.2025.15

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites work

• Co-lexicographically ordering automata and regular languages. I
• Computing the LCP array of a labeled graph
• Faster prefix-sorting algorithms for deterministic finite automata
• scientific article; zbMATH DE number 7788491 (Why is no real title available?)
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Prefix sorting DFAs: a recursive algorithm
• Scalable Algorithms for Data and Network Analysis
• Sorting finite automata via partition refinement
• Space-time trade-offs for the LCP array of Wheeler DFAs
• Three Partition Refinement Algorithms
• Wheeler graphs: a framework for BWT-based data structures

Cited in

(1)

• Fast pattern matching with epsilon transitions

This page was built for publication: Encoding co-lex orders of finite-state automata in linear space

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