Bounded pushdown dimension vs Lempel Ziv information density

DOI10.1007/978-3-319-50062-1_7zbMATH Open1360.68453DBLPconf/birthday/AlbertMM17arXiv0704.2386OpenAlexW1574872460WikidataQ60578847 ScholiaQ60578847MaRDI QIDQ2970951FDOQ2970951

Authors: Pilar Albert, Elvira Mayordomo, Philippe Moser 

Publication date: 4 April 2017

Published in: Computability and Complexity (Search for Journal in Brave)

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 signicantly, 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.

Full work available at URL: https://arxiv.org/abs/0704.2386

Recommendations

• Pushdown dimension
• Lempel-Ziv Dimension for Lempel-Ziv Compression
• Pushdown compression
• On the difference between finite-state and pushdown depth
• Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression

zbMATH Keywords

finite state (bounded pushdown) dimensioninformation lossless compressorsLempel-Ziv compression algorithm

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cites Work

• Finite-state dimension
• The dimensions of individual strings and sequences
• Compression of individual sequences via variable-rate coding
• Entropy rates and finite-state dimension
• Title not available (Why is that?)
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Dimension in Complexity Classes
• Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable
• Title not available (Why is that?)
• Effective fractal dimensions
• On encoding and decoding with two-way head machines
• Title not available (Why is that?)
• Pushdown dimension

Cited In (7)

• Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable
• Pushdown and Lempel-Ziv depth
• Pushdown dimension
• Pushdown compression
• Lempel-Ziv Dimension for Lempel-Ziv Compression
• Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression
• Dimension is compression

This page was built for publication: Bounded pushdown dimension vs Lempel Ziv information density

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2970951)