MURAL - Maynooth University Research Archive Library

    Bounded Pushdown Dimension vs Lempel Ziv Information Density

    Albert, Pilar and 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

    Download (291kB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    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:
    Depositing User: Philippe Moser
    Date Deposited: 12 Dec 2019 15:05
    Publisher: Springer
    Refereed: Yes
    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 per month over past year

    Origin of downloads