The number of repetitions in 2D-strings
- Prelegent(ci)
- Wiktor Zuba
- Termin
- 8 października 2020 12:15
- Informacje na temat wydarzenia
- [online seminar]
- Seminarium
- Seminarium "Algorytmika"
The notions of periodicity and repetitions in strings, and
hence these of runs and squares, naturally extend to two-dimensional
strings. We consider two types of repetitions in 2D-strings: 2D-runs and
quartics (quartics are a 2D-version of squares in standard strings).
Amir et al. introduced 2D-runs, showed that there are O(n^3) of them in
an n×n 2D-string and presented a simple construction giving a lower
bound of Ω(n^2) for their number (TCS, 2020). We make a significant step
towards closing the gap between these bounds by showing that the number
of 2D-runs in an n×n 2D-string is O(n^2 log^2 n). We also present
several algorithmic results connected to this new upper bound, as well
discuss improved upper bounds on the number of quartics.