Finite state incompressible infinite sequences (Q259039): Difference between revisions

In the paper under review, the authors introduce finite state complexity of finite strings and infinite sequences as well as connections between these complexity notions to randomness and normality. A number of results concerning the complexity are proved. For example, the authors characterize Martin-Löf randomness via finite state complexity.

0 references

reviewed by

Liang Yu

0 references

zbMATH Keywords

AIT

0 references

finite state complexity

0 references

finite state incompressibility

0 references

normality

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/j.ic.2015.11.003

0 references

cites work

Q5653940

0 references

Q4452093

0 references

Mathematical Foundations of Computer Science 2004

0 references

An example of a computable absolutely normal number

0 references

A computable absolutely normal Liouville number

0 references

Entropy rates and finite-state dimension

0 references

Resource-bounded kolmogorov complexity revisited

0 references

Q4806962

0 references

Representation of left-computable \(\varepsilon \)-random reals

0 references

Finite state complexity

0 references

STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY

0 references

On partial randomness

0 references

A Theory of Program Size Formally Identical to Information Theory

0 references

Approximating the smallest grammar

0 references

Q5834367

0 references

Finite-state dimension

0 references

Feasible Depth

0 references

Algorithmic Randomness and Complexity

0 references

Q3335015

0 references

Complexity dips in random infinite binary sequences

0 references

An almost machine-independent theory of program-length complexity, sophistication, and induction

0 references

Q4828933

0 references

The dimensions of individual strings and sequences

0 references

The definition of random sequences

0 references

Complexity oscillations in infinite binary sequences

0 references

Q3611832

0 references

Q3425126

0 references

Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity

0 references

Application of Lempel-Ziv factorization to the approximation of grammar-based compression.

0 references

Endliche Automaten und Zufallsfolgen

0 references

Process complexity and effective random tests

0 references

Q4115102

0 references

Kolmogorov complexity and Hausdorff dimension

0 references

Q4218950

0 references

The Kolmogorov complexity of real numbers.

0 references

Constructive dimension equals Kolmogorov complexity

0 references

The Kolmogorov complexity of infinite words

0 references

On Oscillation-free ε-random Sequences

0 references

Phase Transition and Strong Predictability

0 references

Q4002255

0 references

Compression of individual sequences via variable-rate coding

0 references

THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

0 references

Identifiers

zbMATH Open document ID

1338.68128

0 references

DOI

10.1016/j.ic.2015.11.003

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:259039

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.ic.2015.11.003
+Normal rank
@@ Property / OpenAlex ID @@
+W2234983666
@@ Property / OpenAlex ID: W2234983666 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5653940
@@ Property / cites work: Q5653940 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4452093
@@ Property / cites work: Q4452093 / rank @@
+Normal rank
@@ Property / cites work @@
+Mathematical Foundations of Computer Science 2004
@@ Property / cites work: Mathematical Foundations of Computer Science 2004 / rank @@
+Normal rank
@@ Property / cites work @@
+An example of a computable absolutely normal number
+Normal rank
@@ Property / cites work @@
+A computable absolutely normal Liouville number
@@ Property / cites work: A computable absolutely normal Liouville number / rank @@
+Normal rank
@@ Property / cites work @@
+Entropy rates and finite-state dimension
@@ Property / cites work: Entropy rates and finite-state dimension / rank @@
+Normal rank
@@ Property / cites work @@
+Resource-bounded kolmogorov complexity revisited
@@ Property / cites work: Resource-bounded kolmogorov complexity revisited / rank @@
+Normal rank
@@ Property / cites work @@
+Q4806962
@@ Property / cites work: Q4806962 / rank @@
+Normal rank
@@ Property / cites work @@
+Representation of left-computable \(\varepsilon \)-random reals
+Normal rank
@@ Property / cites work @@
+Finite state complexity
@@ Property / cites work: Finite state complexity / rank @@
+Normal rank
@@ Property / cites work @@
+STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY
@@ Property / cites work: STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY / rank @@
+Normal rank
@@ Property / cites work @@
+On partial randomness
@@ Property / cites work: On partial randomness / rank @@
+Normal rank
@@ Property / cites work @@
+A Theory of Program Size Formally Identical to Information Theory
+Normal rank
@@ Property / cites work @@
+Approximating the smallest grammar
@@ Property / cites work: Approximating the smallest grammar / rank @@
+Normal rank
@@ Property / cites work @@
+Q5834367
@@ Property / cites work: Q5834367 / rank @@
+Normal rank
@@ Property / cites work @@
+Finite-state dimension
@@ Property / cites work: Finite-state dimension / rank @@
+Normal rank
@@ Property / cites work @@
+Feasible Depth
@@ Property / cites work: Feasible Depth / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithmic Randomness and Complexity
@@ Property / cites work: Algorithmic Randomness and Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Q3335015
@@ Property / cites work: Q3335015 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity dips in random infinite binary sequences
+Normal rank
@@ Property / cites work @@
+An almost machine-independent theory of program-length complexity, sophistication, and induction
+Normal rank
@@ Property / cites work @@
+Q4828933
@@ Property / cites work: Q4828933 / rank @@
+Normal rank
@@ Property / cites work @@
+The dimensions of individual strings and sequences
+Normal rank
@@ Property / cites work @@
+The definition of random sequences
@@ Property / cites work: The definition of random sequences / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity oscillations in infinite binary sequences
+Normal rank
@@ Property / cites work @@
+Q3611832
@@ Property / cites work: Q3611832 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3425126
@@ Property / cites work: Q3425126 / rank @@
+Normal rank
@@ Property / cites work @@
+Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
+Normal rank
@@ Property / cites work @@
+Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
+Normal rank
@@ Property / cites work @@
+Endliche Automaten und Zufallsfolgen
@@ Property / cites work: Endliche Automaten und Zufallsfolgen / rank @@
+Normal rank
@@ Property / cites work @@
+Process complexity and effective random tests
@@ Property / cites work: Process complexity and effective random tests / rank @@
+Normal rank
@@ Property / cites work @@
+Q4115102
@@ Property / cites work: Q4115102 / rank @@
+Normal rank
@@ Property / cites work @@
+Kolmogorov complexity and Hausdorff dimension
@@ Property / cites work: Kolmogorov complexity and Hausdorff dimension / rank @@
+Normal rank
@@ Property / cites work @@
+Q4218950
@@ Property / cites work: Q4218950 / rank @@
+Normal rank
@@ Property / cites work @@
+The Kolmogorov complexity of real numbers.
@@ Property / cites work: The Kolmogorov complexity of real numbers. / rank @@
+Normal rank
@@ Property / cites work @@
+Constructive dimension equals Kolmogorov complexity
+Normal rank
@@ Property / cites work @@
+The Kolmogorov complexity of infinite words
@@ Property / cites work: The Kolmogorov complexity of infinite words / rank @@
+Normal rank
@@ Property / cites work @@
+On Oscillation-free ε-random Sequences
@@ Property / cites work: On Oscillation-free ε-random Sequences / rank @@
+Normal rank
@@ Property / cites work @@
+Phase Transition and Strong Predictability
@@ Property / cites work: Phase Transition and Strong Predictability / rank @@
+Normal rank
@@ Property / cites work @@
+Q4002255
@@ Property / cites work: Q4002255 / rank @@
+Normal rank
@@ Property / cites work @@
+Compression of individual sequences via variable-rate coding
+Normal rank
@@ Property / cites work @@
+THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
+Normal rank