Representing information with computational resource bounds
Daby Sow, Alexandros Eleftheriadis · 2002
A general framework for data compression, is which computational resource bounds are introduced at both the encoding and decoding end, is presented. We move away from Shannon's (1948) traditional communication system by introducing some structure at the decoder and model it by a Turing machine with finite computational resources. Information is measured using the resource bounded Kolmogorov (1965) complexity. In this setting, we investigate the design of efficient lossy encoders.