35 citations · 99 across the 47 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.DS2018
Compressed Communication Complexity of Longest Common Prefixes
Philip Bille, Mikko Berggreen Ettienne, Roberto Grossi +2
We consider the communication complexity of fundamental longest common prefix (Lcp) problems. In the simplest version, two parties, Alice and Bob, each hold a string, and ,…
cs.DS2018
From Regular Expression Matching to Parsing
Philip Bille, Inge Li Gørtz
Given a regular expression and a string , the regular expression parsing problem is to determine if matches and if so, determine how it matches, e.g., by a mapping o…
cs.DS2018
Decompressing Lempel-Ziv Compressed Text
Philip Bille, Mikko Berggren Ettienne, Travis Gagie +2
We consider the problem of decompressing the Lempel--Ziv 77 representation of a string of length using a working space as close as possible to the size of the input. Th…