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[1]w[2] · · · w[n] is a subset Γ of the positions 1, . . ., n, such that all distinct factors of w have an occurrence crossing at least one of the elements of Γ. While finding the smallest string attractor for a word is a NP-complete problem, it has been proved in [Kempa and Prezza, 2018] that dictionary compressors can be interpreted as algorithms approximating the smallest string attractor for a given word. In this paper we explore the notion of string attractor from a combinatorial point of view, by focusing on several families of finite words. The results presented in the paper suggest that the notion of string attractor can be used to define new tools to investigate combinatorial properties of the words.

Mantaci S., Restivo A., Romana G., Rosone G., Sciortino M. (2019). String attractors and combinatorics on words. In A. Cherubini, N. Sabadini, N. Tini (a cura di), CEUR Workshop Proceedings (pp. 57-71). CEUR-WS.

String attractors and combinatorics on words

Mantaci S.;Romana G.;Sciortino M.
2019-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[1]w[2] · · · w[n] is a subset Γ of the positions 1, . . ., n, such that all distinct factors of w have an occurrence crossing at least one of the elements of Γ. While finding the smallest string attractor for a word is a NP-complete problem, it has been proved in [Kempa and Prezza, 2018] that dictionary compressors can be interpreted as algorithms approximating the smallest string attractor for a given word. In this paper we explore the notion of string attractor from a combinatorial point of view, by focusing on several families of finite words. The results presented in the paper suggest that the notion of string attractor can be used to define new tools to investigate combinatorial properties of the words.
Settore INF/01 - Informatica
Settore ING-INF/05 - Sistemi Di Elaborazione Delle Informazioni
http://ceur-ws.org/
Mantaci S., Restivo A., Romana G., Rosone G., Sciortino M. (2019). String attractors and combinatorics on words. In A. Cherubini, N. Sabadini, N. Tini (a cura di), CEUR Workshop Proceedings (pp. 57-71). CEUR-WS.
File in questo prodotto:
File Dimensione Formato  
ICTCS 2019.pdf

accesso aperto

Tipologia: Versione Editoriale
Dimensione 575.42 kB
Formato Adobe PDF
575.42 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/396235
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact