79333 20190529131324.0 doi 10.1007/978-3-319-50062-1_7 sideral 97819 ART-2017-97819 eng Albert, Pilar Bounded pushdown dimension vs lempel ziv information density 2017 Access copy available to the general public Unrestricted 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. info:eu-repo/semantics/openAccess All rights reserved http://www.europeana.eu/rights/rr-f/ info:eu-repo/semantics/article info:eu-repo/semantics/acceptedVersion (orcid)0000-0002-9109-5337 Mayordomo, Elvira Universidad de Zaragoza Moser, Phillipe 5007 570 Universidad de Zaragoza Dpto. Informát.Ingenie.Sistms. Área Lenguajes y Sistemas Inf. 10010 (2017), 95-114 Lect. notes comput. sci. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 0302-9743 331304 http://zaguan.unizar.es/record/79333/files/texto_completo.pdf Postprint 71462 http://zaguan.unizar.es/record/79333/files/texto_completo.jpg?subformat=icon icon Postprint oai:zaguan.unizar.es:79333 articulos driver 2019-05-29-11:54:11 ARTICLE