Computer Science – Computational Complexity
Scientific paper
2006-09-18
Computer Science
Computational Complexity
We found that Theorem 3.11, which was basically the motive for this paper, was already proven by Sheinwald, Ziv, and Lempel in
Scientific paper
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.
Doty David
Moser Philippe
No associations
LandOfFree
Finite-State Dimension and Lossy Decompressors does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Finite-State Dimension and Lossy Decompressors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finite-State Dimension and Lossy Decompressors will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-647198