1 citations · 1 across the 3 of their papers we have counts for
5 papers
Partial Sums on the Ultra-Wide Word RAM
Philip Bille, Inge Li Gørtz, Frederik Rye Skjoldjensen
We consider the classic partial sums problem on the ultra-wide word RAM model of computation. This model extends the classic -bit word RAM model with special ultrawords of lengt…
Succinct Partial Sums and Fenwick Trees
Philip Bille, Anders Roy Christiansen, Nicola Prezza +1
We consider the well-studied partial sums problem in succint space where one is to maintain an array of n k-bit integers subject to updates such that partial sums queries can be ef…
Deterministic Indexing for Packed Strings
Philip Bille, Inge Li Gørtz, Frederik Rye Skjoldjensen
Given a string of length , the classic string indexing problem is to preprocess into a compact data structure that supports efficient subsequent pattern queries. In the…
Subsequence Automata with Default Transitions
Philip Bille, Inge Li Gørtz, Frederik Rye Skjoldjensen
Let be a string of length with characters from an alphabet of size . The \emph{subsequence automaton} of (often called the \emph{directed acyclic subsequence graph})…
Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation
Philip Bille, Patrick Hagge Cording, Inge Li Gørtz +3
Given a static reference string and a source string , a relative compression of with respect to is an encoding of as a sequence of references to substrings of $R…