The combinatorial complexity of a finite string

DOI10.1007/3-540-58338-6_83MaRDI QIDQ5096895zbMATH OpenOpenAlexFDO

Authors Felix Frayman, Valery Kanevsky, W. Kirchherr

Publication date 18 August 2022

Published in Mathematical Foundations of Computer Science 1994 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-58338-6_83

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• scientific article; zbMATH DE number 1747450
• A linearly computable measure of string complexity
• On the computational power of random strings
• scientific article; zbMATH DE number 3900670
• Non-approximability of the Randomness Deficiency Function

Cites work

• Eulerian graphs and related topics. Part 1, Volume 1
• scientific article; zbMATH DE number 46981 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• scientific article; zbMATH DE number 1142293 (Why is no real title available?)
• scientific article; zbMATH DE number 3338381 (Why is no real title available?)
• On the Complexity of Finite Sequences

Cited in

(9)

• The complexity of string partitioning
• The large deviations law in number theory, computable functions of several arguments, and decoding
• A level of Martin-Lof randomness.
• The Complexity of String Partitioning
• Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity
• Greedy Conjecture for Strings of Length 4
• Effective complexity as a measure of information content
• Non-approximability of the Randomness Deficiency Function
• scientific article; zbMATH DE number 1747450 (Why is no real title available?)

This page was built for publication: The combinatorial complexity of a finite string

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