💬 NLP

On the Complexity of the Matching Problem of Regular Expressions with Backreferences

This paper establishes the fine-grained computational complexity of matching regular expressions with backreferences by proving conditional lower bounds under SETH and triangle detection assumptions while presenting an improved $O(n \log^2 n)$ algorithm for 1-use backreferences.

Original authors: Soh Kumabe, Yuya Uezato

Published 2026-05-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Soh Kumabe, Yuya Uezato

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Regex" Traffic Jam

Imagine you are a security guard at a club (the computer system). You have a list of rules (a Regular Expression) for who can get in.

Simple Rules: "Only people wearing red shirts." This is easy to check. You look at a shirt, say "Red? Yes, come in." It takes the same amount of time whether the line is 10 people or 10,000.
The Problem (ReDoS): Sometimes, hackers craft a specific line of people that tricks the guard into doing a massive amount of unnecessary work. Instead of checking one person and moving on, the guard starts checking Person A, then Person B, then Person A again, then Person C, then Person A again... until the guard collapses from exhaustion. This is called a Denial of Service (ReDoS) attack.

In the real world, this has caused massive websites like Stack Overflow and Cloudflare to crash. The paper notes that even "quadratic" slowness (where checking 100 people takes 10,000 steps) is enough to crash a system.

The Villain: "Backreferences"

Standard rules are simple. But modern "Regex" engines have a super-powerful feature called Backreferences.

The Analogy:
Imagine a rule that says: "Find a word, remember it, and then make sure the exact same word appears again later."

Example: "Find a word, call it 'X'. Then, find 'X' again."
If the input is apple ... apple, it works.
If the input is apple ... banana, it fails.

This feature is incredibly useful for programmers, but it makes the "guard's" job much harder. The guard has to remember what they saw earlier and constantly compare it to what they are seeing now. The paper asks: Can we build a guard who is fast enough to handle these complex rules without getting tired?

The Paper's Findings: The Good, The Bad, and The Ugly

The authors investigated exactly how hard it is to solve these matching problems. They broke it down into two sides: Hardness (Why it's difficult) and Algorithms (How to fix it).

1. The Bad News: Some Rules are Impossible to Speed Up

The paper proves that for certain types of complex rules, there is no "magic bullet" to make them fast.

The "Triangle" Problem: They showed that if you have a rule that uses two variables (like remembering two different words and checking them later), solving it is as hard as finding a triangle in a giant social network graph. If you could solve the rule quickly, you could solve the graph problem quickly. Since graph experts believe the graph problem is inherently slow, the rule problem must be slow too.
The "Orthogonal Vectors" Problem: For rules with even more variables, they proved that the time required grows exponentially with the number of variables. It's like trying to find a specific combination of keys in a lock; the more keys you have, the impossible it becomes to brute-force it quickly.

Takeaway: If your rule is too complex (using many "remember this" features), you cannot build a fast engine for it. You will always hit a wall.

2. The Good News: A "Near-Linear" Solution for Simple Cases

However, the paper found a sweet spot. They focused on a specific, common type of rule:

The "ABCBD" Pattern: "Find a word (A), then a word (B), then a word (C), then the exact same word B again, then a word (D)."
- Real-world example: "Find a username, then a password, then a message, then the same username again, then a signature."

The authors discovered that while this looks tricky, it can be solved very efficiently.

The Old Way: Previous methods were like checking every possible combination in a library, which took $O(n^2)$ time (quadratic). If the book was 1,000 pages, it took 1,000,000 steps.
The New Way: The authors built a new algorithm that takes roughly $O(n \log^2 n)$ $O (n lo g^{2} n)$ time.
- The Analogy: Imagine the library is organized with a magical index system (using Suffix Trees and Factorization Forests). Instead of reading every page, the guard can jump straight to the relevant sections. If the book is 1,000 pages, the new method takes roughly 10,000 steps (or even fewer), which is a massive improvement.

How the New Algorithm Works (The "Magic Tricks")

To achieve this speed, the authors used several clever techniques, which they describe in the paper:

The Suffix Tree (The Map): They built a giant map of the input string. This map shows every possible ending of the string. It helps the guard instantly see, "Oh, this word 'B' appears here, and it also appears there."
Heavy-Light Decomposition (The Sorting Hat): They split the map into "heavy" paths (very common paths) and "light" paths (rare paths). They only do the heavy lifting on the rare paths, saving time.
Periodicity (The Rhythm): They noticed that when a word repeats (like "B...B"), the string often has a rhythm or a pattern. They used math to predict these patterns instead of checking every single letter.
Factorization Forests (The Index): This is a data structure that acts like a super-fast index, allowing the guard to check if a chunk of text matches a rule in constant time, no matter how long the text is.

Summary of the Conclusion

Can we stop all ReDoS attacks? No. If a rule is too complex (too many "remember this" variables), it is mathematically proven to be slow.
Can we fix the most common complex rules? Yes! For the specific case where a rule remembers one word and checks for it once later (the "ABCBD" pattern), the authors created a new engine that is almost as fast as the simple rules.
Why does this matter? It tells software engineers: "Don't use too many backreferences, or you'll be slow. But if you use them in this specific, common way, you can now use our new method to keep your system safe and fast."

The paper essentially draws a line in the sand: Here is where the speed limit is unbreakable, and here is where we found a way to drive faster.

Technical Summary: On the Complexity of the Matching Problem of Regular Expressions with Backreferences

1. Problem Definition and Motivation

The paper investigates the fine-grained computational complexity of the Regular Expression Matching problem with Backreferences (REWB). While classical regular expressions (Regex) can be matched in linear time relative to the input string length $|w|$ using Thompson's construction, practical engines support backreferences (e.g., (E)x to capture a substring and \x to reuse it). This feature strictly extends the expressive power of Regex (allowing recognition of non-regular languages like $\{ww \mid w \in \Sigma^*\}$ ) but introduces significant algorithmic risks.

The motivation stems from Regular Expression Denial of Service (ReDoS) attacks, where adversaries craft inputs to trigger worst-case behavior in matching engines. Notable incidents at Stack Overflow (2016) and Cloudflare (2019) demonstrated that even quadratic-time behavior ( $O(|w|^2)$ ) in backtracking-based engines can cause catastrophic service outages. The authors pose the fundamental question: Is it possible to construct ReDoS-safe engines for REWB that run in linear or near-linear time?

The paper focuses on $r$ -use $k$ -REWBs, defined as expressions with $k$ distinct variables where the total number of backreference executions in any computation is bounded by $r$ .

2. Methodology and Technical Approach

The paper employs a dual approach: establishing conditional lower bounds (hardness) and designing efficient algorithms for specific subclasses.

2.1 Hardness Results

The authors strengthen previous complexity results by reducing well-known hard problems to REWB matching:

W[2]-hardness: By reducing the $k$ -Dominating Set problem, they prove that REWB matching is W[2]-hard when parameterized by the expression size $|E|$ . This strengthens the known W[1]-hardness result.
Conditional Lower Bounds (Triangle Detection): Assuming the "No-Almost-Linear-Time Hypothesis" for Triangle Detection, they show that even the highly restricted 2-use 2-REWB problem cannot be solved in $O(|w|^{1+\delta})$ time for any $\delta > 0$ .
Conditional Lower Bounds (k-OV): Under the $k$ -Orthogonal Vectors (k-OV) hypothesis (weaker than SETH), they prove that $k$ -REWB matching cannot be solved in $O(|w|^{2k-\epsilon})$ time. This implies that for general $k$ , near-linear time is unlikely.

2.2 Algorithmic Results

The primary algorithmic contribution focuses on 1-use REWBs (expressions with one variable referenced exactly once).

Canonical Form Transformation: The authors prove that any 1-use REWB can be transformed into a canonical form involving a sum of terms like $A (B)_x C \backslash x D$ , where $A, B, C, D$ are classical Regexes. This is termed the ABCBD problem.
Decomposition Strategy: The ABCBD problem is decomposed into two subproblems:
1. XYYZ Problem: The case where the two occurrences of $B$ are adjacent ( $w = w_A w_B w_B w_D$ ). This is solved using Crochemore's maximal local power enumeration and properties of ultimately periodic sets derived from transition monoids.
2. Branching ABCBD Problem: The case where the two occurrences of $B$ are separated by a non-empty $C$ , and the characters immediately following the two $B$ occurrences differ.
Suffix Tree and Heavy-Light Decomposition: For the Branching case, the algorithm utilizes the suffix tree of the input string $w$ . It employs heavy-light decomposition to partition the search space.
Data Structures:
- Factorization Forests: Used to evaluate Regex membership on substrings in constant time after linear preprocessing.
- Transition Monoids: Leveraged to track the state of Regexes $A, B, C, D$ efficiently.
- Custom Enumerators: The authors design specialized data structures (RightEnumerator, LeftEnumerator, AuxiliaryEnumerator) to handle transition enumeration. These structures use lazy updates and disjoint-set union (DSU) strategies to manage constraints that vary with the length of the substring $w_B$ .

3. Key Results

Hardness

Theorem 3: REWB matching is W[2]-hard parameterized by expression size.
Theorem 4: Assuming the Triangle Detection hypothesis, 2-use 2-REWB matching requires super-linear time (specifically, not $O(|w|^{1+\delta})$ ).
Theorem 5: Under the $k$ -OV hypothesis, $k$ -REWB matching requires $\Omega(|w|^{2k-\epsilon})$ time.

Algorithms

Theorem 7 (Main Result): The ABCBD problem admits an $O(|w| \log^2 |w|)$ time algorithm. The hidden constant depends exponentially on the sizes of the Regexes $A, B, C, D$ ( $2^{O((|A|+|B|+|C|+|D|)^2)}$ ).
Theorem 8: Consequently, the 1-use REWB matching problem admits an $O(|w| \log^2 |w|)$ time algorithm.
Theorem 9: The XY $\alpha$ Z problem (generalizing XYYZ to $\alpha$ repetitions) admits an $O(|w| \log |w|)$ time algorithm.

These results represent a significant improvement over the previous best-known $O(|w|^2)$ algorithm for the ABCBD problem by Nogami and Terauchi (MFCS 2025).

4. Significance and Claims

The paper claims to provide a fundamental understanding of the complexity landscape for REWB matching:

ReDoS Safety: It establishes that while general REWB matching is likely intractable for near-linear time, a practically relevant subclass (1-use REWB) can be matched in near-linear time. This suggests that engines supporting 1-use backreferences could theoretically be made ReDoS-safe.
Fine-Grained Complexity: The work delineates the boundary between tractable and intractable cases. It shows that increasing the number of backreference uses from 1 to 2 (even with only 2 variables) likely pushes the problem out of the near-linear regime.
Algorithmic Innovation: The paper introduces a complex but highly non-trivial algorithmic framework combining suffix trees, factorization forests, and transition monoids to solve a problem previously thought to require quadratic time.

The authors explicitly state that their algorithm is uniform, meaning it processes the expression and input string together without non-uniform advice dependent on the fixed expression. They acknowledge that the exponential dependency on the expression size $|E|$ remains a limitation for very large expressions, and they leave open the question of whether a truly linear-time algorithm ( $O(|w|)$ ) exists or if the logarithmic factors can be removed.

5. Limitations and Open Problems

The paper identifies several open directions:

Complexity of $r$ -use 1-REWB: The complexity for $r$ -use 1-REWBs where $r \ge 2$ remains open.
Linear Time: Whether the $O(|w| \log^2 |w|)$ bound can be improved to $O(|w|)$ .
Expression Dependency: Reducing the exponential dependency on $|E|$ to polynomial while maintaining near-linear dependence on $|w|$ .
Broader Features: Extending these results to other practical regex features like lookarounds, atomic grouping, and greedy/lazy stars.