A linearly computable measure of string complexity

DOI10.1016/J.TCS.2012.03.007MaRDI QIDQ441859zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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 complexityLempel-Ziv complexitystring complexity

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• scientific article; zbMATH DE number 1747450
• scientific article; zbMATH DE number 2182449
• Maximizing T-complexity
• scientific article; zbMATH DE number 1336330
• scientific article; zbMATH DE number 4085051

Cites work

• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1747450 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• A Mathematical Theory of Communication
• A Pseudorandom Sequence--How Random Is It?
• A Theory of Program Size Formally Identical to Information Theory
• Clustering by Compression
• Compression of individual sequences via variable-rate coding
• Finite-state complexity and the size of transducers
• Lempel-Ziv Dimension for Lempel-Ziv Compression
• On extending de Bruijn sequences
• On the Complexity of Finite Sequences
• Process complexity and effective random tests
• Relations between varieties of kolmogorov complexities
• Resource-bounded Kolmogorov complexity revisited
• Suffix Arrays: A New Method for On-Line String Searches
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Volume and Entropy of Regular Timed Languages: Discretization Approach
• Volume and entropy of regular timed languages: analytic approach

Cited in

(11)

• A new distance metric on strings computable in linear time
• Joint string complexity for Markov sources: small data matters
• Substring complexities on run-length compressed strings
• Joint string complexity for Markov sources
• On average sequence complexity
• scientific article; zbMATH DE number 2182449 (Why is no real title available?)
• Maximizing T-complexity
• The combinatorial complexity of a finite string
• Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity
• Physical complexity of symbolic sequences
• scientific article; zbMATH DE number 1747450 (Why is no real title available?)

This page was built for publication: A linearly computable measure of string complexity

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