6533b858fe1ef96bd12b598a

RESEARCH PRODUCT

A combinatorial view on string attractors

Giovanna RosoneMarinella SciortinoGiuseppe RomanaSabrina MantaciAntonio Restivo

subject

General Computer ScienceSettore INF/01 - InformaticaString (computer science)de Bruijn word0102 computer and information sciences02 engineering and technologyCharacterization (mathematics)Burrows-Wheeler transform01 natural sciencesMeasure (mathematics)Standard Sturmian wordTheoretical Computer ScienceCombinatoricsConjugacy classMonotone polygonString attractor010201 computation theory & mathematicsAttractorThue-Morse word0202 electrical engineering electronic engineering information engineeringLempel-Ziv encoding020201 artificial intelligence & image processingWord (group theory)Mathematics

description

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 Γ. 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.

yearjournalcountryeditionlanguage
2021-01-01
10.1016/j.tcs.2020.11.006http://hdl.handle.net/10447/463264