Automatic Complexity of Strings
Jeffrey O. Shallit, Mingwei Wang · 2001
We define a new measure of complexity for finite strings, called automatic complexity and denoted $A(x)$. Although $A(x)$ is analogous to Kolmogorov-Chaitin complexity, it has the advantage of being computable. We give upper and lower bounds for $A(x)$, and estimate it for some specific strings.