A linearly computable measure of string complexity

DOI10.1016/j.tcs.2012.03.007zbMath1255.68117WikidataQ61927022 ScholiaQ61927022MaRDI QIDQ441859

Verónica Becher, Pablo Ariel Heiber

Publication date: 8 August 2012

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

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

zbMATH Keywords

description complexity; Lempel-Ziv complexity; string complexity

Mathematics Subject Classification ID

68R15: Combinatorics on words

68W32: Algorithms on strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• On extending de Bruijn sequences
• Process complexity and effective random tests
• Resource-Bounded Kolmogorov Complexity Revisited
• A Pseudorandom Sequence--How Random Is It?
• Suffix Arrays: A New Method for On-Line String Searches
• Volume and Entropy of Regular Timed Languages: Discretization Approach
• Clustering by Compression
• Volume and Entropy of Regular Timed Languages: Analytic Approach
• A Theory of Program Size Formally Identical to Information Theory
• On the Complexity of Finite Sequences
• Compression of individual sequences via variable-rate coding
• Relations between varieties of kolmogorov complexities
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Lempel-Ziv Dimension for Lempel-Ziv Compression