{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:21:46Z","timestamp":1755998506818,"version":"3.44.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["522576760"],"award-info":[{"award-number":["522576760"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>We present a linear preprocessing and output-linear delay enumeration algorithm for MSO-queries over trees that are compressed in the well-established grammar-based framework. Time bounds are measured with respect to the size of the compressed representation of the tree. Our result extends previous work on the enumeration of MSO-queries over uncompressed trees and on the enumeration of document spanners over compressed text documents.<\/jats:p>","DOI":"10.1145\/3651141","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-17","source":"Crossref","is-referenced-by-count":1,"title":["Enumeration for MSO-Queries on Compressed Trees"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4680-7198","authenticated-orcid":false,"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[{"name":"Universit\u00e4t Siegen, Siegen, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5137-1504","authenticated-orcid":false,"given":"Markus L.","family":"Schmid","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319702"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_11"},{"key":"e_1_2_2_3_1","unstructured":"Guillaume Bagan. 2009. Algorithmes et complexit\u00e9 des probl\u00e8 mes d'\u00e9 num\u00e9 ration pour l'\u00e9 valuation de requ\u00ea tes logiques. (Algorithms and complexity of enumeration problems for the evaluation of logical queries). Ph. D. Dissertation. University of Caen Normandy France. https:\/\/tel.archives-ouvertes.fr\/tel-00424232"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.3038147"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.IC.2014.12.012"},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]. (Texts in Logic and Games","volume":"132","author":"Igor Walukiewicz Miko\u0142aj Boja'n","year":"2008","unstructured":"Miko\u0142aj Boja'n czyk and Igor Walukiewicz. 2008. Forest algebras. In Proceedings of Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]. (Texts in Logic and Games, Vol. 2). Amsterdam University Press, 107--132."},{"key":"e_1_2_2_7_1","volume-title":"Proceedings of the 12th International Conference on Enterprise Information Systems, ICEIS 2010","volume":"1","author":"Stefan B\u00f6","year":"2010","unstructured":"Stefan B\u00f6 ttcher, Rita Hartel, and Christoph Krislin. 2010. CluX - Clustering XML Sub-trees. In Proceedings of the 12th International Conference on Enterprise Information Systems, ICEIS 2010, Volume 1, DISI. SciTePress, 142--150."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014--9544-x"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012722442-8\/50021-5"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2008.01.004"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-25979-4_8"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-020--10013-w"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850116"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.DAM.2008.08.021"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2018.16"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2003.1210058"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.110"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.12.007"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3457389"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-019-09942-y"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2005.78"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2016.35"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--20086--6_2"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528928"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","unstructured":"Sarah Kleest-Mei\u00dfner Jonas Marasus and Matthias Niewerth. 2023. MSO Queries on Trees: Enumerating Answers under Updates Using Forest Algebras. https:\/\/doi.org\/10.48550\/ARXIV.2208.04180 arxiv: 2208.04180 [cs.LO]","DOI":"10.48550\/ARXIV.2208.04180"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1515\/GCC-2012-0016"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21500-6_3"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.06.006"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2017.18"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-017-0331--3"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.03.003"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2023.7"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209144"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304--3975(02)00777--6"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458325"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524158"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651141","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:39:13Z","timestamp":1755898753000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651141"],"URL":"https:\/\/doi.org\/10.1145\/3651141","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}