Archivio istituzionale della ricerca dell'Università degli Studi di Palermo
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, pubblicazioni, progetti, attività) adottato dall’Università di Palermo, e ha lo scopo di raccogliere, conservare, documentare, e diffondere ad accesso aperto le informazioni relative alla produzione scientifica degli autori afferenti all’Ateneo.
EnglishThe 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.
| Data di pubblicazione: | 2021 |
| Titolo: | A combinatorial view on string attractors |
| Autori: | SCIORTINO, Marinella (Corresponding) |
| Citazione: | Mantaci, S., Restivo, A., Romana, G., Rosone, G., & Sciortino, M. (2021). A combinatorial view on string attractors. THEORETICAL COMPUTER SCIENCE, 850, 236-248. |
| Rivista: | |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.tcs.2020.11.006 |
| 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 Scientifico Disciplinare: | Settore INF/01 - Informatica |
| Appare nelle tipologie: | 1.01 Articolo in rivista |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| A combinatorial view on string attractors.pdf | Versione Editoriale | Administrator Richiedi una copia |
http://hdl.handle.net/10447/463264
Copyright © 2021