{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T13:12:45Z","timestamp":1778764365579,"version":"3.51.4"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["466789228"],"award-info":[{"award-number":["466789228"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["562495345"],"award-info":[{"award-number":["562495345"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["2023\\\/51\\\/B\\\/ST6\\\/01505"],"award-info":[{"award-number":["2023\\\/51\\\/B\\\/ST6\\\/01505"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,12]]},"abstract":"Enumerating all matches of a regular expression with capture variables (variable regex, for short) to a document is a fundamental task in textual information extraction, e.g., in connection to document spanners. State-of-the-art results [Amarilli et al., ACM TODS 2021] show how the matches of a variable regex, representable by a sequential variable-set automaton, to a document can be enumerated with delay constant in the size of the document and polynomial in the size of the query, after a preprocessing requiring time linear in the size of the document and polynomial in the size of the query. However, the polynomial dependency on the size of the query in both the delay and the preprocessing is actually quite high: at least quadratic.<\/jats:p>\n \n We consider here the matching problem for regular expressions with capture variables which can be represented as regular patterns:\n w<\/jats:italic>\n 0<\/jats:sub>\n x<\/jats:italic>\n 0<\/jats:sub>\n w<\/jats:italic>\n 1<\/jats:sub>\n x\n 1<\/jats:sub>\n #8230;s w\n k<\/jats:sub>\n x\n k<\/jats:sub>\n w\n k<\/jats:sub>\n +1, where, for\n i<\/jats:italic>\n \u2208 {0, \u2026\n k<\/jats:italic>\n +1}, w\n i<\/jats:sub>\n is a string of terminal letters and, for\n i<\/jats:italic>\n in {0,\u2026,\n k<\/jats:italic>\n }, x\n i<\/jats:sub>\n is a variable. This problem naturally lies in the intersection of information extraction and stringology, as it can also be seen as computing all the ways in which\n k<\/jats:italic>\n +1 given strings\n w<\/jats:italic>\n 0<\/jats:sub>\n ,\u2026,w\n k<\/jats:sub>\n +1 occur, in this order and without overlaps, in a given text\n T<\/jats:italic>\n . We provide an optimal enumeration algorithm for this problem. After a preprocessing requiring linear time in the size of the document\n T<\/jats:italic>\n and the size of the query pattern \u03b1, we can enumerate all matches with worst-case constant delay (in combined complexity, i.e., both in the document- and the query-size).\n <\/jats:p>","DOI":"10.1145\/3801908","type":"journal-article","created":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T12:50:22Z","timestamp":1778763022000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Enumeration of Regular Pattern Matches"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6993-5440","authenticated-orcid":false,"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[{"name":"Institute of Computer Science, University of Wroc\u0142aw, Wroclaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6094-3324","authenticated-orcid":false,"given":"Florin","family":"Manea","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of G\u00f6ttingen, G\u00f6ttingen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-5413-043X","authenticated-orcid":false,"given":"Paul","family":"Sarnighausen-Cahn","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of G\u00f6ttingen, G\u00f6ttingen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7509-8135","authenticated-orcid":false,"given":"Stefan","family":"Siemer","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of G\u00f6ttingen, G\u00f6ttingen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,14]]},"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."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3436487"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2023.8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90041-0"},{"key":"e_1_2_1_5_1","first-page":"457","article-title":"Which Regular Expression Patterns Are Hard to Match?","author":"Backurs Arturs","year":"2016","unstructured":"Arturs Backurs and Piotr Indyk. 2016. Which Regular Expression Patterns Are Hard to Match?. In FOCS. IEEE Computer Society, 457-466.","journal-title":"FOCS. IEEE Computer Society"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_11"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/10719839_9"},{"key":"e_1_2_1_8_1","volume-title":"TheoretiCS","volume":"3","author":"Bringmann Karl","year":"2024","unstructured":"Karl Bringmann, Allan Gr\u00f8nlund, Marvin K\u00fcnnemann, and Kasper Green Larsen. 2024. The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. TheoretiCS, Vol. 3 (2024)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217026"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644251"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.DAM.2008.08.021"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699442"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646102"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2018.04.035"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3369935"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.IC.2015.03.006"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-015-9635-3"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196987"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100217"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80064-9"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196967"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2017.33"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023), Santiago de Chile, Chile, May 22-26, 2023 (CEUR Workshop Proceedings","volume":"3","author":"Frochaux Andr\u00e9","year":"2023","unstructured":"Andr\u00e9 Frochaux and Sarah Kleest-Mei\u00dfner. 2023. Puzzling over Subsequence-Query Extensions: Disjunction and Generalised Gaps. In Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023), Santiago de Chile, Chile, May 22-26, 2023 (CEUR Workshop Proceedings, Vol. 3409). CEUR-WS.org. https:\/\/ceur-ws.org\/Vol-3409\/paper3.pdf"},{"key":"e_1_2_1_25_1","unstructured":"Leslie Ann Goldberg. 1991. Efficient algorithms for listing combinatorial structures. Ph.D. Dissertation. University of Edinburgh UK. https:\/\/hdl.handle.net\/1842\/10917"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90065-8"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528928"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1283920.1283929"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-28796-2_1"},{"key":"e_1_2_1_31_1","volume-title":"Combinatorial Gray codes-an updated survey. CoRR","author":"M\u00fctze Torsten","year":"2022","unstructured":"Torsten M\u00fctze. 2022. Combinatorial Gray codes-an updated survey. CoRR, Vol. abs\/2202.01280 (2022). arXiv:2202.01280 https:\/\/arxiv.org\/abs\/2202.01280"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31265-6_2"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196961"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-11980-9_1910.1007\/3-540-11980-9_19"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3801908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T12:52:26Z","timestamp":1778763146000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3801908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,12]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5,12]]}},"alternative-id":["10.1145\/3801908"],"URL":"https:\/\/doi.org\/10.1145\/3801908","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,12]]}}}