Kolmogorov structure functions for automatic complexity in computational statistics

DOI10.1007/978-3-319-12691-3_49MaRDI QIDQ2942440zbMATH OpenOpenAlexFDO

Authors Bjørn Kjos-Hanssen

Publication date 11 September 2015

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: For a finite word $w$ we define and study the Kolmogorov structure function $h_w$ for nondeterministic automatic complexity. We prove upper bounds on $h_w$ that appear to be quite sharp, based on numerical evidence.

Recommendations

• Kolmogorov structure functions for automatic complexity
• Few Paths, Fewer Words: Model Selection With Automatic Structure Functions
• scientific article; zbMATH DE number 1747450
• Automaticity. I: Properties of a measure of descriptional complexity
• Kolmogorov's Structure Functions and Model Selection

Cites work

• scientific article; zbMATH DE number 1747450 (Why is no real title available?)
• Kolmogorov structure functions for automatic complexity in computational statistics
• Kolmogorov's Structure Functions and Model Selection
• Nondeterministic automatic complexity of almost square-free and strongly cube-free words
• The Kolmogorov complexity of infinite words
• The Longest Run of Heads

Cited in

(3)

• Kolmogorov structure functions for automatic complexity in computational statistics
• Kolmogorov structure functions for automatic complexity
• Effectively closed sets of measures and randomness

This page was built for publication: Kolmogorov structure functions for automatic complexity in computational statistics

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