Article ID Journal Published Year Pages File Type
435616 Theoretical Computer Science 2015 11 Pages PDF
Abstract

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

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Kolmogorov structure functions for automatic complexity
Authors
,