{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:47:30Z","timestamp":1759063650866,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,25]],"date-time":"2019-06-25T00:00:00Z","timestamp":1561420800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100008952","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE40-0007"],"award-info":[{"award-number":["ANR-16-CE40-0007"]}],"id":[{"id":"10.13039\/501100008952","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["MA 4938\/4-1"],"award-info":[{"award-number":["MA 4938\/4-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,25]]},"DOI":"10.1145\/3294052.3319702","type":"proceedings-article","created":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T12:56:45Z","timestamp":1560776205000},"page":"89-103","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Enumeration on Trees with Tractable Combined Complexity and Efficient Updates"],"prefix":"10.1145","author":[{"given":"Antoine","family":"Amarilli","sequence":"first","affiliation":[{"name":"LTCI, CNRS, T\u00e9l\u00e9com ParisTech, Universit\u00e9 Paris-Saclay, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Bourhis","sequence":"additional","affiliation":[{"name":"CRIStAL, CNRS UMR 9189, Inria Lille, Lille, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Mengel","sequence":"additional","affiliation":[{"name":"CNRS, CRIL UMR 8188, Lens, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Niewerth","sequence":"additional","affiliation":[{"name":"University of Bayreuth, Bayreuth, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,25]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Stephen Alstrup Thore Husfeldt and Theis Rauhe. 1998. hrefhttp:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.71.3834&rep=rep1&type=pdfMarked ancestor problems. In FOCS.  Stephen Alstrup Thore Husfeldt and Theis Rauhe. 1998. hrefhttp:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.71.3834&rep=rep1&type=pdfMarked ancestor problems. In FOCS."},{"key":"e_1_3_2_1_2_1","unstructured":"Antoine Amarilli Pierre Bourhis Louis Jachiet and Stefan Mengel. 2017. hrefhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2017\/7462\/pdf\/LIPIcs-ICALP-2017--111.pdf A Circuit-based approach to efficient enumeration. In mboxhrefhttp:\/\/icalp17.mimuw.edu.pl\/ICALP .  Antoine Amarilli Pierre Bourhis Louis Jachiet and Stefan Mengel. 2017. hrefhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2017\/7462\/pdf\/LIPIcs-ICALP-2017--111.pdf A Circuit-based approach to efficient enumeration. In mboxhrefhttp:\/\/icalp17.mimuw.edu.pl\/ICALP ."},{"key":"e_1_3_2_1_3_1","unstructured":"Antoine Amarilli Pierre Bourhis Louis Jachiet and Stefan Mengel. 2019 a. hrefhttps:\/\/arxiv.org\/abs\/1702.05589 A Circuit-based approach to efficient enumeration . Extended version with proofs. https:\/\/arxiv.org\/abs\/1702.05589.  Antoine Amarilli Pierre Bourhis Louis Jachiet and Stefan Mengel. 2019 a. hrefhttps:\/\/arxiv.org\/abs\/1702.05589 A Circuit-based approach to efficient enumeration . Extended version with proofs. https:\/\/arxiv.org\/abs\/1702.05589."},{"key":"e_1_3_2_1_4_1","unstructured":"Antoine Amarilli Pierre Bourhis and Stefan Mengel. 2018. hrefhttps:\/\/arxiv.org\/abs\/1709.06185?context=cs.LOEnumeration on trees under relabelings. In ICDT .  Antoine Amarilli Pierre Bourhis and Stefan Mengel. 2018. hrefhttps:\/\/arxiv.org\/abs\/1709.06185?context=cs.LOEnumeration on trees under relabelings. In ICDT ."},{"key":"e_1_3_2_1_5_1","unstructured":"Antoine Amarilli Pierre Bourhis Stefan Mengel and Matthias Niewerth. 2019 b. hrefhttps:\/\/arxiv.org\/abs\/1807.09320 Constant-delay enumeration for nondeterministic document spanners. In ICDT .  Antoine Amarilli Pierre Bourhis Stefan Mengel and Matthias Niewerth. 2019 b. hrefhttps:\/\/arxiv.org\/abs\/1807.09320 Constant-delay enumeration for nondeterministic document spanners. In ICDT ."},{"key":"e_1_3_2_1_6_1","unstructured":"Antoine Amarilli Pierre Bourhis Stefan Mengel and Matthias Niewerth. 2019 c. hrefhttps:\/\/arxiv.org\/abs\/1812.09519 Enumeration on trees with tractable combined complexity and efficient updates . Extended version with proofs. https:\/\/arxiv.org\/abs\/1812.09519.  Antoine Amarilli Pierre Bourhis Stefan Mengel and Matthias Niewerth. 2019 c. hrefhttps:\/\/arxiv.org\/abs\/1812.09519 Enumeration on trees with tractable combined complexity and efficient updates . Extended version with proofs. https:\/\/arxiv.org\/abs\/1812.09519."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Antoine Amarilli Pierre Bourhis and Pierre Senellart. 2015. hrefhttps:\/\/arxiv.org\/abs\/1511.08723Provenance circuits for trees and treelike instances. In ICALP .  Antoine Amarilli Pierre Bourhis and Pierre Senellart. 2015. hrefhttps:\/\/arxiv.org\/abs\/1511.08723Provenance circuits for trees and treelike instances. In ICALP .","DOI":"10.1007\/978-3-662-47666-6_5"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_11"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2392389.2392412"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1042046.1042050"},{"key":"e_1_3_2_1_11_1","unstructured":"Christoph Berkholz Jens Keppeler and Nicole Schweikardt. 2017a. hrefhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2017\/7053\/pdf\/LIPIcs-ICDT-2017--8.pdfAnswering FO  Christoph Berkholz Jens Keppeler and Nicole Schweikardt. 2017a. hrefhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2017\/7053\/pdf\/LIPIcs-ICDT-2017--8.pdfAnswering FO"},{"key":"e_1_3_2_1_12_1","unstructured":"MOD queries under updates on bounded degree databases. In ICDT.  MOD queries under updates on bounded degree databases. In ICDT."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Christoph Berkholz Jens Keppeler and Nicole Schweikardt. 2017b. hrefhttps:\/\/arxiv.org\/abs\/1702.06370Answering conjunctive queries under updates. In PODS.  Christoph Berkholz Jens Keppeler and Nicole Schweikardt. 2017b. hrefhttps:\/\/arxiv.org\/abs\/1702.06370Answering conjunctive queries under updates. In PODS.","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_3_2_1_14_1","unstructured":"Christoph Berkholz Jens Keppeler and Nicole Schweikardt. 2018. hrefhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/8599\/ Answering UCQs under updates and in the presence of integrity constraints . In ICDT .  Christoph Berkholz Jens Keppeler and Nicole Schweikardt. 2018. hrefhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/8599\/ Answering UCQs under updates and in the presence of integrity constraints . In ICDT ."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289859"},{"volume-title":"Handbook of Automata Theory","author":"Boja'nczyk M.","key":"e_1_3_2_1_16_1","unstructured":"M. Boja'nczyk . 2010. hrefhttp:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.297.2952Algebra for trees . In Handbook of Automata Theory . European Mathematical Society Publishing . M. Boja'nczyk. 2010. hrefhttp:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.297.2952Algebra for trees. In Handbook of Automata Theory . European Mathematical Society Publishing."},{"key":"e_1_3_2_1_17_1","volume-title":"Boja' nczyk and I. Walukiewicz","author":"M.","year":"2007","unstructured":"M. Boja' nczyk and I. Walukiewicz . 2007 . hrefhttps:\/\/hal.archives-ouvertes.fr\/hal-00105796Forest algebras. In Automata and Logic: History and Perspectives. Amsterdam University Press . M. Boja' nczyk and I. Walukiewicz. 2007. hrefhttps:\/\/hal.archives-ouvertes.fr\/hal-00105796Forest algebras. In Automata and Logic: History and Perspectives. Amsterdam University Press."},{"key":"e_1_3_2_1_18_1","unstructured":"Florent Capelli and Stefan Mengel. 2019. hrefhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/10257\/Tractable QBF by knowledge compilation. In STACS.  Florent Capelli and Stefan Mengel. 2019. hrefhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/10257\/Tractable QBF by knowledge compilation. In STACS."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"J. Carme J. Niehren and M. Tommasi. 2004. hrefhttps:\/\/hal.inria.fr\/inria-00536529Querying unranked trees with stepwise tree automata. In RTA .  J. Carme J. Niehren and M. Tommasi. 2004. hrefhttps:\/\/hal.inria.fr\/inria-00536529Querying unranked trees with stepwise tree automata. In RTA .","DOI":"10.1007\/978-3-540-25979-4_8"},{"key":"e_1_3_2_1_20_1","unstructured":"Nofar Carmeli and Markus Kr\u00f6ll. 2018. hrefhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/8598\/ Enumeration complexity of conjunctive queries with functional dependencies. In ICDT .  Nofar Carmeli and Markus Kr\u00f6ll. 2018. hrefhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/8598\/ Enumeration complexity of conjunctive queries with functional dependencies. In ICDT ."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.11.11-34"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276920.1276923"},{"key":"e_1_3_2_1_23_1","volume-title":"JACM","volume":"62","author":"Fagin Ronald","year":"2015","unstructured":"Ronald Fagin , Benny Kimelfeld , Frederick Reiss , and Stijn Vansummeren . 2015 . hrefhttps:\/\/pdfs.semanticscholar.org\/8df0\/ad1c6aa0df93e58071b8afe3371a16a3182f.pdfDocument spanners: A formal approach to information extraction . JACM , Vol. 62 , 2 (2015). Ronald Fagin, Benny Kimelfeld, Frederick Reiss, and Stijn Vansummeren. 2015. hrefhttps:\/\/pdfs.semanticscholar.org\/8df0\/ad1c6aa0df93e58071b8afe3371a16a3182f.pdfDocument spanners: A formal approach to information extraction . JACM, Vol. 62, 2 (2015)."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Fernando Florenzano Cristian Riveros Martin Ugarte Stijn Vansummeren and Domagoj Vrgoc. 2018. hrefhttps:\/\/arxiv.org\/abs\/1803.05277Constant delay algorithms for regular document spanners. In PODS .  Fernando Florenzano Cristian Riveros Martin Ugarte Stijn Vansummeren and Domagoj Vrgoc. 2018. hrefhttps:\/\/arxiv.org\/abs\/1803.05277Constant delay algorithms for regular document spanners. In PODS .","DOI":"10.1145\/3196959.3196987"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Francc ois Le Gall. 2014. hrefhttps:\/\/arxiv.org\/abs\/1401.7714Powers of tensors and fast matrix multiplication. In ISSAC.  Francc ois Le Gall. 2014. hrefhttps:\/\/arxiv.org\/abs\/1401.7714Powers of tensors and fast matrix multiplication. In ISSAC.","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528928"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Katja Losemann and Wim Martens. 2014. hrefhttp:\/\/www.theoinf.uni-bayreuth.de\/download\/lics14-preprint.pdfMSO queries on trees: enumerating answers under updates. In CSL-LICS .  Katja Losemann and Wim Martens. 2014. hrefhttp:\/\/www.theoinf.uni-bayreuth.de\/download\/lics14-preprint.pdfMSO queries on trees: enumerating answers under updates. In CSL-LICS .","DOI":"10.1145\/2603088.2603137"},{"key":"e_1_3_2_1_28_1","volume-title":"JCSS","volume":"73","author":"Martens W.","year":"2007","unstructured":"W. Martens and J. Niehren . 2007. hrefhttps:\/\/hal.inria.fr\/inria-00088406v2On the Minimization of XML Schemas and tree automata for unranked trees . JCSS , Vol. 73 , 4 ( 2007 ). W. Martens and J. Niehren. 2007. hrefhttps:\/\/hal.inria.fr\/inria-00088406v2On the Minimization of XML Schemas and tree automata for unranked trees . JCSS, Vol. 73, 4 (2007)."},{"key":"e_1_3_2_1_29_1","unstructured":"Wim Martens and Tina Trautner. 2018. hrefhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/8594\/ Evaluation and enumeration problems for regular path queries. In ICDT .  Wim Martens and Tina Trautner. 2018. hrefhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/8594\/ Evaluation and enumeration problems for regular path queries. In ICDT ."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Albert R Meyer. 1975. Weak monadic second order theory of succesor is not elementary-recursive. In Logic Colloquium .  Albert R Meyer. 1975. Weak monadic second order theory of succesor is not elementary-recursive. In Logic Colloquium .","DOI":"10.1007\/BFb0064872"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209144"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196961"},{"key":"e_1_3_2_1_33_1","volume-title":"SIGMOD Record","volume":"45","author":"Olteanu Dan","year":"2016","unstructured":"Dan Olteanu and Maximilian Schleich . 2016 . hrefhttp:\/\/www.cs.ox.ac.uk\/dan.olteanu\/papers\/os-sigrec16.pdfFactorized databases . SIGMOD Record , Vol. 45 , 2 (2016). Dan Olteanu and Maximilian Schleich. 2016. hrefhttp:\/\/www.cs.ox.ac.uk\/dan.olteanu\/papers\/os-sigrec16.pdfFactorized databases . SIGMOD Record, Vol. 45, 2 (2016)."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447256"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1619995.1620079"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196971"},{"key":"e_1_3_2_1_37_1","unstructured":"Luc Segoufin. 2014. hrefhttps:\/\/hal.inria.fr\/hal-01070893\/documentA glimpse on constant delay enumeration (Invited talk). In STACS.  Luc Segoufin. 2014. hrefhttps:\/\/hal.inria.fr\/hal-01070893\/documentA glimpse on constant delay enumeration (Invited talk). In STACS."},{"key":"e_1_3_2_1_38_1","volume-title":"Wright","author":"Thatcher James W.","year":"1968","unstructured":"James W. Thatcher and Jesse B . Wright . 1968 . Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Systems Theory , Vol. 2 , 1 (1968). James W. Thatcher and Jesse B. Wright. 1968. Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Systems Theory, Vol. 2, 1 (1968)."}],"event":{"name":"SIGMOD\/PODS '19: International Conference on Management of Data","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"location":"Amsterdam Netherlands","acronym":"SIGMOD\/PODS '19"},"container-title":["Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3294052.3319702","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3294052.3319702","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:28Z","timestamp":1750204408000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3294052.3319702"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,25]]},"references-count":38,"alternative-id":["10.1145\/3294052.3319702","10.1145\/3294052"],"URL":"https:\/\/doi.org\/10.1145\/3294052.3319702","relation":{},"subject":[],"published":{"date-parts":[[2019,6,25]]},"assertion":[{"value":"2019-06-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}