000079333 001__ 79333 000079333 005__ 20190529131324.0 000079333 0247_ $$2doi$$a10.1007/978-3-319-50062-1_7 000079333 0248_ $$2sideral$$a97819 000079333 037__ $$aART-2017-97819 000079333 041__ $$aeng 000079333 100__ $$aAlbert, Pilar 000079333 245__ $$aBounded pushdown dimension vs lempel ziv information density 000079333 260__ $$c2017 000079333 5060_ $$aAccess copy available to the general public$$fUnrestricted 000079333 5203_ $$aIn 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. 000079333 540__ $$9info:eu-repo/semantics/openAccess$$aAll rights reserved$$uhttp://www.europeana.eu/rights/rr-f/ 000079333 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/acceptedVersion 000079333 700__ $$0(orcid)0000-0002-9109-5337$$aMayordomo, Elvira$$uUniversidad de Zaragoza 000079333 700__ $$aMoser, Phillipe 000079333 7102_ $$15007$$2570$$aUniversidad de Zaragoza$$bDpto. Informát.Ingenie.Sistms.$$cÁrea Lenguajes y Sistemas Inf. 000079333 773__ $$g10010 (2017), 95-114$$pLect. notes comput. sci.$$tLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)$$x0302-9743 000079333 8564_ $$s331304$$uhttps://zaguan.unizar.es/record/79333/files/texto_completo.pdf$$yPostprint 000079333 8564_ $$s71462$$uhttps://zaguan.unizar.es/record/79333/files/texto_completo.jpg?subformat=icon$$xicon$$yPostprint 000079333 909CO $$ooai:zaguan.unizar.es:79333$$particulos$$pdriver 000079333 951__ $$a2019-05-29-11:54:11 000079333 980__ $$aARTICLE