Automatic Kolmogorov complexity, normality, and finite-state dimension revisited

DOI10.1016/j.jcss.2020.12.003zbMath1505.68018arXiv1701.09060OpenAlexW3120179544MaRDI QIDQ2656172

Alexander Kozachinskiy, Alexander Shen

Publication date: 10 March 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1701.09060

zbMATH Keywords

finite-state dimensionnormal sequenceautomatic Kolmogorov complexityfinite-state a priori probability

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (1)

Pushdown and Lempel-Ziv depth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite state incompressible infinite sequences
• Perfect necklaces
• Nondeterministic automatic complexity of overlap-free and almost square-free words
• Normality and automata
• Finite state complexity
• On normal numbers
• Entropy rates and finite-state dimension
• Constructive dimension equals Kolmogorov complexity
• On the valuedness of finite transducers
• On encoding and decoding with two-way head machines
• Automatic Kolmogorov complexity and normality revisited
• Finite-state independence
• The asymptotic distribution of the numerals in the decimal representation of the squares of the natural numbers
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• Finite-state dimension
• The dimensions of individual strings and sequences
• Normal numbers and finite automata
• Two characterizations of finite-state dimension
• Finite-state independence and normal sequences
• Finite-state dimension and real arithmetic
• Endliche Automaten und Zufallsfolgen
• On the definition of normal numbers
• A short proof of Pillai's theorem on normal numbers
• On a paper of Niven and Zuckerman
• Around Kolmogorov Complexity: Basic Notions and Results
• Turing’s Normal Numbers: Towards Randomness
• Algorithmic Randomness and Complexity
• Coding theorems for individual sequences
• On a problem of Steinhaus about normal numbers
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• On the Complexity of Finite Sequences
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Dimension in Complexity Classes
• Normal Numbers and Computer Science
• Relations between varieties of kolmogorov complexities
• A unified approach to the definition of random sequences
• Note on Normal Decimals
• Note on normal numbers

This page was built for publication: Automatic Kolmogorov complexity, normality, and finite-state dimension revisited