Real-time Regular Expression Matching

Alexandra Bernadotte
8/20/2023
cs.FLcs.CCcs.CV

No official code found. Best implementation: google/re2j (1,251 stars, last commit 2025-01-09).

Abstract

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.

View on arXivView PDF

Code Implementations(1)

google/re2jCommunity73%

linear time regular expression matching in Java

1,251163HTML, JavaFeb 18, 20151 years agoNOASSERTION
javaregular-expressions

Similar Papers

New Linear-time Algorithm for SubTree Kernel Computation based on Root-Weighted Tree Automata

78% match2023

Active Learning of Symbolic Automata Over Rational Numbers

77% match2025

An $\mathbf{L^*}$ Algorithm for Deterministic Weighted Regular Languages

77% match2024

Autoregressive Large Language Models are Computationally Universal

77% match2024

Provable Scaling Laws for the Test-Time Compute of Large Language Models

77% match2024

Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs

77% match1 repo52023

Cite this paper

@article{bernadotte2023realtime,
  title  = {Real-time Regular Expression Matching},
  author = {Alexandra Bernadotte},
  year   = {2023},
  eprint = {2308.10208},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2308.10208v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2308.10208.svg)](https://codeofpaper.com/paper/2308.10208)

Discussion