{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T18:24:56Z","timestamp":1777141496849,"version":"3.51.4"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,5,25]],"date-time":"2014-05-25T00:00:00Z","timestamp":1400976000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2015,11]]},"DOI":"10.1007\/s00224-014-9544-x","type":"journal-article","created":{"date-parts":[[2014,5,24]],"date-time":"2014-05-24T02:17:23Z","timestamp":1400897843000},"page":"1322-1371","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["XML Compression via Directed Acyclic Graphs"],"prefix":"10.1007","volume":"57","author":[{"given":"Mireille","family":"Bousquet-M\u00e9lou","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":"Eric","family":"Noeth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,5,25]]},"reference":[{"key":"9544_CR1","doi-asserted-by":"crossref","unstructured":"Arion, A., Bonifati, A., Manolescu, I., Pugliese, A.: XQueC: A query-conscious compressed XML database. ACM Trans. Intern. Tech. 7(2) (2007)","DOI":"10.1145\/1239971.1239974"},{"issue":"11","key":"9544_CR2","first-page":"1232","volume":"5","author":"N Bakibayev","year":"2012","unstructured":"Bakibayev, N., Olteanu, D., Zavodny, J.: Fdb: A query engine for factorised relational databases. PVLDB 5(11), 1232\u20131243 (2012)","journal-title":"PVLDB"},{"key":"9544_CR3","doi-asserted-by":"crossref","unstructured":"Bille, P., Landau, G. M., Raman, R., Sadakane, K., Satti, S. R., Weimann, O.: Random Access to Grammar-Compressed Strings. In: SODA, pp. 373\u2013389 (2011)","DOI":"10.1137\/1.9781611973082.30"},{"key":"9544_CR4","doi-asserted-by":"crossref","unstructured":"Buneman, P., Grohe, M., Koch, C.: Path Queries on Compressed XML. In: VLDB, pp. 141\u2013152 (2003)","DOI":"10.1016\/B978-012722442-8\/50021-5"},{"issue":"4-5","key":"9544_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-5), 456\u2013474 (2008)","journal-title":"Inf. Syst."},{"key":"9544_CR6","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/B978-1-4832-3187-7.50007-6","volume-title":"Graph theory and computing","author":"NG de Bruijn","year":"1972","unstructured":"de Bruijn, N.G., Knuth, D.E., Rice, S.O.: Graph theory and computing, pp 15\u201322. Academic Press, New York (1972)"},{"issue":"1","key":"9544_CR7","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0012-365X(80)90168-5","volume":"31","author":"N Dershowitz","year":"1980","unstructured":"Dershowitz, N., Zaks, S.: Enumerations of ordered trees. Discret. Math. 31(1), 9\u201328 (1980)","journal-title":"Discret. Math."},{"issue":"4","key":"9544_CR8","doi-asserted-by":"crossref","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. J. ACM 27(4), 758\u2013771 (1980)","journal-title":"J. ACM"},{"issue":"8","key":"9544_CR9","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/368892.368907","volume":"1","author":"AP Ershov","year":"1958","unstructured":"Ershov, A. P.: On programming of arithmetic operations. Commun. ACM 1(8), 3\u20139 (1958)","journal-title":"Commun. ACM"},{"issue":"2","key":"9544_CR10","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0022-0000(82)90004-6","volume":"25","author":"P Flajolet","year":"1982","unstructured":"Flajolet, P., Odlyzko, A.: The average height of binary trees and other simple trees. J. Comput. Syst. Sci. 25(2), 171\u2013213 (1982)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9544_CR11","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0403019","volume":"3","author":"P Flajolet","year":"1990","unstructured":"Flajolet, P., Odlyzko, A.: Singularity analysis of generating functions. SIAM J. Discret. Math. 3(2), 216\u2013240 (1990)","journal-title":"SIAM J. Discret. Math."},{"key":"9544_CR12","doi-asserted-by":"crossref","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511801655"},{"key":"9544_CR13","doi-asserted-by":"crossref","unstructured":"Flajolet, P., Sipala, P., Steyaert, J.-M.: Analytic Variations on the Common Subexpression Problem. In: ICALP, pp. 220\u2013234 (1990)","DOI":"10.1007\/BFb0032034"},{"key":"9544_CR14","unstructured":"Knuth, D.E.: The Art of Computer Programming, Vol. I: Fundamental Algorithms. Addison-Wesley (1968)"},{"key":"9544_CR15","doi-asserted-by":"crossref","unstructured":"Koch, C.: Efficient processing of expressive node-selecting queries on XML data in secondary storage: A tree automata-based approach. In: VLDB, pp. 249\u2013260 (2003)","DOI":"10.1016\/B978-012722442-8\/50030-6"},{"key":"9544_CR16","doi-asserted-by":"crossref","unstructured":"Larsson, N. J., Moffat, A.: Offline Dictionary-Based Compression. In: DCC, pp. 296\u2013305 (1999)","DOI":"10.1109\/DCC.1999.755679"},{"key":"9544_CR17","doi-asserted-by":"crossref","unstructured":"Liefke, H., XMILL, D. Suciu.: An Efficient Compressor for XML Data. In: SIGMOD Conference, pp. 153\u2013164 (2000)","DOI":"10.1145\/335191.335405"},{"key":"9544_CR18","first-page":"241","volume":"4","author":"M Lohrey","year":"2013","unstructured":"Lohrey, M.: Algorithmics on SLP-compressed strings: A survey. Groups Complexity Cryptol. 4, 241\u2013299 (2013)","journal-title":"Groups Complexity Cryptol."},{"issue":"2","key":"9544_CR19","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":"9544_CR20","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."},{"key":"9544_CR21","doi-asserted-by":"crossref","unstructured":"Lohrey, M., Maneth, S., Noeth, E.: XML Compression via Dags. In: ICDT, pp. 69\u201380 (2013)","DOI":"10.1145\/2448496.2448506"},{"issue":"5","key":"9544_CR22","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":"9544_CR23","unstructured":"Maneth, S., Sebastian, T.: Fast and tiny structural self-indexes for XML. CoRR arXiv: abs\/1012.5696 (2010)"},{"issue":"2","key":"9544_CR24","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1002\/rsa.10111","volume":"24","author":"J-F Marckert","year":"2004","unstructured":"Marckert, J.-F.: The rotation correspondence is asymptotically a dilatation. Random Struct. Algorithm. 24(2), 118\u2013132 (2004)","journal-title":"Random Struct. Algorithm."},{"key":"9544_CR25","doi-asserted-by":"crossref","unstructured":"Meinel, C., Theobald, T.: Algorithms and Data Structures in VLSI Design: OBDD - Foundations and Applications. Springer (1998)","DOI":"10.1007\/978-3-642-58940-9"},{"issue":"3","key":"9544_CR26","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/601858.601869","volume":"31","author":"F Neven","year":"2002","unstructured":"Neven, F.: Automata theory for XML researchers. SIGMOD Rec. 31(3), 39\u201346 (2002)","journal-title":"SIGMOD Rec."},{"key":"9544_CR27","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1613\/jair.374","volume":"7","author":"CG Nevill-Manning","year":"1997","unstructured":"Nevill-Manning, C. G., Witten, I.H.: Identifying hierarchical strcture in sequences: A linear-time algorithm. J. Artif. Intell. Res. (JAIR) 7, 67\u201382 (1997)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"9544_CR28","doi-asserted-by":"crossref","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: ESA, pp. 460\u2013470 (1994)","DOI":"10.1007\/BFb0049431"},{"issue":"3","key":"9544_CR29","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.jcss.2006.10.003","volume":"73","author":"T Schwentick","year":"2007","unstructured":"Schwentick, T.: Automata for XML - a survey. J. Comput. Syst. Sci. 73(3), 289\u2013315 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"9544_CR30","doi-asserted-by":"crossref","unstructured":"Suciu, D.: Typechecking for semistructured data. In: DBPL, pp. 1\u201320 (2001)","DOI":"10.1007\/3-540-46093-4_1"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9544-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9544-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9544-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,10]],"date-time":"2019-08-10T19:12:49Z","timestamp":1565464369000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9544-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,25]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["9544"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9544-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,25]]}}}