Bounded pushdown dimension vs Lempel Ziv information density

DOI10.1007/978-3-319-50062-1_7MaRDI QIDQ2970951zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Pilar Albert, Elvira Mayordomo, Philippe Moser

Publication date 4 April 2017

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

Full work available at URL https://arxiv.org/abs/0704.2386, http://mural.maynoothuniversity.ie/12014/1/Moser_Bounded_CC_2017.pdf

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3941840 (Why is no real title available?)
• scientific article; zbMATH DE number 5269064 (Why is no real title available?)
• scientific article; zbMATH DE number 3266639 (Why is no real title available?)
• Compression of individual sequences via variable-rate coding
• Dimension in Complexity Classes
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Effective fractal dimensions
• Entropy rates and finite-state dimension
• Finite-state dimension
• On encoding and decoding with two-way head machines
• Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable
• Pushdown dimension
• The dimensions of individual strings and sequences

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)