Bounded Pushdown dimension vs Lempel Ziv information density

Simple item page
dc.creatorAlbert, Pilar
dc.creatorMayordomo, Elvira
dc.creatorMoser, Philippe
dc.date2007-04-18
dc.date.accessioned2026-07-07T08:15:57Z
dc.date.available2026-07-07T08:15:57Z
dc.descriptionIn 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.
dc.identifierhttps://arxiv.org/abs/0704.2386
dc.identifierhttp://arxiv.org/abs/0704.2386
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/133616
dc.subjectComputational Complexity
dc.subjectInformation Theory
dc.titleBounded Pushdown dimension vs Lempel Ziv information density
dc.typetext

Files

Collections

arXiv