An incompressibility theorem for automatic complexity

DOI10.1017/FMS.2021.58MaRDI QIDQ5154787zbMATH OpenOpenAlexFDO

Authors Bjørn Kjos-Hanssen

Publication date 5 October 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1747450
• On the complexity of automatic complexity
• Automaticity. I: Properties of a measure of descriptional complexity
• Kolmogorov structure functions for automatic complexity
• Automaticity. II: Descriptional complexity in the unary case

Cites work

• A formal theory of inductive inference. Part I
• A formal theory of inductive inference. Part II
• Complexity of protein folding
• Few Paths, Fewer Words: Model Selection With Automatic Structure Functions
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 1747450 (Why is no real title available?)
• Nondeterministic automatic complexity of overlap-free and almost square-free words
• On the complexity of automatic complexity
• Resource-bounded Kolmogorov complexity revisited
• Three approaches to the quantitative definition of information^*

Cited in

(3)

• Planar digraphs for automatic complexity
• scientific article; zbMATH DE number 7564405 (Why is no real title available?)
• Conditional automatic complexity and its metrics

Describes a project that uses

Uses Software

• MathOverflow

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

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