{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:48:44Z","timestamp":1759063724395,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,9,4]],"date-time":"2020-09-04T00:00:00Z","timestamp":1599177600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2020,9,4]]},"abstract":"<jats:p>One of the classical tasks in information extraction is to extract subparts of texts through regular expressions. In the database theory literature, this approach has been generalized and formalized as document spanners. In this model, extraction is performed by evaluating a particular kind of automata, called a sequential variable-set automaton (VA). The efficiency of this task is then measured in the context of enumeration algorithms: we first run a preprocessing phase computing a compact representation of the answers, and second we produce the results one after the other with a short time between consecutive answers, called the delay of the enumeration. Our goal is to have an algorithm that is tractable in combined complexity, i.e., in the sizes of the input document and the VA, while ensuring the best possible data complexity bounds in the input document size, i.e., a constant delay that does not depend on the document. We present such an algorithm for a variant of VAs called extended sequential VAs and give an experimental evaluation of this algorithm.<\/jats:p>","DOI":"10.1145\/3422648.3422655","type":"journal-article","created":{"date-parts":[[2020,9,4]],"date-time":"2020-09-04T10:09:28Z","timestamp":1599214168000},"page":"25-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Constant-Delay Enumeration for Nondeterministic Document Spanners"],"prefix":"10.1145","volume":"49","author":[{"given":"Antoine","family":"Amarilli","sequence":"first","affiliation":[{"name":"LTCI, T\u00e9l\u00e9com Paris, Institut Polytechnique de Paris"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Bourhis","sequence":"additional","affiliation":[{"name":"CNRS, CRIStAL, UMR 9189 &amp; Inria Lille"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Mengel","sequence":"additional","affiliation":[{"name":"CRIL, CNRS &amp; Univ Artois"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Niewerth","sequence":"additional","affiliation":[{"name":"University of Bayreuth"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,9,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/578775"},{"key":"e_1_2_1_2_1","volume-title":"ICALP","author":"Amarilli A.","year":"2017","unstructured":"A. Amarilli , P. Bourhis , L. Jachiet , and S. Mengel . A circuit-based approach to efficient enumeration . In ICALP , 2017 . A. Amarilli, P. Bourhis, L. Jachiet, and S. Mengel. A circuit-based approach to efficient enumeration. In ICALP, 2017."},{"key":"e_1_2_1_3_1","volume-title":"ICDT","author":"Amarilli A.","year":"2018","unstructured":"A. Amarilli , P. Bourhis , and S. Mengel . Enumeration on trees under relabelings . In ICDT , 2018 . A. Amarilli, P. Bourhis, and S. Mengel. Enumeration on trees under relabelings. In ICDT, 2018."},{"key":"e_1_2_1_4_1","volume-title":"ICDT","author":"Amarilli A.","year":"2019","unstructured":"A. Amarilli , P. Bourhis , S. Mengel , and M. Niewerth . Constant-delay enumeration for nondeterministic document spanners . In ICDT , 2019 . A. Amarilli, P. Bourhis, S. Mengel, and M. Niewerth. Constant-delay enumeration for nondeterministic document spanners. In ICDT, 2019."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319702"},{"key":"e_1_2_1_6_1","volume-title":"Constant-delay enumeration for nondeterministic document spanners","author":"Amarilli A.","year":"2020","unstructured":"A. Amarilli , P. Bourhis , S. Mengel , and M. Niewerth . Constant-delay enumeration for nondeterministic document spanners , 2020 . https:\/\/arxiv.org\/abs\/2003.02576. A. Amarilli, P. Bourhis, S. Mengel, and M. Niewerth. Constant-delay enumeration for nondeterministic document spanners, 2020. https:\/\/arxiv.org\/abs\/2003.02576."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_11"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699442"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196987"},{"key":"e_1_2_1_10_1","volume-title":"ICDT","author":"Freydenberger D. D.","year":"2017","unstructured":"D. D. Freydenberger . A logic for document spanners . In ICDT , 2017 . D. D. Freydenberger. A logic for document spanners. In ICDT, 2017."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9770-0"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196967"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.116"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"issue":"1","key":"e_1_2_1_15_1","doi-asserted-by":"crossref","DOI":"10.1007\/BF02127798","volume":"16","author":"Grandjean E.","year":"1996","unstructured":"E. Grandjean . Sorting, linear time and the satisfiability problem. Annals of Mathematics and Artificial Intelligence , 16 ( 1 ), 1996 . E. Grandjean. Sorting, linear time and the satisfiability problem. Annals of Mathematics and Artificial Intelligence, 16(1), 1996.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"e_1_2_1_16_1","unstructured":"IBM Research. SystemT 2018. https:\/\/researcher.watson.ibm.com\/ researcher\/view_group.php?id=1264.  IBM Research. SystemT 2018. https:\/\/researcher.watson.ibm.com\/ researcher\/view_group.php?id=1264."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528928"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603137"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196968"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209144"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196961"},{"key":"e_1_2_1_23_1","volume-title":"STACS","author":"Segoufin L.","year":"2014","unstructured":"L. Segoufin . A glimpse on constant delay enumeration (Invited talk) . In STACS , 2014 . L. Segoufin. A glimpse on constant delay enumeration (Invited talk). In STACS, 2014."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206036"},{"key":"e_1_2_1_25_1","volume-title":"The complexity of computing the permanent. Theoretical Computer Science, 8(2)","author":"Valiant L.","year":"1979","unstructured":"L. Valiant . The complexity of computing the permanent. Theoretical Computer Science, 8(2) , 1979 . L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2), 1979."},{"key":"e_1_2_1_26_1","volume-title":"CoRR","author":"Wasa K.","year":"2016","unstructured":"K. Wasa . Enumeration of enumeration algorithms . CoRR , 2016 . K. Wasa. Enumeration of enumeration algorithms. CoRR, 2016."}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3422648.3422655","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3422648.3422655","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:29Z","timestamp":1750195889000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3422648.3422655"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,4]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,9,4]]}},"alternative-id":["10.1145\/3422648.3422655"],"URL":"https:\/\/doi.org\/10.1145\/3422648.3422655","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2020,9,4]]},"assertion":[{"value":"2020-09-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}