20 citations · 86 across the 21 of their papers we have counts for
Showing 2016 · cs.DSShow all
2 papers · 2 filters
cs.DS2016★ 11 cited
On the Size of Lempel-Ziv and Lyndon Factorizations
Juha Kärkkäinen, Dominik Kempa, Yuto Nakashima +2
Lyndon factorization and Lempel-Ziv (LZ) factorization are both important tools for analysing the structure and complexity of strings, but their combinatorial structure is very dif…
cs.DS2016★ 1 cited
Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams
Paweł Gawrychowski, Oleg Merkurev, Arseny M. Shur +1
We consider computing a longest palindrome in the streaming model, where the symbols arrive one-by-one and we do not have random access to the input. While computing the answer exa…