String attractor: a combinatorial object from data compression

Giuseppe Romana
Università degli Studi di Palermo

Date(s) : 17/10/2022   iCal
15 h 00 min - 16 h 00 min

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 of a finite word is a set of positions in such that each distinct factors that occurs in has at least an occurrence that crosses a position . In this talk, we explore String Attractors from a combinatorial perspective. We discuss how the size 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 . 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:

Virtual event


Retour en haut 

Secured By miniOrange