{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T08:39:48Z","timestamp":1780994388374,"version":"3.54.1"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T00:00:00Z","timestamp":1704153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2008096"],"award-info":[{"award-number":["2008096"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,1,2]]},"abstract":"<jats:p>\n            Regular expressions have been extended with lookaround assertions, which are subdivided into lookahead and lookbehind assertions. These constructs are used to refine when a match for a pattern occurs in the input text based on the surrounding context. Current implementation techniques for lookaround involve backtracking search, which can give rise to running time that is super-linear in the length of input text. In this paper, we first consider a formal mathematical semantics for lookaround, which complements the commonly used operational understanding of lookaround in terms of a backtracking implementation. Our formal semantics allows us to establish several equational properties for simplifying lookaround assertions. Additionally, we propose a new algorithm for matching regular expressions with lookaround that has time complexity\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi>O<\/mml:mi>\n                <mml:mfenced close=\")\" open=\"(\">\n                  <mml:mrow>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>\u22c5<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:mfenced>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            , where\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi>m<\/mml:mi>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            is the size of the regular expression and\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi>n<\/mml:mi>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            is the length of the input text. The algorithm works by evaluating lookaround assertions in a bottom-up manner. Our algorithm makes use of a new notion of nondeterministic finite automata (NFAs), which we call oracle-NFAs. These automata are augmented with epsilon-transitions that are guarded by oracle queries that provide the truth values of lookaround assertions at every position in the text. We provide an implementation of our algorithm that incorporates three performance optimizations for reducing the work performed and memory used. We present an experimental comparison against PCRE and Java\u2019s regex library, which are state-of-the-art regex engines that support lookaround assertions. Our experimental results show that, in contrast to PCRE and Java, our implementation does not suffer from super-linear running time and is several times faster.\n          <\/jats:p>","DOI":"10.1145\/3632934","type":"journal-article","created":{"date-parts":[[2024,1,5]],"date-time":"2024-01-05T20:48:51Z","timestamp":1704487731000},"page":"2761-2791","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Efficient Matching of Regular Expressions with Lookaround Assertions"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1209-7738","authenticated-orcid":false,"given":"Konstantinos","family":"Mamouras","sequence":"first","affiliation":[{"name":"Rice University, Houston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-0462-8080","authenticated-orcid":false,"given":"Agnishom","family":"Chattopadhyay","sequence":"additional","affiliation":[{"name":"Rice University, Houston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,1,5]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00182-4"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET2011.2181411"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-75632-5_5"},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/944705.944711"},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.4204\/eptc.151.7s"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.3897\/jucs.66330"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.2307\/2272532"},{"issue":"3","key":"e_1_3_1_11_1","doi-asserted-by":"crossref","first-page":"195","DOI":"10.3233\/FUN-2001-45303","article-title":"From Mirkin\u2019s Prebases to Antimirov\u2019s Word Partial Derivatives","volume":"45","author":"Champarnaud Jean-Marc","year":"2001","unstructured":"Jean-Marc Champarnaud and Djelloul Ziadi. 2001. From Mirkin\u2019s Prebases to Antimirov\u2019s Word Partial Derivatives. Fundamenta Informaticae 45, 3 (2001), 195\u2013205. https:\/\/ip.ios.semcs.net\/articles\/fundamenta-informaticae\/fi45-3-03","journal-title":"Fundamenta Informaticae"},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-60508-7_21"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSCD.2022.15"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25379-9_11"},{"key":"e_1_3_1_15_1","unstructured":"Russ Cox. 2010. Regular Expression Matching in the Wild. https:\/\/swtch.com\/rsc\/regexp\/regexp3.html. [Online; accessed November 14 2023]."},{"key":"e_1_3_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/9783-319-03545-16"},{"key":"e_1_3_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/9783-319-11164-3_19"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3497775.3503694"},{"key":"e_1_3_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03545-1_7"},{"key":"e_1_3_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/964001.964011"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/9783-540-27836-8_53"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837647"},{"key":"e_1_3_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39274-0_7"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10882-7_14"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603095"},{"key":"e_1_3_1_26_1","unstructured":"grep 2023. GREP - Global Regular Expression Print. https:\/\/www.gnu.org\/software\/grep\/."},{"key":"e_1_3_1_27_1","unstructured":"Hyperscan 2023. Intel\u2019s Hyperscan: A high-performance multiple regex matching library. https:\/\/github.com\/intel\/hyperscan."},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/364175.364185"},{"key":"e_1_3_1_29_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400882618-002"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2103776.2103784"},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523456"},{"key":"e_1_3_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1037"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/256167.256195"},{"key":"e_1_3_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_24"},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3586044"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78127-1_26"},{"key":"e_1_3_1_37_1","volume-title":"Extensions of Kleene Algebra for Program Verification","author":"Mamouras Konstantinos","year":"2015","unstructured":"Konstantinos Mamouras. 2015. Extensions of Kleene Algebra for Program Verification. Ph. D. Dissertation. Cornell University, Ithaca, NY. http:\/\/hdl.handle.net\/1813\/40960"},{"key":"e_1_3_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54458-7_6"},{"key":"e_1_3_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-72016-2_18"},{"key":"e_1_3_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-88494-9_8"},{"key":"e_1_3_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-023-00719-w"},{"key":"e_1_3_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.3013053"},{"key":"e_1_3_1_43_1","first-page":"110","article-title":"An Algorithm for Constructing a Base in a Language of Regular Expression","volume":"5","author":"Mirkin B. G.","year":"1966","unstructured":"B. G. Mirkin. 1966. An Algorithm for Constructing a Base in a Language of Regular Expression. Engineering Cybernetics 5 (1966), 110\u2013116.","journal-title":"Engineering Cybernetics"},{"key":"e_1_3_1_44_1","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjjip.27.422"},{"key":"e_1_3_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-68195-1_16"},{"key":"e_1_3_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33314-9_7"},{"key":"e_1_3_1_47_1","doi-asserted-by":"publisher","DOI":"10.11309\/jssst.29.1_147"},{"key":"e_1_3_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591262"},{"key":"e_1_3_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21254-3_32"},{"key":"e_1_3_1_50_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"e_1_3_1_51_1","unstructured":"RE2 2023. RE2: Google\u2019s regular expression library. https:\/\/github.com\/google\/re2."},{"key":"e_1_3_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2015.2430313"},{"key":"e_1_3_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2011.11.003"},{"key":"e_1_3_1_54_1","unstructured":"Snort 2023. Snort Intrusion Detection System. https:\/\/www.snort.org\/."},{"key":"e_1_3_1_55_1","unstructured":"Suricata 2023. Suricata Threat Detection Engine. https:\/\/suricata.io\/."},{"key":"e_1_3_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2004.01.029"},{"key":"e_1_3_1_57_1","unstructured":"The PCRE2 Developers. 2023. Perl-compatible Regular Expressions (revised API: PCRE2). https:\/\/pcre2project.github.io\/pcre2\/doc\/html\/index.html."},{"key":"e_1_3_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_3_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.simpa.2020.100027"},{"key":"e_1_3_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-66246823-4_27"},{"key":"e_1_3_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1185347.1185360"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632934","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632934","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632934","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:03:57Z","timestamp":1751659437000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632934"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,2]]},"references-count":60,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2024,1,2]]}},"alternative-id":["10.1145\/3632934"],"URL":"https:\/\/doi.org\/10.1145\/3632934","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,2]]},"assertion":[{"value":"2024-01-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}