Regex Matching with Counting-Set Automata
summary
Paper builds a counting-set automata implementation (a CA prototype in Microsoft’s automata library) that determinises regexes with counters without exploding states. From 500,000 real-world regexes 1,789 contain nondeterministic counting; 89 cases make RE2 exceed 10s on a 10MB adversarial input while CA solves most within 1s and is faster on 287 benchmarks. CA automata average 29 states versus NFA 112 and DFA 2,802, and matching time stays constant as counter bounds grow.
AI-written summary · about
chapters (7)
- 0:00Research motivation
- 1:26Regex matching techniques
- 2:41Counting set automata
- 5:31Matching and implementation
- 7:44Efficiency and determinization
- 10:32Experimental results
- 13:39Future work and conclusion
related talks
51mRegular Expressions in C++, Present and Future
21mEfficient Matching of Regular Expressions with Lookaround Assertions
37mAll About Regular Expressions
18mRegular Expression Matching using Bit Vector Automata
22mStatic Analysis for Checking the Disambiguation Robustness of Regular Expressions
01h 03mCompile-Time Regular Expressions
24mSolving String Constraints with Regex-Dependent Functions through Transducers wi
19mDerivative Based Nonbacktracking Real-World Regex Matching with Backtracking Semantics