{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:45:29Z","timestamp":1759063529183,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,12]],"date-time":"2022-06-12T00:00:00Z","timestamp":1654992000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","award":["ICN17_002"],"award-info":[{"award-number":["ICN17_002"]}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["431183758"],"award-info":[{"award-number":["431183758"]}],"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":[[2022,6,12]]},"DOI":"10.1145\/3517804.3526232","type":"proceedings-article","created":{"date-parts":[[2022,6,13]],"date-time":"2022-06-13T13:29:54Z","timestamp":1655126994000},"page":"291-300","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Efficient Enumeration for Annotated Grammars"],"prefix":"10.1145","author":[{"given":"Antoine","family":"Amarilli","sequence":"first","affiliation":[{"name":"LTCI, T\u00e9l\u00e9com Paris, Institut Polytechnique de Paris, Paris, France"}]},{"given":"Louis","family":"Jachiet","sequence":"additional","affiliation":[{"name":"LTCI, T\u00e9l\u00e9com Paris, Institut Polytechnique de Paris, Paris, France"}]},{"given":"Mart\u00edn","family":"Mu\u00f1oz","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile, Santiago, Chile"}]},{"given":"Cristian","family":"Riveros","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile, Santiago, Chile"}]}],"member":"320","published-online":{"date-parts":[[2022,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1061771"},{"key":"e_1_3_2_1_2_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"1974","unstructured":"Alfred V. Aho , John E. Hopcroft , and Jeffrey D . Ullman . 1974 . The design and analysis of computer algorithms. Addison-Wesley . Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. 1974. The design and analysis of computer algorithms. Addison-Wesley."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Rajeev Alur and Parthasarathy Madhusudan. 2004. Visibly pushdown languages. In STOC.  Rajeev Alur and Parthasarathy Madhusudan. 2004. Visibly pushdown languages. In STOC.","DOI":"10.1145\/1007352.1007390"},{"key":"e_1_3_2_1_4_1","unstructured":"Antoine Amarilli Pierre Bourhis Louis Jachiet and Stefan Mengel. 2017. A circuit-based approach to efficient enumeration. In ICALP.  Antoine Amarilli Pierre Bourhis Louis Jachiet and Stefan Mengel. 2017. A circuit-based approach to efficient enumeration. In ICALP."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Antoine Amarilli Pierre Bourhis Stefan Mengel and Matthias Niewerth. 2019. Constant-delay enumeration for nondeterministic document spanners. In ICDT.  Antoine Amarilli Pierre Bourhis Stefan Mengel and Matthias Niewerth. 2019. Constant-delay enumeration for nondeterministic document spanners. In ICDT.","DOI":"10.1145\/3422648.3422655"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Antoine Amarilli Pierre Bourhis Stefan Mengel and Matthias Niewerth. 2019. Enumeration on trees with tractable combined complexity and efficient updates. In PODS.  Antoine Amarilli Pierre Bourhis Stefan Mengel and Matthias Niewerth. 2019. Enumeration on trees with tractable combined complexity and efficient updates. In PODS.","DOI":"10.1145\/3294052.3319702"},{"key":"e_1_3_2_1_7_1","volume-title":"Constant-delay enumeration for nondeterministic document spanners. TODS","author":"Amarilli Antoine","year":"2020","unstructured":"Antoine Amarilli , Pierre Bourhis , Stefan Mengel , and Matthias Niewerth . 2020. Constant-delay enumeration for nondeterministic document spanners. TODS ( 2020 ). Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth. 2020. Constant-delay enumeration for nondeterministic document spanners. TODS (2020)."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Antoine Amarilli Louis Jachiet Mart\u00edn Mu\u00f1oz and Cristian Riveros. 2022. Efficient enumeration for annotated grammars. https:\/\/arxiv.org\/abs\/2201.00549 Complete version with proofs.  Antoine Amarilli Louis Jachiet Mart\u00edn Mu\u00f1oz and Cristian Riveros. 2022. Efficient enumeration for annotated grammars. https:\/\/arxiv.org\/abs\/2201.00549 Complete version with proofs.","DOI":"10.1145\/3517804.3526232"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Guillaume Bagan. 2006. MSO queries on tree decomposable structures are computable with linear delay. In CSL.  Guillaume Bagan. 2006. MSO queries on tree decomposable structures are computable with linear delay. In CSL.","DOI":"10.1007\/11874683_11"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Christoph Berkholz Jens Keppeler and Nicole Schweikardt. 2017. Answering conjunctive queries under updates. In PODS.  Christoph Berkholz Jens Keppeler and Nicole Schweikardt. 2017. Answering conjunctive queries under updates. In PODS.","DOI":"10.1145\/3034786.3034789"},{"volume-title":"Transductions and context-free languages","author":"Berstel Jean","key":"e_1_3_2_1_12_1","unstructured":"Jean Berstel . 2013. Transductions and context-free languages . Springer-Verlag . Jean Berstel. 2013. Transductions and context-free languages. Springer-Verlag."},{"key":"e_1_3_2_1_13_1","volume-title":"Linear delay enumeration and monadic second-order logic. Discret. Appl. Math. 157, 12","author":"Courcelle Bruno","year":"2009","unstructured":"Bruno Courcelle . 2009. Linear delay enumeration and monadic second-order logic. Discret. Appl. Math. 157, 12 ( 2009 ). Bruno Courcelle. 2009. Linear delay enumeration and monadic second-order logic. Discret. Appl. Math. 157, 12 (2009)."},{"key":"e_1_3_2_1_14_1","volume-title":"Daniel Dominic Sleator, and Robert Endre Tarjan","author":"Driscoll James R","year":"1986","unstructured":"James R Driscoll , Neil Sarnak , Daniel Dominic Sleator, and Robert Endre Tarjan . 1986 . Making data structures persistent. In STOC. James R Driscoll, Neil Sarnak, Daniel Dominic Sleator, and Robert Endre Tarjan. 1986. Making data structures persistent. In STOC."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276920.1276923"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699442"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Fernando Florenzano Cristian Riveros Mart\u00edn Ugarte Stijn Vansummeren and Domagoj Vrgoc. 2018. Constant delay algorithms for regular document spanners. In PODS.  Fernando Florenzano Cristian Riveros Mart\u00edn Ugarte Stijn Vansummeren and Domagoj Vrgoc. 2018. Constant delay algorithms for regular document spanners. In PODS.","DOI":"10.1145\/3196959.3196987"},{"key":"e_1_3_2_1_18_1","volume-title":"Efficient enumeration algorithms for regular document spanners. TODS 45, 1","author":"Florenzano Fernando","year":"2020","unstructured":"Fernando Florenzano , Cristian Riveros , Mart\u00edn Ugarte , Stijn Vansummeren , and Domagoj Vrgoc . 2020. Efficient enumeration algorithms for regular document spanners. TODS 45, 1 ( 2020 ). Fernando Florenzano, Cristian Riveros, Mart\u00edn Ugarte, Stijn Vansummeren, and Domagoj Vrgoc. 2020. Efficient enumeration algorithms for regular document spanners. TODS 45, 1 (2020)."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Olaf Hartig and Jorge P\u00e9rez. 2018. Semantics and complexity of GraphQL. In TheWebConf.  Olaf Hartig and Jorge P\u00e9rez. 2018. Semantics and complexity of GraphQL. In TheWebConf.","DOI":"10.1145\/3178876.3186014"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Muhammad Idris Mart\u00edn Ugarte and Stijn Vansummeren. 2017. The dynamic Yannakakis algorithm: Compact and efficient query processing under updates. In SIGMOD.  Muhammad Idris Mart\u00edn Ugarte and Stijn Vansummeren. 2017. The dynamic Yannakakis algorithm: Compact and efficient query processing under updates. In SIGMOD.","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Ahmet Kara Milos Nikolic Dan Olteanu and Haozhe Zhang. 2020. Trade-offs in static and dynamic evaluation of hierarchical queries. In PODS.  Ahmet Kara Milos Nikolic Dan Olteanu and Haozhe Zhang. 2020. Trade-offs in static and dynamic evaluation of hierarchical queries. In PODS.","DOI":"10.1145\/3375395.3387646"},{"key":"e_1_3_2_1_22_1","unstructured":"Markus Kr\u00f6ll Reinhard Pichler and Sebastian Skritek. 2016. On the complexity of enumerating the answers to well-designed pattern trees. In ICDT.  Markus Kr\u00f6ll Reinhard Pichler and Sebastian Skritek. 2016. On the complexity of enumerating the answers to well-designed pattern trees. In ICDT."},{"key":"e_1_3_2_1_23_1","volume-title":"To CNF or not to CNF? An efficient yet presentable version of the CYK algorithm. Informatica Didactica 8","author":"Lange Martin","year":"2009","unstructured":"Martin Lange and Hans Lei\u00df . 2009. To CNF or not to CNF? An efficient yet presentable version of the CYK algorithm. Informatica Didactica 8 , 2009 (2009). Martin Lange and Hans Lei\u00df. 2009. To CNF or not to CNF? An efficient yet presentable version of the CYK algorithm. Informatica Didactica 8, 2009 (2009)."},{"key":"e_1_3_2_1_24_1","volume-title":"A direct proof of the inherent ambiguity of a simple context-free language. JACM 16, 2","author":"Maurer Herman A","year":"1969","unstructured":"Herman A Maurer . 1969. A direct proof of the inherent ambiguity of a simple context-free language. JACM 16, 2 ( 1969 ). Herman A Maurer. 1969. A direct proof of the inherent ambiguity of a simple context-free language. JACM 16, 2 (1969)."},{"key":"e_1_3_2_1_25_1","unstructured":"Martin Mu\u00f1oz and Cristian Riveros. 2022. Streaming Enumeration on Nested Documents. In ICDT.  Martin Mu\u00f1oz and Cristian Riveros. 2022. Streaming Enumeration on Nested Documents. In ICDT."},{"key":"e_1_3_2_1_26_1","unstructured":"Dirk Nowotka and Jiri Srba. 2007. Height-deterministic pushdown automata. In MFCS.  Dirk Nowotka and Jiri Srba. 2007. Height-deterministic pushdown automata. In MFCS."},{"key":"e_1_3_2_1_28_1","unstructured":"Liat Peterfreund. 2021. Grammars for document spanners. In ICDT.  Liat Peterfreund. 2021. Grammars for document spanners. In ICDT."},{"key":"e_1_3_2_1_29_1","volume-title":"Ronald Fagin, and Benny Kimelfeld.","author":"Peterfreund Liat","year":"2019","unstructured":"Liat Peterfreund , Balder ten Cate , Ronald Fagin, and Benny Kimelfeld. 2019 . Recursive programs for document spanners. In ICDT. Liat Peterfreund, Balder ten Cate, Ronald Fagin, and Benny Kimelfeld. 2019. Recursive programs for document spanners. In ICDT."},{"key":"e_1_3_2_1_30_1","unstructured":"Sylvain Schmitz. 2012. Can all unambiguous grammars be parsed in linear time? Theoretical Computer Science Stack Exchange. https:\/\/cstheory.stackexchange.com\/q\/10504 Version: 2012-03-02.  Sylvain Schmitz. 2012. Can all unambiguous grammars be parsed in linear time? Theoretical Computer Science Stack Exchange. https:\/\/cstheory.stackexchange.com\/q\/10504 Version: 2012-03-02."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Luc Segoufin. 2013. Enumerating with constant delay the answers to a query. In ICDT.  Luc Segoufin. 2013. Enumerating with constant delay the answers to a query. In ICDT.","DOI":"10.1145\/2448496.2448498"}],"event":{"name":"SIGMOD\/PODS '22: International Conference on Management of Data","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"location":"Philadelphia PA USA","acronym":"SIGMOD\/PODS '22"},"container-title":["Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517804.3526232","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3517804.3526232","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:05Z","timestamp":1750182545000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3517804.3526232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,12]]},"references-count":30,"alternative-id":["10.1145\/3517804.3526232","10.1145\/3517804"],"URL":"https:\/\/doi.org\/10.1145\/3517804.3526232","relation":{},"subject":[],"published":{"date-parts":[[2022,6,12]]},"assertion":[{"value":"2022-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}