An incompressibility theorem for automatic complexity

DOI10.1017/fms.2021.58OpenAlexW3199072391MaRDI QIDQ5154787

Bjørn Kjos-Hanssen

Publication date: 5 October 2021

Published in: Forum of Mathematics, Sigma (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Uses Software

• MathOverflow

Cites Work

• Unnamed Item
• Unnamed Item
• Nondeterministic automatic complexity of overlap-free and almost square-free words
• Complexity of protein folding
• On the complexity of automatic complexity
• Resource-Bounded Kolmogorov Complexity Revisited
• Three approaches to the quantitative definition of information^*
• A formal theory of inductive inference. Part I
• A formal theory of inductive inference. Part II
• Few Paths, Fewer Words: Model Selection With Automatic Structure Functions

This page was built for publication: An incompressibility theorem for automatic complexity