Bounded Pushdown Dimension vs Lempel Ziv Information Density

详细信息    查看全文

• 关键词：Information lossless compressors ; Finite state (bounded pushdown) dimension ; Lempel ; Ziv compression algorithm
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10010
• 期：1
• 页码：95-114
• 参考文献：1.Athreya, K.B., Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: Effective strong dimension in algorithmic information and computational complexity. SIAM J. Comput. 37, 671–705 (2007)MathSciNet CrossRef MATH
  2.Bourke, C., Hitchcock, J.M., Vinodchandran, N.V.: Entropy rates and finite-state dimension. Theor. Comput. Sci. 349(3), 392–406 (2005)MathSciNet CrossRef MATH
  3.Dai, J.J., Lathrop, J.I., Lutz, J.H., Mayordomo, E.: Finite-state dimension. Theor. Comput. Sci. 310, 1–33 (2004)MathSciNet CrossRef MATH
  4.Doty, D., Moser, P.: Finite-state dimension and lossy decompressors. Technical report, Technical report cs.CC/0609096, arXiv (2006)
  5.Doty, D., Nichols, J.: Nichols.: pushdown dimension. Theor. Comput. Sci. 381, 105–123 (2007)MathSciNet CrossRef MATH
  6.Falconer, K.: The Geometry of Fractal Sets. Cambridge University Press, Cambridge (1985)CrossRef MATH
  7.Hariharan, S., Shankar, P.: Evaluating the role of context in syntax directed compression of xml documents. In: Proceedings of the 2006 IEEE Data Compression Conference (DCC 2006), p. 453 (2006)
  8.Hitchcock, J.M., Lutz, J.H.: The fractal geometry of complexity. SIGACT News Complex. Theory Column 36, 24–38 (2005)
  9.Huffman, D.A.: Canonical forms for information-lossless finite-state logical machines. Trans. Circ. Theory CT–6, 41–59 (1959)MATH
  10.League, C., Eng, K.: Type-based compression of xml data. In: Proceedings of the 2007 IEEE Data Compression Conference (DCC 2007), pp. 272–282 (2007)
  11.Lutz, J.H.: Dimension in complexity classes. SIAM J. Comput. 32, 1236–1259 (2003)MathSciNet CrossRef MATH
  12.Lutz, J.H.: The dimensions of individual strings and sequences. Inf. Comput. 187, 49–79 (2003)MathSciNet CrossRef MATH
  13.Lutz, J.H.: Effective fractal dimensions. Math. Logic Q. 51, 62–72 (2005)MathSciNet CrossRef MATH
  14.Mayordomo, E.: Effective fractal dimension in algorithmic information theory. In: Cooper, S.B., Löwe, B., Sorbi, A. (eds.) New Computational Paradigms: Changing Conceptions of What is Computable, pp. 259–285. Springer, New York (2008)CrossRef
  15.Mayordomo, E., Moser, P., Perifel, S.: Polylog space compression, pushdown compression, and lempel-ziv are incomparable. Theory Comput. Syst. 48, 731–766 (2011)MathSciNet CrossRef MATH
  16.Sheinwald, D., Lempel, A., Ziv, J.: On compression with two-way head machines. In: Data Compression Conference, pp. 218–227 (1991)
  17.Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theor. 24(5), 530–536 (1978)MathSciNet CrossRef MATH
  
• 作者单位：Pilar Albert (19)
  Elvira Mayordomo (19)
  Philippe Moser (20)
  
  19. Departamento de Informática e Ingeniería de Sistemas, Instituto de Investigación en Ingeniería de Aragón, Universidad de Zaragoza, 50018, Zaragoza, Spain
  20. Department of Computer Science, National University of Ireland Maynooth, Co Kildare, Ireland
  
• 丛书名：Computability and Complexity
• ISBN：978-3-319-50062-1
• 卷排序：10010

文摘

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.