{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T19:43:44Z","timestamp":1779911024759,"version":"3.53.1"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,2,8]],"date-time":"2020-02-08T00:00:00Z","timestamp":1581120000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"crossref","award":["11160383 and 11150653"],"award-info":[{"award-number":["11160383 and 11150653"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004744","name":"Innoviris","doi-asserted-by":"publisher","award":["SPICES"],"award-info":[{"award-number":["SPICES"]}],"id":[{"id":"10.13039\/501100004744","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2020,3,31]]},"abstract":"<jats:p>\n            Regular expressions and automata models with capture variables are core tools in rule-based information extraction. These formalisms, also called\n            <jats:italic>regular document spanners<\/jats:italic>\n            , use regular languages to locate the data that a user wants to extract from a text document and then store this data into variables. Since document spanners can easily generate large outputs, it is important to have efficient evaluation algorithms that can generate the extracted data in a quick succession, and with relatively little precomputation time. Toward this goal, we present a practical evaluation algorithm that allows output-linear delay enumeration of a spanner\u2019s result after a precomputation phase that is linear in the document. Although the algorithm assumes that the spanner is specified in a syntactic variant of variable-set automata, we also study how it can be applied when the spanner is specified by general variable-set automata, regex formulas, or spanner algebras. Finally, we study the related problem of counting the number of outputs of a document spanner and provide a fine-grained analysis of the classes of document spanners that support efficient enumeration of their results.\n          <\/jats:p>","DOI":"10.1145\/3351451","type":"journal-article","created":{"date-parts":[[2020,2,8]],"date-time":"2020-02-08T09:03:56Z","timestamp":1581152636000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Efficient Enumeration Algorithms for Regular Document Spanners"],"prefix":"10.1145","volume":"45","author":[{"given":"Fernando","family":"Florenzano","sequence":"first","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile and IMFD Chile, Macul, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cristian","family":"Riveros","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile and IMFD Chile, Macul, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mart\u00edn","family":"Ugarte","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles and IMFD Chile, Macul, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stijn","family":"Vansummeren","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles, Brussels, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Domagoj","family":"Vrgo\u010d","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile and IMFD Chile, Macul, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,2,8]]},"reference":[{"key":"e_1_2_1_1_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_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90252-O"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 22nd International Conference on Database Theory (ICDT\u201919)","author":"Amarilli Antoine","year":"2019","unstructured":"Antoine Amarilli , Pierre Bourhis , Stefan Mengel , and Matthias Niewerth . 2019 . Constant-delay enumeration for nondeterministic document spanners . In Proceedings of the 22nd International Conference on Database Theory (ICDT\u201919) . 22:1--22:19. Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth. 2019. Constant-delay enumeration for nondeterministic document spanners. In Proceedings of the 22nd International Conference on Database Theory (ICDT\u201919). 22:1--22:19."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2983200.2983204"},{"key":"e_1_2_1_5_1","series-title":"Lecture Notes in Computer Science","volume-title":"Computer Science Logic","author":"Bagan Guillaume","unstructured":"Guillaume Bagan . 2006. MSO queries on tree decomposable structures are computable with linear delay . In Computer Science Logic . Lecture Notes in Computer Science , Vol. 4207 . Springer , 167--181. Guillaume Bagan. 2006. MSO queries on tree decomposable structures are computable with linear delay. In Computer Science Logic. Lecture Notes in Computer Science, Vol. 4207. Springer, 167--181."},{"key":"e_1_2_1_6_1","series-title":"Lecture Notes in Computer Science","volume-title":"Computer Science Logic","author":"Bagan Guillaume","unstructured":"Guillaume Bagan , Arnaud Durand , and Etienne Grandjean . 2007. On acyclic conjunctive queries and constant delay enumeration . In Computer Science Logic . Lecture Notes in Computer Science , Vol. 4646 . Springer , 208--222. Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007. On acyclic conjunctive queries and constant delay enumeration. In Computer Science Logic. Lecture Notes in Computer Science, Vol. 4646. Springer, 208--222."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL\u201910)","author":"Chiticariu Laura","year":"2010","unstructured":"Laura Chiticariu , Rajasekar Krishnamurthy , Yunyao Li , Sriram Raghavan , Frederick Reiss , and Shivakumar Vaithyanathan . 2010 . SystemT: An algebraic approach to declarative information extraction . In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL\u201910) . 128--137. Laura Chiticariu, Rajasekar Krishnamurthy, Yunyao Li, Sriram Raghavan, Frederick Reiss, and Shivakumar Vaithyanathan. 2010. SystemT: An algebraic approach to declarative information extraction. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL\u201910). 128--137."},{"key":"e_1_2_1_8_1","volume-title":"Reiss","author":"Chiticariu Laura","year":"2013","unstructured":"Laura Chiticariu , Yunyao Li , and Frederick R . Reiss . 2013 . Rule-based information extraction is dead! Long live rule-based information extraction systems! In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing (EMNLP\u2019 13). 827--832. Laura Chiticariu, Yunyao Li, and Frederick R. Reiss. 2013. Rule-based information extraction is dead! Long live rule-based information extraction systems! In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing (EMNLP\u201913). 827--832."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.021"},{"key":"e_1_2_1_10_1","volume-title":"Retrieved","author":"Cox Russ","year":"2007","unstructured":"Russ Cox . 2007 . Regular Expression Matching Can Be Simple and Fast (But Is Slow in Java, Perl, PHP, Python, Ruby, \u2026) . Retrieved December 27, 2019 from http:\/\/swtch.com\/&sim;rsc\/regexp\/regexp1.html. Russ Cox. 2007. Regular Expression Matching Can Be Simple and Fast (But Is Slow in Java, Perl, PHP, Python, Ruby, \u2026). Retrieved December 27, 2019 from http:\/\/swtch.com\/&sim;rsc\/regexp\/regexp1.html."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594540"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699442"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2877202"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196987"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 20th International Conference on Database Theory (ICDT\u201917)","author":"Freydenberger Dominik D.","year":"2017","unstructured":"Dominik D. Freydenberger . 2017 . A logic for document spanners . In Proceedings of the 20th International Conference on Database Theory (ICDT\u201917) . Article 13, 18 pages. Dominik D. Freydenberger. 2017. A logic for document spanners. In Proceedings of the 20th International Conference on Database Theory (ICDT\u201917). Article 13, 18 pages."},{"key":"e_1_2_1_16_1","volume-title":"LIPIcs-Leibniz International Proceedings in Informatics","volume":"48","author":"Dominik","year":"2016","unstructured":"Dominik D, Freydenberger, and Mario Holldack . 2016 . Document spanners: From expressive power to decision problems . In LIPIcs-Leibniz International Proceedings in Informatics , Vol. 48 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Dominik D, Freydenberger, and Mario Holldack. 2016. Document spanners: From expressive power to decision problems. In LIPIcs-Leibniz International Proceedings in Informatics, Vol. 48. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196967"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528928"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594563"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1519103.1519105"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196968"},{"key":"e_1_2_1_23_1","unstructured":"Andrea Morciano. 2017. Engineering a Runtime System for AQL. Master\u2019s Thesis. Universit\u00e9 Libre de Bruxelles and Politecnico di Milano.  Andrea Morciano. 2017. Engineering a Runtime System for AQL. Master\u2019s Thesis. Universit\u00e9 Libre de Bruxelles and Politecnico di Milano."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448498"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914)","author":"Segoufin Luc","year":"2014","unstructured":"Luc Segoufin . 2014 . A glimpse on constant delay enumeration . In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914) . 13--27. Luc Segoufin. 2014. A glimpse on constant delay enumeration. In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914). 13--27."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783888.2783894"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 33rd International Conference on Very Large Data Bases. 1033--1044","author":"Shen Warren","year":"2007","unstructured":"Warren Shen , AnHai Doan , Jeffrey F. Naughton , and Raghu Ramakrishnan . 2007 . Declarative information extraction using datalog with embedded extraction predicates . In Proceedings of the 33rd International Conference on Very Large Data Bases. 1033--1044 . Warren Shen, AnHai Doan, Jeffrey F. Naughton, and Raghu Ramakrishnan. 2007. Declarative information extraction using datalog with embedded extraction predicates. In Proceedings of the 33rd International Conference on Very Large Data Bases. 1033--1044."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133651.1133652"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3351451","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3351451","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:51Z","timestamp":1750206351000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3351451"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,8]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3,31]]}},"alternative-id":["10.1145\/3351451"],"URL":"https:\/\/doi.org\/10.1145\/3351451","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,8]]},"assertion":[{"value":"2018-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}