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

    [img]
    Preview
    Download (291kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    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: https://doi.org/10.1007/978-3-319-50062-1_7
    Depositing User: Philippe Moser
    Date Deposited: 12 Dec 2019 15:05
    Publisher: Springer
    Refereed: Yes
    URI:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year