Generalization of repetitiveness measures for two-dimensional strings

DOI10.1007/S00224-025-10244-9MaRDI QIDQ7233448zbMATH OpenFDO

Authors Lorenzo Carfagna, Giovanni Manzini, Giuseppe Romana, M. Sciortino, Cristian Urbina

Publication date 27 April 2026

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00224-025-10244-9

zbMATH Keywords

grammar compressionrepetitiveness measurestext compressiontwo-dimensional strings

Mathematics Subject Classification ID

Theory of data (68Pxx) Theory of computing (68Qxx) Algorithms in computer science (68Wxx)

Cites work

• \(LZ\)-based image compression
• A combinatorial view on string attractors
• A Generalization of the Suffix Tree to Square Matrices, with Applications
• At the roots of dictionary compression: string attractors
• Block trees
• Compressibility measures for two-dimensional data
• Data compression via textual substitution
• Linear-time construction of two-dimensional suffix trees
• On the approximation ratio of Lempel-Ziv parsing
• On the Approximation Ratio of Ordered Parsings
• On the complexity of pattern matching for highly compressed two-dimensional texts.
• Optimal-Time Dictionary-Compressed Indexes
• Random access to grammar-compressed strings and trees
• Substring complexity in sublinear space
• The Smallest Grammar Problem
• The Smallest Grammar Problem Revisited
• Toward a Definitive Compressibility Measure for Repetitive Sequences

This page was built for publication: Generalization of repetitiveness measures for two-dimensional strings

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