Ordering regular languages and automata: complexity

DOI10.1016/j.tcs.2023.113709OpenAlexW4317213941MaRDI QIDQ2686107

Davide Martincigh, Giovanna D'Agostino, Alberto Policriti

Publication date: 24 February 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2203.12534

zbMATH Keywords

finite automataregular languagesordering languagesWheeler automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• The state complexities of some basic operations on regular languages
• Wheeler graphs: a framework for BWT-based data structures
• Wheeler languages
• Relationships between nondeterministic and deterministic tape complexities
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Regular Languages meet Prefix Sorting