Speaker: Jakub Radoszewski

Time: Saturday, 9:00-10:00

Title: Repetitions in labeled trees

Abstract:

Repetitions in strings are one of fundamental notions of algorithmics and combinatorics of strings. A basic type of repetitions are string powers, in particular, squares and cubes. In this talk I consider string powers in edge-labeled trees, that is, paths such that the sequence of symbols on a path forms a string power of a given exponent.

A classical bound related to squares in a string is that a string of length n contains at most 2n different squares. Moreover, all different squares in a string can be computed in linear time. It turns out that in trees the number of squares behaves totally differently. Denote by \(\text{powers}_p(n)\) the maximum number of different string powers of exponent p in a tree of n nodes. Then \(\text{powers}_2(n)\) is exactly of the order \(n^{4/3}\), and both the lower and the upper bound is obtained using a special family of trees called combs. The number of different squares for a tree of n nodes, together with an O(n)-sized representation of all the different squares in a tree, can be computed in \(O(n\log^2 n)\) time. This algorithm uses efficient versions of multiple classical string algorithms in the context of trees.

For any smaller fractional exponent p<2, already in the case of strings we have $$\text{powers}_p(n) = \Omega(n^2).$$ For trees, the second phase transition of this function takes place for cubes: for any fractional [latex] 2 < p < 3[/latex], [latex]\text{powers}_p(n) = \Omega(n^{4/3})[/latex], whereas [latex]\text{powers}_3(n) = O(n \log n)[/latex]. We also present some results on powers with higher exponent. Some results from this talk have been published at CPM 2012 and ISAAC 2012 conferences and also in the Theoretical Computer Science journal in 2014.

Forum Informatyki Teoretycznej 2015