The notion of string attractor has recently been introduced in [Prezza, 2017] and studied in [Kempa and Prezza, 2018] to provide a unifying framework for known dictionary-based compressors. A string attractor for a word w=w_1w_2...w_n is a subset Γ of the positions {1,2,...,n}, such that all distinct factors of w have an occurrence crossing at least one of the elements of Γ. In this paper we explore the notion of string attractor by focusing on its combinatorial properties. In particular, we show how the size of the smallest string attractor of a word varies when combinatorial operations are applied and we deduce that such a measure is not monotone. Moreover, we introduce a circular variant of the notion of string attractor to provide a characterization of the conjugacy classes of standard Sturmian words.

Mantaci, S., Restivo, A., Romana, G., Rosone, G., Sciortino, M. (2021). A combinatorial view on string attractors. THEORETICAL COMPUTER SCIENCE, 850, 236-248 [10.1016/j.tcs.2020.11.006].

A combinatorial view on string attractors

Mantaci, Sabrina;Romana, Giuseppe;Sciortino, Marinella
2021-01-01

Abstract

The notion of string attractor has recently been introduced in [Prezza, 2017] and studied in [Kempa and Prezza, 2018] to provide a unifying framework for known dictionary-based compressors. A string attractor for a word w=w_1w_2...w_n is a subset Γ of the positions {1,2,...,n}, such that all distinct factors of w have an occurrence crossing at least one of the elements of Γ. In this paper we explore the notion of string attractor by focusing on its combinatorial properties. In particular, we show how the size of the smallest string attractor of a word varies when combinatorial operations are applied and we deduce that such a measure is not monotone. Moreover, we introduce a circular variant of the notion of string attractor to provide a characterization of the conjugacy classes of standard Sturmian words.
Settore INF/01 - Informatica
Mantaci, S., Restivo, A., Romana, G., Rosone, G., Sciortino, M. (2021). A combinatorial view on string attractors. THEORETICAL COMPUTER SCIENCE, 850, 236-248 [10.1016/j.tcs.2020.11.006].
File in questo prodotto:
File Dimensione Formato  
A combinatorial view on string attractors.pdf

Solo gestori archvio

Tipologia: Versione Editoriale
Dimensione 456.4 kB
Formato Adobe PDF
456.4 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
MRRRS_TCS2021.pdf

Open Access dal 11/11/2022

Tipologia: Post-print
Dimensione 371.69 kB
Formato Adobe PDF
371.69 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/463264
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 2
social impact