{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T22:26:17Z","timestamp":1768343177511,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2017,7,24]],"date-time":"2017-07-24T00:00:00Z","timestamp":1500854400000},"content-version":"unspecified","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"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00453-017-0331-3","type":"journal-article","created":{"date-parts":[[2017,7,24]],"date-time":"2017-07-24T10:03:54Z","timestamp":1500890634000},"page":"2082-2105","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Constant-Time Tree Traversal and Subtree Equality Check for Grammar-Compressed Trees"],"prefix":"10.1007","volume":"80","author":[{"given":"Markus","family":"Lohrey","sequence":"first","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"}]}],"member":"297","published-online":{"date-parts":[[2017,7,24]]},"reference":[{"key":"331_CR1","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Proceedings of LATIN 2000. Lecture Notes in Computer Science, vol.\u00a01776, pp. 88\u201394. Springer, Berlin (2000)","DOI":"10.1007\/10719839_9"},{"key":"331_CR2","doi-asserted-by":"crossref","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."},{"issue":"3","key":"331_CR3","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/130936889","volume":"44","author":"P Bille","year":"2015","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings and trees. SIAM J. Comput. 44(3), 513\u2013539 (2015)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"331_CR4","doi-asserted-by":"crossref","first-page":"1322","DOI":"10.1007\/s00224-014-9544-x","volume":"57","author":"M Bousquet-M\u00e9lou","year":"2014","unstructured":"Bousquet-M\u00e9lou, M., Lohrey, M., Maneth, S., Noeth, E.: XML compression via DAGs. Theory Comput. Syst. 57(4), 1322\u20131371 (2014)","journal-title":"Theory Comput. Syst."},{"issue":"4\u20135","key":"331_CR5","doi-asserted-by":"crossref","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\u20135), 456\u2013474 (2008)","journal-title":"Inf. Syst."},{"issue":"1&2","key":"331_CR6","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(94)00183-J","volume":"145","author":"J Cai","year":"1995","unstructured":"Cai, J., Paige, R.: Using multiset discrimination to solve language processing problems without hashing. Theor. Comput. Sci. 145(1&2), 189\u2013228 (1995)","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"331_CR7","doi-asserted-by":"crossref","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":"331_CR8","unstructured":"Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., L\u00f6ding, C., Tison, S., Tommasi, M.: Tree automata techniques and applications. http:\/\/tata.gforge.inria.fr\/ (2007)"},{"key":"331_CR9","doi-asserted-by":"crossref","unstructured":"Delpratt, O., Raman, R., Rahman, N.: Engineering succinct DOM. In: Proceedings of EDBT. ACM International Conference Proceeding Series, vol. 261, pp. 49\u201360. ACM (2008)","DOI":"10.1145\/1353343.1353354"},{"key":"331_CR10","unstructured":"Gasieniec, L., Kolpakov, R.M., Potapov, I., Sant, P.: Real-time traversal in grammar-based compressed files. In: Proceedings of DCC 2005, p. 458. IEEE Computer Society. Long version availabe at http:\/\/www.csc.liv.ac.uk\/~leszek\/papers\/dcc05.ps.gz (2005)"},{"key":"331_CR11","unstructured":"H\u00fcbschle-Schneider, L., Raman, R.: Tree compression with top trees revisited. In: Proceedings of SEA 2015. Lecture Notes in Computer Science, vol.\u00a09125, pp. 15\u201327. Springer, Berlin (2015). Long version available at arXiv:1506.04499"},{"key":"331_CR12","unstructured":"Hucke, D., Lohrey, M., Noeth, E.: Constructing small tree grammars and small circuits for formulas. In: Proceedings of FSTTCS 2014. LIPIcs, vol.\u00a029, pp. 457\u2013468. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2014)"},{"key":"331_CR13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"key":"331_CR14","unstructured":"Je\u017c, A., Lohrey, M.: Approximation of smallest linear tree grammars. In: Proceedings of STACS 2014. LIPIcs, vol.\u00a025, pp. 445\u2013457. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2014)"},{"key":"331_CR15","volume-title":"The Art of Computer Programming. Fundamental Algorithms","author":"D Knuth","year":"1968","unstructured":"Knuth, D.: The Art of Computer Programming. Fundamental Algorithms, vol. I. Addison-Wesley, Reading (1968)"},{"issue":"2","key":"331_CR16","doi-asserted-by":"crossref","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."},{"issue":"2","key":"331_CR17","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 363(2), 196\u2013210 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"331_CR18","doi-asserted-by":"crossref","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."},{"issue":"5","key":"331_CR19","doi-asserted-by":"crossref","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":"331_CR20","unstructured":"Maneth, S., Sebastian, T.: Fast and tiny structural self-indexes for XML. CoRR (2010). arXiv:1012.5696"},{"key":"331_CR21","doi-asserted-by":"crossref","unstructured":"Maneth, S., Sebastian, T.: XPath node selection over grammar-compressed trees. In: Proceedings of TTATT 2013, Electronic Proceedings in Theoretical Computer Science, vol. 134, pp. 38\u201348 (2013)","DOI":"10.4204\/EPTCS.134.5"},{"issue":"3","key":"331_CR22","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1145\/2601073","volume":"10","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), 16 (2014)","journal-title":"ACM Trans. Algorithms"},{"issue":"6","key":"331_CR23","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B Schieber","year":"1988","unstructured":"Schieber, B., Vishkin, U.: On finding lowest common ancestors: simplification and parallelization. SIAM J. Comput. 17(6), 1253\u20131262 (1988)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"331_CR24","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.jcss.2006.10.003","volume":"73","author":"T Scwentick","year":"2007","unstructured":"Scwentick, T.: Automata for XML\u2014a survey. J. Comput. Syst. Sci. 73(3), 289\u2013315 (2007)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0331-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0331-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0331-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T10:25:22Z","timestamp":1569925522000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0331-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,24]]},"references-count":24,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["331"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0331-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,24]]}}}