Doty, David and Moser, Philippe (2006) Finite-State Dimension and Lossy Decompressors. Technical Report. arXiv.

Preview

Download (305kB) | Preview

Abstract

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.

Item Type:	Monograph (Technical Report)
Additional Information:	We found that Theorem 3.11, which was basically the motive for this paper, was already proven by Sheinwald, Ziv, and Lempel in 1991 and 1995 papers.
Keywords:	Finite-State Dimension; Lossy Decompressors;
Academic Unit:	Faculty of Science and Engineering > Computer Science
Item ID:	8246
Identification Number:	arXiv:cs/0609096
Depositing User:	Philippe Moser
Date Deposited:	29 May 2017 14:34
Publisher:	arXiv
URI:
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads