Regular Expression Matching using Bit Vector Automata

Explore a novel algorithm for efficient matching of regular expressions with bounded repetition in this 18-minute conference talk from OOPSLA 2023. Dive into the concept of nondeterministic bit vector automata (NBVA), a new model designed to be expressively equivalent to nondeterministic counter automata with bounded counters. Learn how this approach can match certain regular expressions with bounded repetition in time independent of repetition bounds. Discover the implementation of this technique in the BVA-Scan regex engine and its performance comparison against state-of-the-art alternatives on real datasets. Gain insights into addressing performance challenges in regex matching, particularly for patterns involving advanced constructs like bounded repetition.

[OOPSLA23] Regular Expression Matching using Bit Vector Automata