A quantitative analysis of OS noise
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011
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.
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011
Anupam Gupta, Viswanath Nagarajan, et al.
Operations Research
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
Thomas R. Puzak, A. Hartstein, et al.
CF 2007