MURAL - Maynooth University Research Archive Library



    Finite-State Dimension and Lossy Decompressors


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

    [img]
    Preview
    Download (305kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    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)

      View Item Item control page

      Downloads

      Downloads per month over past year

      Origin of downloads