Abstract :
Shannon´s self-information of a string is generalized to its complexity relative to the class of finite-state-machine (FSM) defined sources. Unlike an earlier generalization, the new one is valid for both short and long strings. The definition is justified in part by a theorem stating that, asymptotically, the mean complexity provides a tight lower bound for the mean length of all so-called regular codes. This also generalizes Shannon´s noiseless coding theorem. For a large subclass of FSM sources a simple algorithm is described for computing the complexity.
