Évènement

Giuseppe Romana
Università degli Studi di Palermo
https://dblp.org/pid/244/9952.html

Date(s) : 17/10/2022   iCal
15h00 - 16h00

Very recently, Kempa and Prezza [STOC 2018] introduced the notion of String Attractor in the field of Data Compression, and showed how this concept was already implicit in many other well known compression schemes. Basically, a String Attractor $\Gamma$ of a finite word $w$ is a set of positions in $w$ such that each distinct factors that occurs in $w$ has at least an occurrence that crosses a position $j\in \Gamma$. In this talk, we explore String Attractors from a combinatorial perspective. We discuss how the size ${\gamma }^{\ast }$ of a string attractor of minimum size is affected when some classical combinatorial operations are applied to finite words. Further, we show how the size and other structural properties of string attractors can be used to obtain new characterizations for infinite words. Most of the results presented in this talk come from [A combinatorial view on string attractors, Theoret. Comput. Sci. 2021] and [String Attractors and Infinite Words, LATIN 2022](to appear).

The address of the Zoom meeting is https://zoom.us/j/92245493528 . The password is distributed in announcements. If you want to receive them, or receive them and want to unsubscribe, please write to Anna Frid.
More info: https://www.i2m.univ-amu.fr/wiki/Combinatorics-on-Words-seminar/

Emplacement
Virtual event

Catégories Pas de Catégories