{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T18:49:49Z","timestamp":1782672589771,"version":"3.54.5"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2020,11,13]]},"abstract":"<jats:p>\n            We propose a solution to the problem of efficient matching regular expressions (regexes) with bounded repetition, such as (ab){1,100}, using deterministic automata. For this, we introduce novel\n            <jats:italic>counting-set automata (CsAs)<\/jats:italic>\n            , automata with registers that can hold sets of bounded integers and can be manipulated by a limited portfolio of constant-time operations. We present an algorithm that compiles a large sub-class of regexes to deterministic CsAs. This includes (1) a novel Antimirov-style translation of regexes with counting to\n            <jats:italic>counting automata (CAs)<\/jats:italic>\n            , nondeterministic automata with bounded counters, and (2) our main technical contribution, a determinization of CAs that outputs CsAs. The main advantage of this workflow is that\n            <jats:italic>the size of the produced CsAs does not depend on the repetition bounds used in the regex<\/jats:italic>\n            (while the size of the DFA is exponential to them). Our experimental results confirm that deterministic CsAs produced from practical regexes with repetition are indeed vastly smaller than the corresponding DFAs. More importantly, our prototype matcher based on CsA simulation handles practical regexes with repetition regardless of sizes of counter bounds. It easily copes with regexes with repetition where state-of-the-art matchers struggle.\n          <\/jats:p>","DOI":"10.1145\/3428286","type":"journal-article","created":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T23:36:06Z","timestamp":1606260966000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Regex matching with counting-set automata"],"prefix":"10.1145","volume":"4","author":[{"given":"Lenka","family":"Turo\u0148ov\u00e1","sequence":"first","affiliation":[{"name":"Brno University of Technology, Czechia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6957-1651","authenticated-orcid":false,"given":"Luk\u00e1\u0161","family":"Hol\u00edk","sequence":"additional","affiliation":[{"name":"Brno University of Technology, Czechia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3038-5875","authenticated-orcid":false,"given":"Ond\u0159ej","family":"Leng\u00e1l","sequence":"additional","affiliation":[{"name":"Brno University of Technology, Czechia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7596-4734","authenticated-orcid":false,"given":"Olli","family":"Saarikivi","sequence":"additional","affiliation":[{"name":"Microsoft, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Margus","family":"Veanes","sequence":"additional","affiliation":[{"name":"Microsoft, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2746-8792","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Vojnar","sequence":"additional","affiliation":[{"name":"Brno University of Technology, Czechia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85361-9_9"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11821069_10"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00182-4"},{"key":"e_1_2_2_4_1","unstructured":"Adam Baldwin. 2016. Regular Expression Denial of Service a ecting Express.js. http:\/\/web.archive.org\/web\/20170116160113\/ https:\/\/medium.com\/node-security\/ regular-expression-denial-of-service-a ecting-express-js-9c397c164c43  Adam Baldwin. 2016. Regular Expression Denial of Service a ecting Express.js. http:\/\/web.archive.org\/web\/20170116160113\/ https:\/\/medium.com\/node-security\/ regular-expression-denial-of-service-a ecting-express-js-9c397c164c43"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-008-0064-3"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90088-5"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00104-2"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806434"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2695"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21254-3_13"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48194-X_15"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.001"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/157485.164585"},{"key":"e_1_2_2_16_1","unstructured":"Wikipedia contributors. 2019. Regular expression-Wikipedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Regular_expression&%20oldid= 852858998  Wikipedia contributors. 2019. Regular expression-Wikipedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Regular_expression&%20oldid= 852858998"},{"key":"e_1_2_2_17_1","unstructured":"Russ Cox. 2010. Regular Expression Matching in the Wild. https:\/\/swtch.com\/~rsc\/regexp\/regexp3.html.  Russ Cox. 2010. Regular Expression Matching in the Wild. https:\/\/swtch.com\/~rsc\/regexp\/regexp3.html."},{"key":"e_1_2_2_18_1","unstructured":"Loris D'Antoni and Margus Veanes. 2020. Automata Modulo Theories. Commun. ACM ( 2020 ).  Loris D'Antoni and Margus Veanes. 2020. Automata Modulo Theories. Commun. ACM ( 2020 )."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3342509"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236024.3236027"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3338909"},{"key":"e_1_2_2_22_1","unstructured":"Stack Exchange. 2016. Outage Postmortem. http:\/\/stackstatus.net\/post\/147710624694\/outage-postmortem-july-20-2016  Stack Exchange. 2016. Outage Postmortem. http:\/\/stackstatus.net\/post\/147710624694\/outage-postmortem-july-20-2016"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863543.1863594"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/100814196"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_19"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"e_1_2_2_27_1","unstructured":"Google. [n.d.]. RE2. https:\/\/github.com\/google\/re2.  Google. [n.d.]. RE2. https:\/\/github.com\/google\/re2."},{"key":"e_1_2_2_28_1","volume-title":"Details of the Cloud are outage on","author":"Graham-Cumming John","year":"2019","unstructured":"John Graham-Cumming . 2019. Details of the Cloud are outage on July 2, 2019 . https:\/\/blog.cloud are. com\/details-of-thecloud are-outage-on-july-2-2019\/ John Graham-Cumming. 2019. Details of the Cloud are outage on July 2, 2019. https:\/\/blog.cloud are. com\/details-of-thecloud are-outage-on-july-2-2019\/"},{"key":"e_1_2_2_29_1","unstructured":"Mike Haertel. [n.d.]. why GNU grep is fast. https:\/\/lists.freebsd.org\/pipermail\/freebsd-current\/2010-August\/019310.html.  Mike Haertel. [n.d.]. why GNU grep is fast. https:\/\/lists.freebsd.org\/pipermail\/freebsd-current\/2010-August\/019310.html."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03466-4_15"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28332-1_27"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00090-7"},{"key":"e_1_2_2_33_1","first-page":"163","volume-title":"Proceedings of the Eighth Symposium on Programming Languages and Software Tools, SPLST'03","author":"Kilpel\u00e4inen Pekka","year":"2003","unstructured":"Pekka Kilpel\u00e4inen and Rauno Tuhkanen . 2003 . Regular Expressions with Numerical Occurrence Indicators-preliminary results . In Proceedings of the Eighth Symposium on Programming Languages and Software Tools, SPLST'03 , Kuopio, Finland , June 17-18, 2003. University of Kuopio, Department of Computer Science, 163 - 173 . Pekka Kilpel\u00e4inen and Rauno Tuhkanen. 2003. Regular Expressions with Numerical Occurrence Indicators-preliminary results. In Proceedings of the Eighth Symposium on Programming Languages and Software Tools, SPLST'03, Kuopio, Finland, June 17-18, 2003. University of Kuopio, Department of Computer Science, 163-173."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.12.003"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.016"},{"key":"e_1_2_2_36_1","unstructured":"Microsoft. 2020.. https:\/\/docs.microsoft.com\/en-us\/dotnet\/api\/system.text.regularexpressions.regex.match  Microsoft. 2020.. https:\/\/docs.microsoft.com\/en-us\/dotnet\/api\/system.text.regularexpressions.regex.match"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796808007090"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17462-0_24"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028752"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/230514.571645"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2008.14"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89862-7_15"},{"key":"e_1_2_2_43_1","volume-title":"Software Solutions in C","author":"Spencer Henry","year":"1846","unstructured":"Henry Spencer . 1994. Software Solutions in C . Academic Press Professional, Inc. , San Diego, CA, USA , Chapter A Regularexpression Matcher, 35-71. http:\/\/dl.acm.org\/citation.cfm?id= 156626. 1846 89 Henry Spencer. 1994. Software Solutions in C. Academic Press Professional, Inc., San Diego, CA, USA, Chapter A Regularexpression Matcher, 35-71. http:\/\/dl.acm.org\/citation.cfm?id= 156626. 184689"},{"key":"e_1_2_2_44_1","unstructured":"Michael Sperberg-McQueen. [n.d.]. Notes on nite state automata with counters. https:\/\/www.w3.org\/XML\/ 2004 \/05\/msmcfa.html Accessed: 2018-08-08.  Michael Sperberg-McQueen. [n.d.]. Notes on nite state automata with counters. https:\/\/www.w3.org\/XML\/ 2004 \/05\/msmcfa.html Accessed: 2018-08-08."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2010.15"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15512-3_4"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428286","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428286","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:58Z","timestamp":1750197778000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":47,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2020,11,13]]}},"alternative-id":["10.1145\/3428286"],"URL":"https:\/\/doi.org\/10.1145\/3428286","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,13]]},"assertion":[{"value":"2020-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}