MURAL - Maynooth University Research Archive Library



    Bounded Pushdown Dimension vs Lempel Ziv Information Density


    Albert, Pilar, Mayordomo, Elvira and Moser, Philippe (2017) Bounded Pushdown Dimension vs Lempel Ziv Information Density. In: Computabilityand Complexity: Essays Dedicated to Rodney G. Downeyon the Occasion of His 60th Birthday. Lecture Notes in Computer Science (10010). Springer, Cham, Switzerland, pp. 95-114. ISBN 978-3-319-50061-4

    [thumbnail of Moser_Bounded_CC_2017.pdf]
    Preview
    Text
    Moser_Bounded_CC_2017.pdf

    Download (291kB) | Preview

    Abstract

    In this paper we introduce a variant of pushdown dimension called bounded pushdown (BPD) dimension, that measures the density of information contained in a sequence, relative to a BPD automata, i.e. a finite state machine equipped with an extra infinite memory stack, with the additional requirement that every input symbol only allows a bounded number of stack movements. BPD automata are a natural real-time restriction of pushdown automata. We show that BPD dimension is a robust notion by giving an equivalent characterization of BPD dimension in terms of BPD compressors. We then study the relationships between BPD compression, and the standard Lempel-Ziv (LZ) compression algorithm, and show that in contrast to the finite-state compressor case, LZ is not universal for bounded pushdown compressors in a strong sense: we construct a sequence that LZ fails to compress significantly, but that is compressed by at least a factor 2 by a BPD compressor. As a corollary we obtain a strong separation between finite-state and BPD dimension.
    Item Type: Book Section
    Keywords: Information lossless compressors; Finite state (bounded pushdown) dimension; Lempel-Ziv compression algorithm;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 12014
    Identification Number: 10.1007/978-3-319-50062-1_7
    Depositing User: Philippe Moser
    Date Deposited: 12 Dec 2019 15:05
    Publisher: Springer
    Refereed: Yes
    Related URLs:
    URI: https://mural.maynoothuniversity.ie/id/eprint/12014
    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
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads