Lune

POPL2025Top-tier venue

RE#: High Performance Derivative-Based Regex Matching with Intersection, Complement, and Restricted Lookarounds

Ian Erik Varatalu, Margus Veanes, Juhan P. Ernits

Abstract

We present a tool and theory RE # 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 RE # is over 71% faster than the next fastest regex engine in Rust on the baseline, and outperforms all state-of-the-art engines on extensions of the benchmarks often by several orders of magnitude.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

5 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Towards Efficient Matching of Regexes with Backreferences using Register Set Automata cites Regex matching with counting-set automata
  • Membership Testing for Semantic Regular Expressions cites Regular Expression Matching using Bit Vector Automata
  • Regex Decision Procedures in Extended RE# cites Solving string constraints with Regex-dependent functions through transducers with priorities and variables
  • Regex Decision Procedures in Extended RE# cites Symbolic Boolean derivatives for efficiently solving extended regular expression constraints
  • Regex Decision Procedures in Extended RE# cites Derivative Based Nonbacktracking Real-World Regex Matching with Backtracking Semantics
  • Regular Expression Matching using Bit Vector Automata cites Regex matching with counting-set automata
  • Formal Verification for JavaScript Regular Expressions: A Proven Mechanized Semantics and Its Applications cites Solving string constraints with Regex-dependent functions through transducers with priorities and variables
  • Formal Verification for JavaScript Regular Expressions: A Proven Mechanized Semantics and Its Applications cites Derivative Based Nonbacktracking Real-World Regex Matching with Backtracking Semantics
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers5

  1. Regex Decision Procedures in Extended RE#Ian Erik Varatalu, Margus Veanes, Ekaterina Zhuchko, Juhan P. ErnitsCAV 2025 · 3 citations
  2. Towards Efficient Matching of Regexes with Backreferences using Register Set AutomataVojtech Havlena, Lukás Holík, Ondrej Lengál, Jan Vasák et al.PLDI 2026
  3. Membership Testing for Semantic Regular ExpressionsYifei Huang, Matin Amini, Alexis Le Glaunec, Konstantinos Mamouras et al.PLDI 2025
  4. Formally Verified Linear-Time Invertible LexingSamuel Chassot, Viktor KuncakCAV 2026
  5. Formal Verification for JavaScript Regular Expressions: A Proven Mechanized Semantics and Its ApplicationsAurèle Barrière, Victor Deng, Clément Pit-ClaudelPOPL 2026

Builds on8

  1. Solving string constraints with Regex-dependent functions through transducers with priorities and variablesTaolue Chen, Alejandro Flores-Lamas, Matthew Hague, Zhilei Han et al.POPL 2022 · 39 citations
  2. Symbolic Boolean derivatives for efficiently solving extended regular expression constraintsCaleb Stanford, Margus Veanes, Nikolaj S. BjørnerPLDI 2021 · 38 citations
  3. Regex matching with counting-set automataLenka Turonová, Lukás Holík, Ondrej Lengál, Olli Saarikivi et al.OOPSLA 2020 · 22 citations
  4. Regular Expression Matching using Bit Vector AutomataAlexis Le Glaunec, Lingkun Kong, Konstantinos MamourasOOPSLA 2023 · 22 citations
  5. Derivative Based Nonbacktracking Real-World Regex Matching with Backtracking SemanticsDan Moseley, Mario Nishio, Jose Perez Rodriguez, Olli Saarikivi et al.PLDI 2023 · 21 citations

Related papers

  1. Linear Matching of JavaScript Regular ExpressionsAurèle Barrière, Clément Pit-ClaudelPLDI 2024 · 11 citations
  2. Regulator: Dynamic Analysis to Detect ReDoSRobert McLaughlin, Fabio Pagani, Noah Spahn, Christopher Kruegel et al.USENIX Security 2022
  3. Efficient Matching of Regular Expressions with Lookaround AssertionsKonstantinos Mamouras, Agnishom ChattopadhyayPOPL 2024 · 19 citations
  4. REmatch: a novel regex engine for finding all matchesCristian Riveros, Nicolás Van Sint Jan, Domagoj VrgocVLDB 2023 · 10 citations
  5. Revealer: Detecting and Exploiting Regular Expression Denial-of-Service VulnerabilitiesYinxi Liu, Mingxue Zhang, Wei MengS&P 2021 · 28 citations
Dusk over the sea between two cliffs drawn in fine vertical lines