Bounded Pushdown Dimension vs Lempel Ziv Information Density

Autores

Albert, P; Mayordomo, E; Moser, P

Revista

COMPUTABILITY AND COMPLEXITY: ESSAYS DEDICATED TO RODNEY G. DOWNEY ON THE OCCASION OF HIS 60TH BIRTHDAY

Año: 2017 Volumen: 10010 Páginas: 95-114

Editor:

SPRINGER INTERNATIONAL PUBLISHING AG

DOI:

10.1007/978-3-319-50062-1\_7

Resumen

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.

Palabras clave

Information ; lossless ; compressors ; Finite ; state ; (bounded ; pushdown) ; dimension ; Lempel-Ziv ; compression ; algorithm

Afiliación

Mayordomo, E (Reprint Author), Univ Zaragoza, Dept Informat & Ingn Sistemas, Inst Invest Ingn Aragon, Zaragoza 50018, Spain.
Albert, Pilar; Mayordomo, Elvira, Univ Zaragoza, Dept Informat & Ingn Sistemas, Inst Invest Ingn Aragon, Zaragoza 50018, Spain.
Moser, Philippe, Natl Univ Ireland Maynooth, Dept Comp Sci, Maynooth, Kildare, Ireland.