Anupam Gupta, Viswanath Nagarajan, et al.
Operations Research
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.
Anupam Gupta, Viswanath Nagarajan, et al.
Operations Research
Elliot Linzer, M. Vetterli
Computing
Marshall W. Bern, Howard J. Karloff, et al.
Theoretical Computer Science
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011