52 citations · 133 across the 25 of their papers we have counts for
3 papers · 1 filter
Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
Gabriel Bathie, Tomasz Kociumaka, Tatiana Starikovskaya
We study the online variant of the language distance problem for two classical formal languages, the language of palindromes and the language of squares, and for the two most funda…
Sorting Signed Permutations by Reversals in Nearly-Linear Time
Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya
Given a signed permutation on elements, we need to sort it with the fewest reversals. This is a fundamental algorithmic problem motivated by applications in comparative genomic…
Compressed Indexing for Consecutive Occurrences
Paweł Gawrychowski, Garance Gourdel, Tatiana Starikovskaya +1
The fundamental question considered in algorithms on strings is that of indexing, that is, preprocessing a given string for specific queries. By now we have a number of efficient s…