{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T22:07:15Z","timestamp":1784844435997,"version":"3.55.0"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319214993","type":"print"},{"value":"9783319215006","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21500-6_3","type":"book-chapter","created":{"date-parts":[[2015,7,17]],"date-time":"2015-07-17T08:07:44Z","timestamp":1437120464000},"page":"46-57","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Grammar-Based Tree Compression"],"prefix":"10.1007","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,7,18]]},"reference":[{"issue":"18\u201319","key":"3_CR1","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1016\/j.ipl.2010.07.004","volume":"110","author":"T Akutsu","year":"2010","unstructured":"Akutsu, T.: A bisection algorithm for grammar-based compression of ordered trees. Information Processing Letters 110(18\u201319), 815\u2013820 (2010)","journal-title":"Information Processing Letters"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/978-3-642-39206-1_14","volume-title":"Automata, Languages, and Programming","author":"P Bille","year":"2013","unstructured":"Bille, P., G\u00f8rtz, I.L., Landau, G.M., Weimann, O.: Tree compression with top trees. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 160\u2013171. Springer, Heidelberg (2013)"},{"key":"3_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9544-x","author":"M Bousquet-M\u00e9lou","year":"2014","unstructured":"Bousquet-M\u00e9lou, M., Lohrey, M., Maneth, S., Noeth, E.: XML compression via DAGs. Theory of Computing Systems (2014). doi:10.1007\/s00224-014-9544-x","journal-title":"Theory of Computing Systems"},{"issue":"2","key":"3_CR4","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"RP Brent","year":"1974","unstructured":"Brent, R.P.: The parallel evaluation of general arithmetic expressions. Journal of the Association for Computing Machinery 21(2), 201\u2013206 (1974)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Buneman, P., Grohe, M., Koch, C.: Path queries on compressed XML. In: Proceedings of VLDB 2003, pp. 141\u2013152. Morgan Kaufmann (2003)","DOI":"10.1016\/B978-012722442-8\/50021-5"},{"issue":"4\u20135","key":"3_CR6","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.is.2008.01.004","volume":"33","author":"G Busatto","year":"2008","unstructured":"Busatto, G., Lohrey, M., Maneth, S.: Efficient memory representation of XML document trees. Information Systems 33(4\u20135), 456\u2013474 (2008)","journal-title":"Information Systems"},{"key":"3_CR7","unstructured":"Carles Creus, A.G., Godoy, G.: One-context unification with STG-compressed terms is in NP. In: Proceedings of RTA 2012, vol. 15 of LIPIcs, pp. 149\u2013164. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2012)"},{"issue":"7","key":"3_CR8","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Lehman, A., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Transactions on Information Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"key":"3_CR9","unstructured":"Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., L\u00f6ding, C., Tison, S., Tommasi, M.: Tree automata techniques and applications (2007). http:\/\/tata.gforge.inria.fr\/"},{"issue":"4","key":"3_CR10","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1145\/322217.322228","volume":"27","author":"PJ Downey","year":"1980","unstructured":"Downey, P.J., Sethi, R., Tarjan, R.E.: Variations on the common subexpression problem. Journal of the Association for Computing Machinery 27(4), 758\u2013771 (1980)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/BFb0032034","volume-title":"Automata, Languages and Programming","author":"P Flajolet","year":"1990","unstructured":"Flajolet, P., Sipala, P., Steyaert, J.-M.: Analytic variations on the common subexpression problem. In: Paterson, M. (ed.) ICALP 1990. LNCS, vol. 443, pp. 220\u2013234. Springer, Heidelberg (1990)"},{"key":"3_CR12","unstructured":"Frick, M., Grohe, M., Koch, C.: Query evaluation on compressed trees (extended abstract). In: Proceedings of LICS 2003, pp. 188\u2013197. IEEE Computer Society Press (2003)"},{"issue":"4","key":"3_CR13","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/1970398.1970402","volume":"12","author":"A Gasc\u00f3n","year":"2011","unstructured":"Gasc\u00f3n, A., Godoy, G., Schmidt-Schau\u00df, M.: Unification and matching on compressed terms. ACM Transactions on Computational Logic 12(4), 26 (2011)","journal-title":"ACM Transactions on Computational Logic"},{"issue":"1&2","key":"3_CR14","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0304-3975(95)00064-X","volume":"158","author":"Y Hirshfeld","year":"1996","unstructured":"Hirshfeld, Y., Jerrum, M., Moller, F.: A polynomial algorithm for deciding bisimilarity of normed context-free processes. Theoretical Computer Science 158(1&2), 143\u2013159 (1996)","journal-title":"Theoretical Computer Science"},{"key":"3_CR15","unstructured":"Hucke, D., Lohrey, M., Noeth, E.: Constructing small tree grammars and small circuits for formulas. In: Proceedings of FSTTCS 2014, vol. 29 of LIPIcs, pp. 457\u2013468. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2014)"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/978-3-642-38905-4_17","volume-title":"Combinatorial Pattern Matching","author":"A Je\u017c","year":"2013","unstructured":"Je\u017c, A.: Approximation of grammar-based compression via recompression. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 165\u2013176. Springer, Heidelberg (2013)"},{"key":"3_CR17","unstructured":"Je\u017c, A., Lohrey, M.: Approximation of smallest linear tree grammars. In: Proceedings of STACS 2014, vol. 25 of LIPIcs, pp. 445\u2013457. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2014)"},{"issue":"3","key":"3_CR18","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1109\/18.841160","volume":"46","author":"JC Kieffer","year":"2000","unstructured":"Kieffer, J.C., Yang, E.H.: Grammar-based codes: A new class of universal lossless source codes. IEEE Transactions on Information Theory 46(3), 737\u2013754 (2000)","journal-title":"IEEE Transactions on Information Theory"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Kobayashi, N., Matsuda, K., Shinohara, A.: Functional programs as compressed data. In: Proceedings of PEPM 2012, pp. 121\u2013130. ACM Press (2012)","DOI":"10.1145\/2103746.2103770"},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Larsson, N.J., Moffat, A.: Offline dictionary-based compression. In: Proceedings of DCC 1999, pp. 296\u2013305. IEEE Computer Society Press (1999)","DOI":"10.1109\/DCC.1999.755679"},{"issue":"3","key":"3_CR21","doi-asserted-by":"publisher","first-page":"1113","DOI":"10.1137\/050645403","volume":"38","author":"J Levy","year":"2008","unstructured":"Levy, J., Schmidt-Schau\u00df, M., Villaret, M.: The complexity of monadic second-order unification. SIAM Journal on Computing 38(3), 1113\u20131140 (2008)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Lindell, S.: A logspace algorithm for tree canonization (extended abstract). In: Proceedings of STOC 1992, pp. 400\u2013404. ACM Press (1992)","DOI":"10.1145\/129712.129750"},{"key":"3_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/3-540-45127-7_16","volume-title":"Rewriting Techniques and Applications","author":"M Lohrey","year":"2001","unstructured":"Lohrey, M.: On the parallel complexity of tree automata. In: Middeldorp, A. (ed.) RTA 2001. LNCS, vol. 2051, pp. 201\u2013215. Springer, Heidelberg (2001)"},{"issue":"2","key":"3_CR24","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on SLP-compressed strings: A survey. Groups Complexity Cryptology 4(2), 241\u2013299 (2012)","journal-title":"Groups Complexity Cryptology"},{"issue":"2","key":"3_CR25","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/j.tcs.2006.07.024","volume":"363","author":"M Lohrey","year":"2006","unstructured":"Lohrey, M., Maneth, S.: The complexity of tree automata and XPath on grammar-compressed trees. Theoretical Computer Science 363(2), 196\u2013210 (2006)","journal-title":"Theoretical Computer Science"},{"issue":"8","key":"3_CR26","doi-asserted-by":"publisher","first-page":"1150","DOI":"10.1016\/j.is.2013.06.006","volume":"38","author":"M Lohrey","year":"2013","unstructured":"Lohrey, M., Maneth, S., Mennicke, R.: XML tree structure compression using RePair. Information Systems 38(8), 1150\u20131167 (2013)","journal-title":"Information Systems"},{"key":"3_CR27","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/978-3-662-47666-6_27","volume-title":"Automata, Languages, and Programming","author":"Markus Lohrey","year":"2015","unstructured":"Lohrey, M., Maneth, S., Peternek, F.: Compressed tree canonization.Technical report, arXiv.org (2015). http:\/\/arxiv.org\/abs\/1502.04625. An extended abstract will appear in Proceedings of ICALP 2015"},{"issue":"5","key":"3_CR28","doi-asserted-by":"publisher","first-page":"1651","DOI":"10.1016\/j.jcss.2012.03.003","volume":"78","author":"M Lohrey","year":"2012","unstructured":"Lohrey, M., Maneth, S., Schmidt-Schau\u00df, M.: Parameter reduction and automata evaluation for grammar-compressed trees. Journal of Computer and System Sciences 78(5), 1651\u20131669 (2012)","journal-title":"Journal of Computer and System Sciences"},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.ic.2013.01.002","volume":"224","author":"M Lohrey","year":"2013","unstructured":"Lohrey, M., Mathissen, C.: Isomorphism of regular trees and words. Information and Computation 224, 71\u2013105 (2013)","journal-title":"Information and Computation"},{"key":"3_CR30","unstructured":"Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality-tests in polylogarithmic time. In: Proceedings of SODA 1994, pp. 213\u2013222. ACM\/SIAM (1994)"},{"key":"3_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"Algorithms - ESA \u201994","author":"W Plandowski","year":"1994","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 460\u2013470. Springer, Heidelberg (1994)"},{"issue":"1\u20133","key":"3_CR32","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theoretical Computer Science 302(1\u20133), 211\u2013222 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"2\u20134","key":"3_CR33","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1016\/j.jda.2004.08.016","volume":"3","author":"H Sakamoto","year":"2005","unstructured":"Sakamoto, H.: A fully linear-time approximation algorithm for grammar-based compression. Journal of Discrete Algorithms 3(2\u20134), 416\u2013430 (2005)","journal-title":"Journal of Discrete Algorithms"},{"key":"3_CR34","unstructured":"Schmidt-Schau\u00df, M.: Polynomial equality testing for terms with shared substructures. Technical Report Report 21, Institut f\u00fcr Informatik, J. W. Goethe-Universit\u00e4t Frankfurt am Main (2005)"},{"key":"3_CR35","unstructured":"Schmidt-Schau\u00df, M.: Matching of compressed patterns with character-variables. In: Proceedings of RTA 2012, vol. 15 of LIPIcs, pp. 272\u2013287. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2012)"},{"key":"3_CR36","doi-asserted-by":"crossref","first-page":"29","DOI":"10.4204\/EPTCS.110.5","volume":"110","author":"Manfred Schmidt-Schauss","year":"2013","unstructured":"Schmidt-Schau\u00df, M.: Linear compressed pattern matching for polynomial rewriting (extended abstract). In: Proceedings of TERMGRAPH 2013, vol. 110 of EPTCS, pp. 29\u201340 (2013)","journal-title":"Electronic Proceedings in Theoretical Computer Science"},{"key":"3_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/978-3-642-24364-6_16","volume-title":"Frontiers of Combining Systems","author":"M Schmidt-Schauss","year":"2011","unstructured":"Schmidt-Schauss, M., Sabel, D., Anis, A.: Congruence closure of compressed terms in polynomial time. In: Tinelli, C., Sofronie-Stokkermans, V. (eds.) FroCoS 2011. LNCS, vol. 6989, pp. 227\u2013242. Springer, Heidelberg (2011)"},{"issue":"3","key":"3_CR38","doi-asserted-by":"publisher","first-page":"1373","DOI":"10.1109\/TIT.2013.2295392","volume":"60","author":"J Zhang","year":"2014","unstructured":"Zhang, J., Yang, E.-H., Kieffer, J.C.: A universal grammar-based code for lossless compression of binary trees. IEEE Transactions on Information Theory 60(3), 1373\u20131386 (2014)","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21500-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T13:11:49Z","timestamp":1676466709000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21500-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319214993","9783319215006"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21500-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"18 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}