Matthias Kaiserswerth
IEEE/ACM Transactions on Networking
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. Copyright © 1986 by The Institute of Electrical and Electronics Engineers, Inc.
Matthias Kaiserswerth
IEEE/ACM Transactions on Networking
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
Bowen Zhou, Bing Xiang, et al.
SSST 2008
Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008