A combinatorial view on string attractors

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=w1w2⋯wn is a subset Γ of the positions {1,…,n}, such that all distinct factors...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2021-01, Vol.850, p.236-248
Main Authors: Mantaci, Sabrina, Restivo, Antonio, Romana, Giuseppe, Rosone, Giovanna, Sciortino, Marinella
Format: Article
Language:English
Subjects:
Burrows-Wheeler transform
de Bruijn word
Lempel-Ziv encoding
Standard Sturmian word
String attractor
Thue-Morse word
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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=w1w2⋯wn 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 Γ. 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2020.11.006