The number of repetitions in 2D-strings

Speaker(s)

Wiktor Zuba

Date

Oct. 8, 2020, 12:15 p.m.

Information about the event

[online seminar]

Seminar

Seminar Algorithms

---

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.

---