Regular Languages meet Prefix Sorting

DOI10.1137/1.9781611975994.55OpenAlexW3002181530MaRDI QIDQ5146826

Giovanna D'Agostino, Alberto Policriti, Nicola Prezza, Jarno Alanko

Publication date: 2 February 2021

Published in: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items

Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails, On the Complexity of String Matching for Graphs, Algorithms and complexity on indexing founder graphs, Quantum time complexity and algorithms for pattern matching on labeled graphs, Colored constrained spanning tree on directed graphs, Ordering regular languages and automata: complexity, Unnamed Item, Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails, On the Hardness and Inapproximability of Recognizing Wheeler Graphs, Wheeler languages, Space efficient merging of de Bruijn graphs and Wheeler graphs, On the complexity of recognizing Wheeler graphs