{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T21:23:35Z","timestamp":1746393815334},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T00:00:00Z","timestamp":1565222400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T00:00:00Z","timestamp":1565222400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["LO748\/10-1"],"award-info":[{"award-number":["LO748\/10-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N510129\/1"],"award-info":[{"award-number":["EP\/N510129\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/J017728\/2"],"award-info":[{"award-number":["EP\/J017728\/2"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s00224-019-09942-y","type":"journal-article","created":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T07:02:48Z","timestamp":1565247768000},"page":"141-176","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Grammar-Based Compression of Unranked Trees"],"prefix":"10.1007","volume":"64","author":[{"given":"Adri\u00e0","family":"Gasc\u00f3n","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Maneth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carl Philipp","family":"Reh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kurt","family":"Sieber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,8,8]]},"reference":[{"issue":"4","key":"9942_CR1","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1007\/s00224-015-9617-5","volume":"57","author":"S Abiteboul","year":"2015","unstructured":"Abiteboul, S., Bourhis, P., Vianu, V.: Highly expressive query languages for unordered data trees. Theory Comput. Syst. 57(4), 927\u2013966 (2015)","journal-title":"Theory Comput. Syst."},{"key":"9942_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"9942_CR3","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.ic.2014.12.012","volume":"243","author":"P Bille","year":"2015","unstructured":"Bille, P., G\u00f8rtz, I.L., Landau, G.M., Weimann, O.: Tree compression with top trees. Inf. Comput. 243, 166\u2013177 (2015)","journal-title":"Inf. Comput."},{"key":"9942_CR4","doi-asserted-by":"crossref","unstructured":"Boiret, A., Hugot, V., Niehren, J., Treinen, R.: Logics for unordered trees with data constraints on siblings. In: Proceedings of LATA 2015, Volume 8977 of Lecture Notes in Computer Science, pp 175\u2013187. Springer (2015)","DOI":"10.1007\/978-3-319-15579-1_13"},{"key":"9942_CR5","unstructured":"Boja\u0144czyk, M., Walukiewicz, I.: Forest algebras. In: Proceedings of Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas], Volume 2 of Texts in Logic and Games, pp 107\u2013132. Amsterdam University Press (2008)"},{"issue":"2","key":"9942_CR6","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00224-014-9593-1","volume":"57","author":"I Boneva","year":"2015","unstructured":"Boneva, I., Ciucanu, R., Staworko, S.: Schemas for unordered XML on a DIME. Theory Comput. Syst. 57(2), 337\u2013376 (2015)","journal-title":"Theory Comput. Syst."},{"issue":"4-5","key":"9942_CR7","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. Inf. Syst. 33(4-5), 456\u2013474 (2008)","journal-title":"Inf. Syst."},{"issue":"7","key":"9942_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 Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9942_CR9","unstructured":"Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., L\u00f6ding, C., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications. Available at: \nhttp:\/\/www.grappa.univ-lille3.fr\/tata\n\n (2007)"},{"key":"9942_CR10","unstructured":"Creus, C., Gasc\u00f3n, A., Godoy, G.: One-context unification with STG-compressed terms is in NP. In: Proceedings of RTA 2012, volume 15 of LIPIcs, pp 149\u2013164. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2012)"},{"key":"9942_CR11","unstructured":"Dudek, B., Gawrychowski, P.: Slowing down top trees for better worst-case bounds. In: Proceedings of CPM 2018, Volume 105 of LIPIcs, pp 16:1\u201316:8. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"9942_CR12","doi-asserted-by":"crossref","unstructured":"Ganardi, M., Jez, A., Lohrey, M.: Balancing straight-line programs. Technical report, arXiv:\n1902.03568\n\n (2019)","DOI":"10.1109\/FOCS.2019.00073"},{"issue":"4","key":"9942_CR13","doi-asserted-by":"publisher","first-page":"26,1","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 Trans. Comput. Logic 12(4), 26,1\u201326,37 (2011)","journal-title":"ACM Trans. Comput. Logic"},{"key":"9942_CR14","doi-asserted-by":"crossref","unstructured":"Gasc\u00f3n, A., Lohrey, M., Maneth, S., Reh, C.P., Sieber, K.: Grammar-based compression of unranked trees. In: Proceedings of CSR 2018, Volume 10846 of Lecture Notes in Computer Science, pp 118\u2013131. Springer (2018)","DOI":"10.1007\/978-3-319-90530-3_11"},{"key":"9942_CR15","unstructured":"Hirshfeld, Y., Jerrum, M., Moller, F.: A polynomial-time algorithm for deciding equivalence of normed context-free processes. In: Proceedings of FOCS 1994, pp 623\u2013631. IEEE Computer Society (1994)"},{"key":"9942_CR16","doi-asserted-by":"crossref","unstructured":"H\u00fcbschle-Schneider, L., Raman, R.: Tree compression with top trees revisited. In: Proceedings of SEA 2015, Volume 9125 of Lecture Notes in Computer Science, pp 15\u201327. Springer (2015)","DOI":"10.1007\/978-3-319-20086-6_2"},{"issue":"3","key":"9942_CR17","first-page":"20,1","volume":"11","author":"A Je\u017b","year":"2015","unstructured":"Je\u017b, A.: Faster fully compressed pattern matching by recompression. ACM Trans. Algor. 11(3), 20,1\u201320,43 (2015)","journal-title":"ACM Trans. Algor."},{"key":"9942_CR18","doi-asserted-by":"crossref","unstructured":"Je\u017b, A.: Context unification is in PSPACE. In: Proceedings of ICALP 2014, Part II, Volume 8573 of Lecture Notes in Computer Science, pp 244\u2013255, Springer (2014)","DOI":"10.1007\/978-3-662-43951-7_21"},{"key":"9942_CR19","unstructured":"Krebs, A., Limaye, N., Ludwig, M.: A unified method for placing problems in polylogarithmic depth. In: Proceedings of FSTTCS 2017, Volume 93 of LIPIcs, pp 36:36\u201336:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"issue":"2","key":"9942_CR20","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 Complex. Cryptol. 4(2), 241\u2013299 (2012)","journal-title":"Groups Complex. Cryptol."},{"key":"9942_CR21","doi-asserted-by":"crossref","unstructured":"Lohrey, M.: Grammar-based tree compression. In: Proceedings of DLT 2015, Volume 9168 of Lecture Notes in Computer Science, pp 46\u201357. Springer (2015)","DOI":"10.1007\/978-3-319-21500-6_3"},{"issue":"8","key":"9942_CR22","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. Inf. Syst. 38(8), 1150\u20131167 (2013)","journal-title":"Inf. Syst."},{"key":"9942_CR23","doi-asserted-by":"crossref","unstructured":"Lohrey, M., Maneth, S., Peternek, F.: Compressed tree canonization. In: Proceedings of ICALP 2015, Part II, Volume 9135 of Lecture Notes in Computer Science, pp 337\u2013349. Springer (2015)","DOI":"10.1007\/978-3-662-47666-6_27"},{"key":"9942_CR24","unstructured":"Lohrey, M., Maneth, S., Reh, C.P.: Compression of unordered XML trees. In: Proceedings of ICDT 2017, Volume 68 of LIPIcs, pp 18:1\u201318:17. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"issue":"5","key":"9942_CR25","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. J. Comput. Syst. Sci. 78(5), 1651\u20131669 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"9942_CR26","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.ipl.2019.03.001","volume":"147","author":"M Lohrey","year":"2019","unstructured":"Lohrey, M., Reh, C.P., Sieber, K.: Optimal top dag construction. Inf. Process. Lett. 147, 27\u201331 (2019)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9942_CR27","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02522825","volume":"17","author":"K Mehlhorn","year":"1997","unstructured":"Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica 17(2), 183\u2013198 (1997)","journal-title":"Algorithmica"},{"key":"9942_CR28","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: Proceedings of ESA 1994, Volume 855 of Lecture Notes in Computer Science, pp 460\u2013470. Springer (1994)","DOI":"10.1007\/BFb0049431"},{"key":"9942_CR29","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/j.datak.2011.11.003","volume":"72","author":"S Sundaram","year":"2012","unstructured":"Sundaram, S., Madria, S.K.: A change detection system for unordered XML data using a relational model. Data & Knowl. Eng. 72, 257\u2013284 (2012)","journal-title":"Data & Knowl. Eng."},{"issue":"6","key":"9942_CR30","doi-asserted-by":"publisher","first-page":"1113","DOI":"10.1109\/TCYB.2014.2345579","volume":"45","author":"S Zhang","year":"2015","unstructured":"Zhang, S., Du, Z., Wang, J.T.: New techniques for mining frequent patterns in unordered trees. IEEE Trans. Cybern. 45(6), 1113\u20131125 (2015)","journal-title":"IEEE Trans. Cybern."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09942-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09942-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09942-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,6]],"date-time":"2020-08-06T23:19:07Z","timestamp":1596755947000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09942-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,8]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["9942"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09942-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,8]]},"assertion":[{"value":"8 August 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}