Finite-State Dimension and Lossy Decompressors
<|reference_start|>Finite-State Dimension and Lossy Decompressors: This paper examines information-theoretic questions regarding the difficulty of compressing data versus the difficulty of decompressing data and the role that information loss plays in this interaction. Finite-state compression and decompression are shown to be of equivalent difficulty, even when the decompressors are allowed to be lossy.   Inspired by Kolmogorov complexity, this paper defines the optimal *decompression *ratio achievable on an infinite sequence by finite-state decompressors (that is, finite-state transducers outputting the sequence in question). It is shown that the optimal compression ratio achievable on a sequence S by any *information lossless* finite state compressor, known as the finite-state dimension of S, is equal to the optimal decompression ratio achievable on S by any finite-state decompressor. This result implies a new decompression characterization of finite-state dimension in terms of lossy finite-state transducers.<|reference_end|>
@article{doty2006finite-state,
    title={Finite-State Dimension and Lossy Decompressors},
    author={David Doty and Philippe Moser},
    journal={arXiv preprint arXiv:cs/0609096},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0609096},
    primaryClass={cs.CC cs.IT math.IT}
}