18 citations · 54 across the 16 of their papers we have counts for
4 papers · 1 filter
Online Detection of Repetitions with Backtracking
Dmitry Kosolobov
In this paper we present two algorithms for the following problem: given a string and a rational , detect in the online fashion the earliest occurrence of a repetition of ex…
Online Square Detection
Dmitry Kosolobov
The online square detection problem is to detect the first occurrence of a square in a string whose characters are provided as input one at a time. Recall that a square is a string…
Lempel-Ziv Factorization May Be Harder Than Computing All Runs
Dmitry Kosolobov
The complexity of computing the Lempel-Ziv factorization and the set of all runs (= maximal repetitions) is studied in the decision tree model of computation over ordered alphabet.…
Is Linear Recognizable Online
Dmitry Kosolobov, Mikhail Rubinchik, Arseny M. Shur
Given a language that is online recognizable in linear time and space, we construct a linear time and space online recognition algorithm for the language ,…