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

Watch this 21-minute conference talk from POPL 2025 where researchers Ian Erik Varatalu, Margus Veanes, and Juhan Ernits present RE#, a novel tool and theory for regular expression matching. Learn about their approach built on symbolic derivatives that avoids backtracking while supporting complement, intersection, and restricted lookarounds beyond classical regex operators. Discover how their formal theory demonstrates input-linear complexity in both theoretical analysis and experimental results. The presentation showcases comprehensive benchmark evaluations where RE# outperforms the next fastest Rust regex engine by over 71% on baseline tests and surpasses all state-of-the-art engines on extended benchmarks, often by several orders of magnitude. The research has been recognized with "Artifacts Available" and "Artifacts Evaluated — Functional" badges, with supplementary materials available via Zenodo.