4 papers
Variations on the Problem of Identifying Spectrum-Preserving String Sets
Sankardeep Chakraborty, Roberto Grossi, Ren Kimura +3
In computational genomics, many analyses rely on efficient storage and traversal of -mers, motivating compact representations such as spectrum-preserving string sets (SPSS), whi…
Revisiting the Sparse Matrix Compression Problem
Vincent Jugé, Dominik Köppl, Vincent Limouzy +4
The sparse matrix compression problem asks for a one-dimensional representation of a binary matrix, formed by an integer array of row indices and a shift function f…
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…
The Complexity of Maximal Common Subsequence Enumeration
Giovanni Buzzega, Alessio Conte, Yasuaki Kobayashi +2
Frequent pattern mining is widely used to find ``important'' or ``interesting'' patterns in data. While it is not easy to mathematically define such patterns, maximal frequent patt…