Computer Science – Computational Complexity
Scientific paper
2007-04-18
Computer Science
Computational Complexity
Scientific paper
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.
Albert Pilar
Mayordomo Elvira
Moser Philippe
No associations
LandOfFree
Bounded Pushdown dimension vs Lempel Ziv information density does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Bounded Pushdown dimension vs Lempel Ziv information density, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounded Pushdown dimension vs Lempel Ziv information density will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-405458