A combinatorial view on string attractors

DOI10.1016/J.TCS.2020.11.006MaRDI QIDQ2216440zbMATH OpenOpenAlexFDO

Authors Sabrina Mantaci, Antonio Restivo, Giuseppe Romana, Giovanna Rosone, M. Sciortino

Publication date 16 December 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2020.11.006

zbMATH Keywords

Thue-Morse wordBurrows-Wheeler transformde Bruijn wordstandard Sturmian wordLempel-Ziv encodingstring attractor

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Combinatorics on words (68R15)

Recommendations

• At the roots of dictionary compression: string attractors
• Universal compressed text indexing
• Compressed string-matching in standard Sturmian words
• Usefulness of directed acyclic subword graphs in problems related to standard Sturmian words
• Repetitions in strings: algorithms and combinatorics

Cites work

• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 6850405 (Why is no real title available?)
• scientific article; zbMATH DE number 7378722 (Why is no real title available?)
• A universal algorithm for sequential data compression
• At the roots of dictionary compression: string attractors
• Balancing and clustering of words in the Burrows-Wheeler transform
• Burrows-Wheeler transform and Sturmian words
• Circular Sturmian words and Hopcroft's algorithm
• Compressed string-matching in standard Sturmian words
• Compression of individual sequences via variable-rate coding
• Computing Burrows-Wheeler similarity distributions for string collections
• Enumeration of factors in the Thue-Morse word
• Fast Pattern Matching in Strings
• From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space
• Hopcroft’s Algorithm and Cyclic Automata
• LZ77 computation based on the run-length encoded BWT
• Measuring the clustering effect of BWT via RLE
• On Christoffel classes
• On extremal cases of Hopcroft's algorithm
• On the Complexity of Finite Sequences
• Some combinatorial properties of Sturmian words
• Sorting conjugates and suffixes of words in a multiset
• Sturmian words, Lyndon words and trees
• Sturmian words: structure, combinatorics, and their arithmetics
• Suffix Automata and Standard Sturmian Words
• Suffix array and Lyndon factorization of a text
• Suffixes, conjugates and Lyndon words
• Towards a definitive measure of repetitiveness

Cited in

(11)

• String Attractors of Fixed Points of k-Bonacci-Like Morphisms
• String attractors of episturmian sequences
• A separation of \(\gamma\) and \(b\) via Thue-Morse words
• New string attractor-based complexities for infinite words
• An umbral relation between pattern and commutation in strings
• Substring complexities on run-length compressed strings
• Sensitivity of string compressors and repetitiveness measures
• String attractors of some simple-parry automatic sequences
• String Attractors for Factors of the Thue-Morse Word
• String attractors and infinite words
• Compressibility measures for two-dimensional data

Describes a project that uses

Uses Software

• Big-BWT
• r-index

This page was built for publication: A combinatorial view on string attractors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2216440)