{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T10:19:30Z","timestamp":1743157170315,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540958901"},{"type":"electronic","value":"9783540958918"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-540-95891-8_56","type":"book-chapter","created":{"date-parts":[[2009,1,22]],"date-time":"2009-01-22T01:19:21Z","timestamp":1232587161000},"page":"633-644","source":"Crossref","is-referenced-by-count":1,"title":["Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression"],"prefix":"10.1007","author":[{"given":"Elvira","family":"Mayordomo","sequence":"first","affiliation":[]},{"given":"Philippe","family":"Moser","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"56_CR1","unstructured":"Albert, P., Mayordomo, E., Moser, P.: Bounded pushdown dimension vs lempel ziv information density. Technical Report TR07-051, ECCC: Electronic Coloquium on Computational Complexity (2007)"},{"key":"56_CR2","unstructured":"Albert, P., Mayordomo, E., Moser, P., Perifel, S.: Pushdown compression. In: Proceedings of the 25th Symposium on Theoretical Aspects of Computer Science (STACS 2008), pp. 39\u201348 (2008)"},{"key":"56_CR3","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. Journal of Computer and System Sciences\u00a058, 137\u2013147 (1999)","journal-title":"Journal of Computer and System Sciences"},{"key":"56_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11779148_1","volume-title":"Developments in Language Theory","author":"R. Alur","year":"2006","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. In: H. Ibarra, O., Dang, Z. (eds.) DLT 2006. LNCS, vol.\u00a04036, pp. 1\u201313. Springer, Heidelberg (2006)"},{"key":"56_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-642-59136-5_3","volume-title":"Handbook of Formal Languages, Word, Language, Grammar","author":"J. Autebert","year":"1997","unstructured":"Autebert, J., Berstel, J., Boasson, L.: Context-free languages and pushdown automata. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, Word, Language, Grammar, vol.\u00a01, pp. 111\u2013174. Springer, Heidelberg (1997)"},{"issue":"8","key":"56_CR6","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1112\/jlms\/s1-8.4.254","volume":"2","author":"D.G. Champernowne","year":"1933","unstructured":"Champernowne, D.G.: Construction of decimals normal in the scale of ten. J. London Math. Soc.\u00a02(8), 254\u2013260 (1933)","journal-title":"J. London Math. Soc."},{"key":"56_CR7","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1090\/S0002-9904-1946-08657-7","volume":"52","author":"A. Copeland","year":"1946","unstructured":"Copeland, A., Erd\u00f6s, P.: Note on normal numbers. Bulletin of the American Mathematical Society\u00a052, 857\u2013860 (1946)","journal-title":"Bulletin of the American Mathematical Society"},{"key":"56_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(03)00244-5","volume":"310","author":"J.J. Dai","year":"2004","unstructured":"Dai, J.J., Lathrop, J.I., Lutz, J.H., Mayordomo, E.: Finite-state dimension. Theoretical Computer Science\u00a0310, 1\u201333 (2004)","journal-title":"Theoretical Computer Science"},{"key":"56_CR9","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.1109\/DCC.2006.34"},{"key":"56_CR10","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1109\/SFCS.1978.31","volume-title":"Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS 1978)","author":"J. Hartmanis","year":"1978","unstructured":"Hartmanis, J., Immerman, N., Mahaney, S.: One-way log-tape reductions. In: Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS 1978), pp. 65\u201372. IEEE Computer Society Press, Los Alamitos (1978)"},{"key":"56_CR11","unstructured":"Hitchcock, J.M.: Effective Fractal Dimension: Foundations and Applications. PhD thesis, Iowa State University (2003)"},{"key":"56_CR12","first-page":"202","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005)","author":"P. Indyk","year":"2005","unstructured":"Indyk, P., Woodruff, D.: Optimal approximations of the frequency moments of data streams. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pp. 202\u2013208. ACM Press, New York (2005)"},{"key":"56_CR13","doi-asserted-by":"crossref","unstructured":"Kuma, V., Madhusudan, P., Viswanathan, M.: Visibly pushdown automata for streaming xml. In: International World Wide Web Conference WWW 2007, pp. 1053\u20131062 (2007)","DOI":"10.1145\/1242572.1242714"},{"key":"56_CR14","first-page":"123","volume-title":"Compression and Complexity of Sequences 1997","author":"J.I. Lathrop","year":"1998","unstructured":"Lathrop, J.I., Strauss, M.J.: A universal upper bound on the performance of the Lempel-Ziv algorithm on maliciously-constructed data. In: Carpentieri, B. (ed.) Compression and Complexity of Sequences 1997, pp. 123\u2013135. IEEE Computer Society Press, Los Alamitos (1998)"},{"key":"56_CR15","doi-asserted-by":"crossref","unstructured":"League, C., Eng, K.: Type-based compression of xml data. In: Proceedings of the 2007 IEEE Data Compression Conference (DCC 2007), pp. 272\u2013282 (2007)","DOI":"10.1109\/DCC.2007.79"},{"key":"56_CR16","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"A. Lempel","year":"1978","unstructured":"Lempel, A., Ziv, J.: Compression of individual sequences via variable rate coding. IEEE Transaction on Information Theory\u00a024, 530\u2013536 (1978)","journal-title":"IEEE Transaction on Information Theory"},{"key":"56_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1007\/11549345_58","volume-title":"Mathematical Foundations of Computer Science 2005","author":"M. L\u00f3pez-Vald\u00e9s","year":"2005","unstructured":"L\u00f3pez-Vald\u00e9s, M., Mayordomo, E.: Dimension is compression. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 676\u2013685. Springer, Heidelberg (2005)"},{"key":"56_CR18","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/978-0-387-68546-5_12","volume-title":"New Computational Paradigms: Changing Conceptions of What is Computable","author":"E. Mayordomo","year":"2008","unstructured":"Mayordomo, E.: Effective fractal dimension in algorithmic information theory. In: New Computational Paradigms: Changing Conceptions of What is Computable, pp. 259\u2013285. Springer, Heidelberg (2008)"},{"key":"56_CR19","doi-asserted-by":"crossref","unstructured":"Sculley, D., Brodley, C.E.: Compression and machine learning: A new perspective on feature space vectors. In: Proceedings of the Data Compression Conference (DCC 2006), pp. 332\u2013341 (2006)","DOI":"10.1109\/DCC.2006.13"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2009: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-95891-8_56","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T08:22:22Z","timestamp":1558081342000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-95891-8_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783540958901","9783540958918"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-95891-8_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}