Kolmogorov structure functions for automatic complexity

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.

arXiv commentPreliminary version: "Kolmogorov structure functions for automatic complexity in computational statistics", Lecture Notes in Comput. Sci., vol. 8881, Springer, Cham, 2014, 652--665, 8th International Conference on Combinatorial Optimization and Applications (COCOA 2014)

Cited by in corpus (1)

• Pricing complexity options