{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T20:12:30Z","timestamp":1784837550466,"version":"3.55.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T00:00:00Z","timestamp":1736208000000},"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":[[2025,1,7]]},"abstract":"<jats:p>\n                    We present a tool and theory\n                    <jats:bold>RE<\/jats:bold>\n                    # for regular expression matching that is built on symbolic derivatives, does not use backtracking, and, in addition to the classical operators, also supports complement, intersection and restricted lookarounds. We develop the theory formally and show that the main matching algorithm has input-linear complexity both in theory as well as experimentally. We apply thorough evaluation on popular benchmarks that show that\n                    <jats:bold>RE<\/jats:bold>\n                    # is\n                    <jats:italic toggle=\"yes\">over 71% faster than the next fastest regex engine in Rust<\/jats:italic>\n                    on the baseline, and\n                    <jats:italic toggle=\"yes\">outperforms all state-of-the-art engines on extensions of the benchmarks often by several orders of magnitude.<\/jats:italic>\n                  <\/jats:p>","DOI":"10.1145\/3704837","type":"journal-article","created":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T05:48:42Z","timestamp":1736401722000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["RE#: High Performance Derivative-Based Regex Matching with Intersection, Complement, and Restricted Lookarounds"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1267-2712","authenticated-orcid":false,"given":"Ian Erik","family":"Varatalu","sequence":"first","affiliation":[{"name":"Tallinn University of Technology, Tallinn, Estonia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-8427-7977","authenticated-orcid":false,"given":"Margus","family":"Veanes","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4591-0425","authenticated-orcid":false,"given":"Juhan","family":"Ernits","sequence":"additional","affiliation":[{"name":"Tallinn University of Technology, Tallinn, Estonia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,1,9]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00182-4"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-43144-4_5"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99524-9_24"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656431"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.01.010"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.3897\/jucs.66330"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00982-2_24"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21254-3_13"},{"key":"e_1_3_2_11_1","first-page":"31","article-title":"Solving String Constraints with Regex-Dependent Functions through Transducers with Priorities and Variables","volume":"6","author":"Chen Taolue","year":"2022","unstructured":"Taolue Chen, Alejandro Flores-Lamas, Matthew Hague, Zhilei Han, Denghang Hu, Shuanglong Kan, Anthony W. Lin, Philipp R\u00fcmmer, and Zhilin Wu. 2022. Solving String Constraints with Regex-Dependent Functions through Transducers with Priorities and Variables. Proc.ACMProgram.Lang. 6, POPL, Article 45 (jan 2022), 31 pages. https:\/\/doi.org\/10.1145\/3498707 10.1145\/3498707","journal-title":"Proc.ACMProgram.Lang."},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1587\/transinf.2022EDP7098"},{"key":"e_1_3_2_13_1","unstructured":"Russ Cox. 2010. Regular Expression Matching in the Wild. https:\/\/swtch.com\/~rsc\/regexp\/regexp3.html"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3419404"},{"key":"e_1_3_2_15_1","first-page":"1256","volume-title":"Proceedings of ESEC\/FSE'19 (Tallinn, Estonia) (ESEC\/FSE 2019)","author":"C James","year":"2019","unstructured":"James C. Davis. 2019. Rethinking Regex Engines to Address ReDoS. In Proceedings of ESEC\/FSE'19 (Tallinn, Estonia) (ESEC\/FSE 2019). ACM, New York, NY, USA, 1256 \u2013 1258. https:\/\/doi.org\/10.1145\/3338906.3342509 10.1145\/3338906.3342509"},{"key":"e_1_3_2_16_1","first-page":"246","volume-title":"Proceedings of ESEC\/FSE'18 (Lake Buena Vista, FL, USA) (ESEC\/FSE 2018)","author":"C James","year":"2018","unstructured":"James C. Davis, Christy A. Coghlan, Francisco Servant, and Dongyoon Lee. 2018. The Impact of Regular Expression Denial of Service (ReDoS) in Practice: An Empirical Study at the Ecosystem Scale. In Proceedings of ESEC\/FSE'18 (Lake Buena Vista, FL, USA) (ESEC\/FSE 2018). ACM, New York, NY, USA, 246 \u2013 256. https:\/\/doi.org\/10.1145\/3236024.3236027 10.1145\/3236024.3236027"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1932681.1863594"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_53"},{"key":"e_1_3_2_20_1","unstructured":"Andrew Gallant. 2024. BurntSushi: rebar. https:\/\/github.com\/BurntSushi\/rebar"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071368.2071372"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3586044"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"e_1_3_2_24_1","unstructured":"GNU. 2023. grep. https:\/\/www.gnu.org\/software\/grep\/."},{"key":"e_1_3_2_25_1","unstructured":"Google. 2024. RE2. https:\/\/github.com\/google\/re2."},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837647"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30829-1_19"},{"key":"e_1_3_2_28_1","unstructured":"Alec Koumjian. 2024. akoumjian: datefinder. https:\/\/github.com\/akoumjian\/datefinder"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/256167.256195"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SPIRE.2000.878194"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24246-0_9"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314645"},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632934"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1960.5221603"},{"key":"e_1_3_2_35_1","unstructured":"Microsoft. 2021a. CredScan. https:\/\/secdevtools.azurewebsites.net\/helpcredscan.html."},{"key":"e_1_3_2_36_1","unstructured":"Microsoft. 2021b. Regular Expression Language - Quick Reference. https:\/\/docs.microsoft.com\/en-us\/dotnet\/standard\/base-types\/regular-expression-language-quick-reference."},{"key":"e_1_3_2_37_1","unstructured":"Microsoft. 2022. .NET Regular Expressions. https:\/\/github.com\/dotnet\/runtime\/tree\/main\/src\/libraries\/System.Text.RegularExpressions."},{"key":"e_1_3_2_38_1","first-page":"422","article-title":"Derivatives of Regular Expressions with Lookahead","volume":"27","author":"Miyazaki Takayuki","year":"2019","unstructured":"Takayuki Miyazaki and Yasuhiko Minamide. 2019. Derivatives of Regular Expressions with Lookahead. J. Inf. Process. 27 (2019), 422 \u2013 430. https:\/\/doi.org\/10.2197\/ipsjjip.27.422 10.2197\/ipsjjip.27.422","journal-title":"J. Inf. Process."},{"key":"e_1_3_2_39_1","first-page":"147","article-title":"Translation of Regular Expression with Lookahead into Finite State Automaton","volume":"1","author":"Morihata Akimasa","year":"2012","unstructured":"Akimasa Morihata. 2012. Translation of Regular Expression with Lookahead into Finite State Automaton. Computer Software 29, 1 (2012), 147 \u2013 158. https:\/\/doi.org\/10.11309\/jssst.29.1_147 10.11309\/jssst.29.1_147","journal-title":"Computer Software"},{"key":"e_1_3_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591262"},{"key":"e_1_3_2_41_1","unstructured":"OISF. 2024. Suricata. https:\/\/suricata.io\/"},{"key":"e_1_3_2_42_1","unstructured":"OWASP. 2024. Regular expression Denial of Service - ReDoS. https:\/\/owasp.org\/www-community\/attacks\/Regular_expression_Denial_of_Service_-_ReDoS"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796808007090"},{"key":"e_1_3_2_44_1","first-page":"357","article-title":"Symbolic Algorithms for Language Equivalence and Kleene Algebra with Tests","volume":"1","author":"Pous Damien","year":"2015","unstructured":"Damien Pous. 2015. Symbolic Algorithms for Language Equivalence and Kleene Algebra with Tests. ACM SIGPLAN Notices - POPL'15 50, 1 (2015), 357 \u2013 368. https:\/\/doi.org\/10.1145\/2775051.2677007 10.1145\/2775051.2677007","journal-title":"ACM SIGPLAN Notices - POPL'15"},{"key":"e_1_3_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3472456.3473512"},{"key":"e_1_3_2_46_1","unstructured":"Rust. 2024. The Rust Programming Language: regex. https:\/\/github.com\/rust-lang\/regex"},{"key":"e_1_3_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17462-0_24"},{"key":"e_1_3_2_48_1","unstructured":"SMT-LIB. 2021. The Satisfiability Modulo Theories Library. http:\/\/smtlib.cs.uiowa.edu\/"},{"key":"e_1_3_2_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/156626.184689"},{"key":"e_1_3_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454066"},{"key":"e_1_3_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370776.2370788"},{"key":"e_1_3_2_52_1","unstructured":"Chengsong Tan and Christian Urban. 2023. POSIX Lexing with Bitcoded Derivatives. In 14th International Conference on Interactive Theorem Proving (Schloss Dagstuhl Germany) (LIPICS 26) A. Naumowicz and R. Thiemann (Eds.). Dagstuhl Publishing Dagstuhl 26:1-26:18. https:\/\/doi.org\/10.4230\/LIPIcs.ITP.2023.27 10.4230\/LIPIcs.ITP.2023.27"},{"key":"e_1_3_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_3_2_54_1","unstructured":"Stephen Toub. 2024. Performance Improvements in .NET 9. Microsoft .NET Blog. https:\/\/devblogs.microsoft.com\/dotnet\/performance-improvements-in-net-9\/"},{"key":"e_1_3_2_55_1","first-page":"4165","volume-title":"31st USENIX Security Symposium (USENIX Security 22)","author":"Turo\u0148ov\u00e1 Lenka","year":"2022","unstructured":"Lenka Turo\u0148ov\u00e1 , Luk\u00e1s Hol\u00edk, Ivan Homoliak, Ondrej Leng\u00e1l, Margus Veanes, and Tom\u00e1s Vojnar. 2022. Counting in Regexes Considered Harmful: Exposing ReDoS Vulnerability of Nonbacktracking Matchers. In 31st USENIX Security Symposium (USENIX Security 22). USENIX Association, Boston, MA, 4165 \u2013 4182. https:\/\/www.usenix.org\/conference\/usenixsecurity22\/presentation\/turonova"},{"key":"e_1_3_2_56_1","first-page":"30","article-title":"Regex Matching with Counting-Set Automata","volume":"4","author":"Turo Lenka","year":"2020","unstructured":"Lenka Turo\u00f1ov\u00e1, Luk\u00e1s Hol\u00edk, Ondrej Leng\u00e1l, Olli Saarikivi, Margus Veanes, and Tom\u00e1s Vojnar. 2020. Regex Matching with Counting-Set Automata. Proceedings of the ACM on Programming Languages 4, OOPSLA, Article 218 (Nov. 2020), 30 pages. https:\/\/doi.org\/10.1145\/3428286 10.1145\/3428286","journal-title":"Proceedings of the ACM on Programming Languages"},{"issue":"2023","key":"e_1_3_2_57_1","first-page":"1","article-title":"POSIX Lexing with Derivatives of Regular Expressions","volume":"67","author":"Urban Christian","year":"2023","unstructured":"Christian Urban. 2023. POSIX Lexing with Derivatives of Regular Expressions. Journal of Automated Reasoning 67 (July 2023), 1 \u2013 24. https:\/\/doi.org\/10.1007\/s10817-023-09667-1 10.1007\/s10817-023-09667-1","journal-title":"Journal of Automated Reasoning"},{"key":"e_1_3_2_58_1","unstructured":"Ian Erik Varatalu. .2024a. Artifact for this paper. https:\/\/doi.org\/10.5281\/zenodo.13937348 10.5281\/zenodo.13937348"},{"key":"e_1_3_2_59_1","unstructured":"Ian Erik Varatalu. 2024b. RE# Interactive. https:\/\/ieviev.github.io\/resharp-webapp\/"},{"key":"e_1_3_2_60_1","unstructured":"Ian Erik Varatalu. 2024c. Resharp. https:\/\/www.nuget.org\/packages\/Resharp"},{"key":"e_1_3_2_61_1","article-title":"Derivative Based Extended Regular Expression Matching Supporting Intersection, Complement and Lookarounds","author":"Varatalu Ian Erik","year":"2023","unstructured":"Ian Erik Varatalu, Margus Veanes, and Juhan Ernits. 2023. Derivative Based Extended Regular Expression Matching Supporting Intersection, Complement and Lookarounds. In arXiv. https:\/\/doi.org\/10.48550\/arXiv.2309.14401 10.48550\/arXiv.2309.14401","journal-title":"arXiv"},{"key":"e_1_3_2_62_1","first-page":"631","volume-title":"16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)","author":"Wang Xiang","year":"2019","unstructured":"Xiang Wang, Yang Hong, Harry Chang, KyoungSoo Park, Geoff Langdale, Jiayu Hu, and Heqing Zhu. 2019. Hyperscan: A Fast Multi-pattern Regex Matcher for Modern CPUs. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19). USENIX Association, Boston, MA, 631 \u2013 648. https:\/\/www.usenix.org\/conference\/nsdi19\/presentation\/wang-xiang"},{"key":"e_1_3_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3636501.3636959"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3704837","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3704837","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T10:18:52Z","timestamp":1770200332000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3704837"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,7]]},"references-count":62,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2025,1,7]]}},"alternative-id":["10.1145\/3704837"],"URL":"https:\/\/doi.org\/10.1145\/3704837","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,7]]},"assertion":[{"value":"2024-07-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}