2014/09/19 by Dmitry Kosolobov, Kosolobov, Dmitry · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1409.5641
12 pages, 3 figures, submitted
arxiv created 2014/09/19 · openalex publication_date 2014/09/19 · arxiv updated 2014/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. It is known that both these problems can be solved by RAM algorithms in O(nlogσ) time, where n is the length of the input string and σ is the number of distinct letters in it. We prove an Ω(nlogσ) lower bound on the number of comparisons required to construct the Lempel-Ziv factorization and thereby conclude that a popular technique of computation of runs using the Lempel-Ziv factorization cannot achieve an o(nlogσ) time bound. In contrast with this, we exhibit an O(n) decision tree algorithm finding all runs in a string. Therefore, in the decision tree model the runs problem is easier than the Lempel-Ziv factorization. Thus we support the conjecture that there is a linear RAM algorithm finding all runs.