3 papers
cs.CC2025
Are Depth-2 Regular Expressions Hard to Intersect?
Rocco Ascone, Giulia Bernardini, Alessio Conte +2
We study the basic regular expression intersection testing problem, which asks to determine whether the intersection of the languages of two regular expressions is nonempty. A text…
cs.DS2025
Prefix-free parsing for merging big BWTs
Diego Diaz-Dominguez, Travis Gagie, Veronica Guerrini +5
When building Burrows-Wheeler Transforms (BWTs) of truly huge datasets, prefix-free parsing (PFP) can use an unreasonable amount of memory. In this paper we show how if a dataset c…
cs.DS2025
Indexing Strings with Utilities
Giulia Bernardini, Huiping Chen, Alessio Conte +5
Applications in domains ranging from bioinformatics to advertising feature strings that come with numerical scores (utilities). The utilities quantify the importance, interest, pro…