# Real-time Regular Expression Matching

arXiv: https://arxiv.org/abs/2308.10208 · HTML: https://mlsanity.com/paper/2308.10208/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 29 references that are in the map.
- First posted on arXiv 20 Aug 2023.

## Builds on (most cited first, 2 of 2)

- [Which Regular Expression Patterns are Hard to Match?](https://mlsanity.com/paper/1511.07070/) (2015)
- [Simulating and Reconstructing Neurodynamics with Epsilon-Automata Applied to Electroencephalography (EEG) Microstate Sequences](https://mlsanity.com/paper/1710.02387/) (2017)

## Abstract (arXiv)

This paper is devoted to finite state automata, regular expression matching, pattern recognition, and the exponential blow-up problem, which is the growing complexity of automata exponentially depending on regular expression length. This paper presents a theoretical and hardware solution to the exponential blow-up problem for some complicated classes of regular languages, which caused severe limitations in Network Intrusion Detection Systems work. The article supports the solution with theorems on correctness and complexity.