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

Soh Kumabe

CyberAgent, Inc., Tokyo, Japan Yuya Uezato

CyberAgent, Inc., Tokyo, Japan
National Institute of Informatics, Tokyo, Japan

Abstract

Regular Expression Denial of Service (ReDoS) is a well-known type of algorithmic complexity attack, where an adversary supplies maliciously crafted strings to a regular expression matching engine, aiming to exhaust computational resources of systems. Even quadratic-time behavior in matching engines has been exploited in successful attacks, as exemplified by major outages at Stack Overflow (2016) and Cloudflare (2019). These incidents motivate a fundamental question: Is it possible to construct matching engines that run in linear or near-linear time in the length of the input string? For classical regular expressions (REGEX), Thompson’s construction yields a linear-time algorithm for fixed expressions. However, practical engines support powerful features such as backreferences, which allow capturing a substring and reusing it later. This feature strictly extends the expressive power of REGEX but unfortunately increases the risk of ReDoS attacks.

This paper investigates the fine-grained complexity of the string matching problem for regular expressions with backreferences (REWBs). Specifically, we consider $r$ -use $k$ -REWBs, i.e., REWBs with $k$ variables such that, in any computation, the total number of backreference executions is at most $r$ . On the hardness side, we show that the string matching problem for $k$ -REWBs cannot be solved in $O(n^{2k-\epsilon})$ time for any $\epsilon>0$ under the Strong Exponential Time Hypothesis (SETH), where $n$ is the length of the input string. We also prove that this problem is W[2]-hard when parameterized by the length of the REWB expression, strengthening the previous W[1]-hardness result. Moreover, we prove that this problem for $2$ -use $2$ -REWBs cannot be solved in $n^{1+o(1)}$ time unless the triangle detection problem can be solved in that time. On the algorithmic side, we present an $O(n\log^{2}n)$ -time algorithm for $1$ -use REWBs. In particular, we focus on the ABCBD problem, which is the REWB matching problem for the form $A\,(B)_{x}\,C\,\backslash x\,D$ where $A$ , $B$ , $C$ , and $D$ are fixed REGEXes. We also show that every $1$ -use REWB can be transformed into this canonical form. Our algorithm significantly improves upon the recent $O(n^{2})$ -time algorithm for the ABCBD problem by Nogami and Terauchi (MFCS, 2025). Our algorithm is highly nontrivial and employs several techniques, including suffix trees, transition monoids of REGEXes, factorization forest data structures, and periodicity of strings.

Keywords and phrases:

Pattern Matching, Regular Expression, Backreference, Fine-grained Complexity

Category:

Track A: Algorithms, Complexity and Games

Funding:

Yuya Uezato: Yuya Uezato was supported by JST, CREST Grant Number JPMJCR21M3.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Pattern matching ; Theory of computation

\rightarrow

Formal languages and automata theory

Related Version:

Full Version: https://arxiv.org/abs/2605.07289 [53]

Acknowledgements:

We are grateful to the anonymous reviewers for their careful reading and valuable comments. We are especially indebted to the anonymous reviewers of an earlier version of this work, whose detailed and constructive feedback led to substantial improvements in the technical exposition, the organization, and the overall clarity of the paper.

DOI:

10.4230/LIPIcs.ICALP.2026.135

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Background.

Regular expressions are widely used in web services to validate and filter user-provided text. However, depending on the engine implementation and the specific expressions used, the worst-case regular expression matching time can be prohibitive. In most web-service settings, expressions are fixed by the application, while the input string is provided by potentially untrusted users. In such cases, an adversary can craft inputs that trigger the worst-case behavior, potentially exhausting computational resources (CPU and memory) and causing service outages.

Attacks that exploit such worst-case algorithmic behavior are known as algorithmic complexity attacks [21]. Those specifically involving regular expressions are called ReDoS (Regular Expression Denial of Service) [20]. ReDoS is a major vulnerability and is cataloged in the Common Weakness Enumeration (CWE, the de facto standard for vulnerability classification) as CWE-1333 [58].

We highlight two well-documented service outages caused by ReDoS, together with the real-world regular expression that triggered the worst-case behavior in the deployed engines.¹¹1These two examples are written in the syntax of the corresponding real-world regex engines, not in the formal syntax introduced below. For example, \s is a whitespace character class and \u200c is the Unicode escape for U+200C. These examples are used only to demonstrate that backtracking engines can already cause quadratic-time ReDoS without backreferences.

1.

The 2016 Stack Overflow outage, caused by the expression
ˆ[\s\u200c]+|[\s\u200c]+$ [78].
2.

The 2019 Cloudflare outage, caused by an expression whose core part is .*.*=.* [43].

According to their reports [78, 43], these outages occurred because the employed regular expression engines relied on backtracking algorithms. Consequently, the above expressions exhibited quadratic-time computation on crafted inputs. It is well known that backtracking-based engines can cause catastrophic exponential backtracking [36, 16, 39], and it is widely believed that avoiding exponential behavior would be sufficient. However, these incidents were surprising in showing that even quadratic-time behavior can lead to a system outage. This is stated explicitly in the post-mortem [78], which we quote verbatim below:

So the Regex engine has to perform a “character belongs to a certain character class” check (plus some additional things) 20,000+19,999+19,998+…+3+2+1 = 199,990,000 [sic] times, and that takes a while. This is not classic catastrophic backtracking (performance is $O(n^{2})$ , not exponential, in length), but it was enough.

Motivated by this background, we propose the following criterion:

A regular expression engine is ReDoS-safe if, for each fixed expression, it runs in linear or near-linear time in the length of the input string.

In this paper, we address the following fundamental questions: Can we construct a ReDoS-safe regular expression engine in the above sense? If so, which practical extensions can such an engine still support?

Complexity of REGEX matching problems

The term “regular expression” is used for several different formalisms. In this paper, following classical formal language theory, we use the standard (Kleene) regular expressions, denoted by REGEX.

Definition 1 (Syntax of REGEX).

The syntax of REGEX over an alphabet $\Sigma$ is given by the grammar:

E::=\emptyset\mid\epsilon\mid\sigma\mid E+E\mid E\cdot E\mid E^{*}\qquad\text{% where $\sigma\in\Sigma$}.

We give the formal semantics, including the language $\mathbb{L}\left(\cdot\right)$ , in the full version [53]. For REGEX, we consider the following computational problem.

REGEX Matching Problem

Fixed Object: A REGEX $E$ .

Input: A string $w$ .

Task: Deciding if $w\in\mathbb{L}\left(E\right)$ where $\mathbb{L}\left(E\right)$ is the language of $E$ .

Is it possible to design a ReDoS-safe engine for the REGEX matching problem? The answer is Yes. Using Thompson’s construction [80] and the standard efficient NFA simulation [16][3, Sec 3.7], we can solve this problem in $O(|E|\,|w|)$ time, which is linear in $|w|$ for each fixed $E$ .

From REGEX to REWB

Does the linear-time algorithm for REGEX matching fully resolve ReDoS in practice? The answer is No. This is because most real-world regular expression engines support extensions beyond REGEX. One of the most prominent extensions is backreferences. We use REWB to denote the class of regular expressions with backreferences. Unlike REGEX, REWB allows variables that capture substrings matched by a subexpression and refer back to that captured string later. Backreferences are widely supported in the standard regular expression libraries of major programming languages (e.g., C++, Java, JavaScript, Python, Ruby, Perl, PHP, and OCaml). The syntax of REWB is given as follows.

Definition 2 (Syntax of REWB).

The syntax of REWB is given by the following grammar:

E::=\emptyset\mid\epsilon\mid\sigma\mid E+E\mid E\cdot E\mid E^{*}\mid(E)_{x}% \mid\mathord{\backslash x},

where $\sigma\in\Sigma$ and $x$ is a variable. The expression $(E)_{x}$ captures the substring matched by $E$ and stores it in $x$ , while $\mathord{\backslash x}$ refers to the content stored in $x$ .

As with REGEX, we give the formal semantics of REWB in the full version [53].

We note that REWB is strictly more expressive than REGEX. Consider the expression $E:=((0+1)^{*})_{x}\>\mathord{\backslash x}$ . Intuitively, the subexpression $((0+1)^{*})_{x}$ matches an arbitrary string $w\in\{0,1\}^{*}$ and binds it to $x$ . Then, $\mathord{\backslash x}$ matches the captured substring stored in $x$ . Hence, $E$ defines the non-regular language $\{ww:w\in\{0,1\}^{*}\}$ .

This paper focuses on the following problem.

REWB Matching Problem

Fixed Object: A REWB $E$ .

Input: A string $w$ .

Task: Deciding if $w\in\mathbb{L}\left(E\right)$ .

This raises a natural question: Is it possible to design a ReDoS-safe engine for the REWB matching problem? Unfortunately, No. If we view $E$ as part of the input and parameterize the problem by $c$ , the number of variable occurrences in $E$ , then the REWB matching problem is W[1]-hard [79, 33]. In particular, under the standard assumption $\mathbf{FPT}\neq\textbf{W[1]}$ , there is no uniform algorithm running in $f(c)\cdot|w|^{O(1)}$ for all inputs $(w,E)$ . However, this worst-case hardness is too pessimistic for practice. In practice, many real-world REWB expressions use backreferences in restricted ways. To identify which REWB subclasses are ReDoS-safe and which remain vulnerable, we need a fine-grained analysis of the REWB matching problem.

Classification of REWB

We write $k$ -REWB to denote the set of REWBs that have at most $k$ distinct variables. We say that an expression $E$ is $r$ -use if, for every input string $w$ and for all computations of $E$ on $w$ , the total number of executed backreferences (i.e., executed occurrences of $\mathord{\backslash x}$ ) is at most $r$ . Intuitively, a computation is one possible run of $E$ on $w$ ; different runs may arise from different choices at the union and Kleene-star subexpressions of $E$ , and may therefore execute different numbers of backreferences. If no such finite $r$ exists, we call $E$ $\omega$ -use. We illustrate these notions with the following examples:

$\blacksquare$

$(\Sigma^{*})_{x}\mathord{\backslash x}$ is a $1$ -use $1$ -REWB because there is only one variable $x$ , which is referenced once.
$\blacksquare$

$(\Sigma^{*})_{x}\>\mathord{\backslash x}\>\mathord{\backslash x}$ is a $2$ -use $1$ -REWB because there is only one variable $x$ , which is referenced twice.
$\blacksquare$

$(\Sigma^{*})_{x}\>\mathord{\backslash x}\>(\Sigma^{*})_{x}\>\mathord{% \backslash x}$ is also a $2$ -use $1$ -REWB that reuses the single variable $x$ .
$\blacksquare$

$(\Sigma^{*})_{x}\>(\mathord{\backslash x})^{*}$ is an $\omega$ -use $1$ -REWB, as $x$ can be referenced an unbounded number of times.
$\blacksquare$

$(\Sigma^{*})_{x}\ (\Sigma^{*})_{y}\mathord{\backslash y}\mathord{\backslash x}$ is a $2$ -use $2$ -REWB because it contains two variables $x$ and $y$ , which are referenced a total of two times.

We allow both capture groups and backreferences to appear inside capture groups. That is, the body of a capture group $(\cdots)_{x}$ may contain subexpressions of the form $\mathord{\backslash y}$ or $(\cdots)_{y}$ , where $y$ may be equal to $x$ . For example, $(\mathord{\backslash x}\,\mathord{\backslash x})_{x}$ (“doubling the content of $x$ ”) and $(0\,\mathord{\backslash x}\>0)_{x}$ (“wrapping $x$ with $0$ s”) are well-formed.

Known algorithmic results for REWB matching

The current best-known algorithm for $k$ -REWB matching runs in $O(|E|\cdot|w|^{1+2k})$ time [25, §IX. C][70] based on standard dynamic programming. Recently, Nogami and Terauchi studied the ABCBD problem, a subclass of the $1$ -REWB matching problem, and gave an $O(|E|^{2}|w|^{2})$ -time algorithm [70, Thm. 5]. Although their result improved upon the standard DP-based $O(|E|\,|w|^{3})$ -time algorithm, it is not ReDoS-safe due to its quadratic dependence on $|w|$ .

1.1 Our Contribution

We summarize our main hardness and algorithmic results.

1.1.1 Hardness Results for the REWB Matching Problem

We strengthen the previously known W[1]-hardness results [79, 33] by showing W[2]-hardness.

Theorem 3.

When the expression $E$ is part of the input, the REWB matching problem is $\mathbf{W[2]}$ -hard parameterized by the expression size $|E|$ .

Assuming that Triangle Detection on an $m$ -edge graph does not admit an $m^{1+\delta-o(1)}$ -time algorithm [1, Conjecture 3], we derive a conditional lower bound even for the highly restricted class, $2$ -use 2-REWB.

Theorem 4.

Assuming the no-almost-linear-time hypothesis for Triangle Detection, there exists a fixed $2$ -use $2$ -REWB expression $\Psi$ such that the matching problem for $\Psi$ cannot be solved in $|w|^{1+\delta-o(1)}$ time for some constant $\delta>0$ .

Under the $k$ -Orthogonal Vectors hypothesis ( $𝒌$ -OV) [84], which is a weaker assumption than the strong exponential time hypothesis (SETH), we have the following result.

Theorem 5.

Assuming the $𝐤$ -OV hypothesis, for each fixed integer $k\geq 1$ , there exists a fixed $\omega$ -use $k$ -REWB expression $\Psi_{k}$ such that the matching problem for $\Psi_{k}$ cannot be solved in $O(|w|^{2k-\epsilon})$ time for any $\epsilon>0$ .

Very recently and independently of our work, Nogami and Terauchi [71, Theorem 1] proved the following lower bound: assuming the $2$ -OV hypothesis, no algorithm solves the $1$ -REWB matching problem in $O(|w|^{2-\epsilon}\,\text{poly}(|E|))$ time. Our result strengthens theirs in the following two ways: (1) our hardness holds for general $k$ ; and (2) as our hardness holds for a fixed expression $\Psi_{k}$ , it rules out any speedup gained by allowing arbitrary dependence on $|E|$ .

1.1.2 Algorithmic Results

We have shown that the REWB matching problem remains hard even for $2$ -use $2$ -REWBs (Theorem 4) and for ( $\omega$ -use) $1$ -REWBs (Theorem 5 with $k=1$ ) when seeking a near-linear-time algorithm. This naturally raises the question: What is the complexity of $1$ -use REWB matching? Our main algorithmic result is a near-linear-time algorithm for the following special case:

ABCBD Problem

Fixed Objects: REGEXes $A$ , $B$ , $C$ , and $D$ .

Input: A string $w$ .

Task: Deciding if we can decompose $w$ into $w=w_{A}\,w_{B}\,w_{C}\,w_{B}\,w_{D}$ so that $w_{A}\in\mathbb{L}\left(A\right)$ , $w_{B}\in\mathbb{L}\left(B\right)$ , $w_{C}\in\mathbb{L}\left(C\right)$ , and $w_{D}\in\mathbb{L}\left(D\right)$ . Equivalently, decide whether $w\in\mathbb{L}\left(A\,(B)_{x}\,C\,\mathord{\backslash x}\,D\right)$ .

At first glance, this syntax may appear highly restricted. However, the ABCBD problem captures the general case of $1$ -use REWB in the following sense:

Theorem 6.

For any 1-use REWB $E$ , there exists an equivalent REWB of the following form:

(A_{1}\,(B_{1})_{x}\,C_{1}\,\mathord{\backslash x}\,D_{1})+(A_{2}\,(B_{2})_{x}% \,C_{2}\,\mathord{\backslash x}\,D_{2})+\cdots+(A_{K}\,(B_{K})_{x}\,C_{K}% \mathord{\backslash x}\,D_{K})+E^{\prime}

where $A_{i}$ , $B_{i}$ , $C_{i}$ , $D_{i}$ , $E^{\prime}$ are REGEXes. We can construct the above representation in $O(|E|^{4})$ time. Furthermore, the following holds for their size:
$K=O(|E|^{2}),\ |A_{i}|=O(|E|^{2}),\ |B_{i}|=O(|E|),\ |C_{i}|=O(|E|^{2}),\ |D_{% i}|=O(|E|),\ |E^{\prime}|=O(|E|^{2}).$

The main result of this paper is as follows.

Theorem 7.

The ABCBD problem admits an $O(|w|\log^{2}|w|)$ -time algorithm. The hidden constant is $2^{O((|A|+|B|+|C|+|D|)^{2})}$ .

This significantly improves the $O(|w|^{2})$ -time algorithm of Nogami and Terauchi [70]. Our algorithm is highly nontrivial; for a more detailed overview, see Section 3. Note that our algorithm can also be viewed as a near-linear-time fixed-parameter algorithm for the ABCBD matching problem, parameterized by the (combined) size of REGEXes $A$ , $B$ , $C$ , and $D$ . Combining Theorems 6 and 7, we obtain the following.

Theorem 8.

The $1$ -use REWB matching problem admits an $O(|w|\log^{2}|w|)$ -time algorithm. The hidden constant is $2^{O(\,|E|^{4}\,)}$ .

Note that the hidden constant $2^{O(\,|E|^{4}\,)}$ is larger than in Theorem 7 because Theorem 6 may yield expressions of quadratic length.

Remark: Uniformity.

The algorithms in Theorems 7 and 8 are uniform. Namely, they take the relevant expressions ( $A, B, C, D$ in Theorem 7, and $E$ in Theorem 8) together with the input string $w$ , perform all preprocessing depending on these expressions, and then run the main procedures. The fixed-object formulation only emphasizes the dependence on $|w|$ ; no non-uniform advice depending on the fixed expressions is assumed.

As a key subroutine for solving the ABCBD problem, we have also developed an efficient algorithm for the following problem.

$XY^{\alpha}Z$ Problem

Fixed Objects: An integer $\alpha\geq 2$ and REGEXes $X$ , $Y$ , and $Z$ .

Input: A string $w$ .

Task: Deciding if we can decompose $w$ into $w=w_{X}\,\smash{\overbrace{w_{Y}\,\cdots\,w_{Y}}^{\alpha\text{ times}}}\,w_{Z}$ so that $w_{X}\in\mathbb{L}\left(X\right)$ , $w_{Y}\in\mathbb{L}\left(Y\right)$ , and $w_{Z}\in\mathbb{L}\left(Z\right)$ . Equivalently, decide whether $w\in\mathbb{L}\left(X\,(Y)_{x}\,(\mathord{\backslash x})^{\alpha-1}\,Z\right)$ .

Our theorem for this problem is the following.

Theorem 9.

The $XY^{\alpha}Z$ problem admits an $O(|w|\log|w|)$ -time algorithm. The hidden constant is $2^{O(s^{2})}+\alpha\cdot 2^{O(s)}$ , where $s:=|X|+|Y|+|Z|$ . Alternatively, at the cost of an additional $\log|w|$ factor (i.e., time $O(|w|\log^{2}|w|)$ ), we can achieve a polynomial dependence on $s+\alpha$ .

1.1.3 Open Problems

Several problems remain to be investigated. The first direction is to specify classes of REWB that admit near-linear-time algorithms. We have shown that $1$ -use REWBs admit a near-linear-time algorithm, whereas $2$ -use $2$ -REWBs and $\omega$ -use $1$ -REWBs are unlikely to admit such algorithms. However, the matching complexity of $r$ -use $1$ -REWB for any constant $r\geq 2$ remains open.

The second direction is to improve our algorithm for the $A B C B D$ problem. The most direct question is whether we can eliminate the remaining logarithmic factor and obtain a truly linear-time algorithm: reducing $O(|w|\log^{2}|w|)$ to $O(|w|)$ . Moreover, when REWB $E$ is given as input, our algorithm has an exponential dependency on the expression length $|E|$ . Specifically, it is open whether it is possible to reduce the dependence on $|E|$ to polynomial while preserving near-linear dependence on $|w|$ . Note that, if we allow quadratic dependence on $|w|$ , the algorithm of Nogami and Terauchi [70] already achieves $O(|E|^{2}|w|^{2})$ -time. Furthermore, as we describe in Section 3, our algorithm consists of many building blocks and is therefore quite complex. Simplifying it is a meaningful task both for advancing theoretical understanding and for improving practical implementability.

The third direction is to broaden the scope. Real-world regular expression engines support many features beyond backreferences, such as lookaround [36, 41], greedy and lazy Kleene stars [36, 42], and atomic grouping [36, 40]. Therefore, investigating the complexity of matching regular expressions augmented with such features is important in practice. We believe that these problems are also theoretically interesting, in the same way that the REWB matching problem admits deep algorithmic study, as demonstrated in this paper.

1.1.4 Organization

The rest of the paper is organized as follows. Section 2 reviews related work on ReDoS and on hardness and algorithmic results for REGEX, REWB, and related matching problems. Section 3 gives a technical overview of our main algorithmic result, Theorem 7. Section 4 presents our hardness results: W[2]-hardness from $k$ -Dominating Set, a conditional lower bound for 2-use 2-REWBs under the Triangle Detection hypothesis, and a lower bound for $k$ -REWBs under the $k$ -OV hypothesis, and hence under SETH. The remaining proofs and complete algorithmic details are deferred to the full version [53].

2 Related Work

2.1 ReDoS

Regular Expression Denial of Service (ReDoS) has been recognized as an important instance of algorithmic complexity attacks [21] since at least 2003 [20]. Outages at Stack Overflow (2016) [78] and Cloudflare (2019) [43] are representative examples, and notably, both incidents were triggered by quadratic behavior of regular expression engines, highlighting that even polynomial complexity can result in severe real-world failures. ReDoS is a common type of DoS attack that is officially cataloged as CWE-1333: Inefficient Regular Expression Complexity [58]. Vulnerabilities continue to be discovered and reported in practice; high-risk examples include [61, 62, 63, 64, 65] from 2021 to 2024. In 2025, notable entries in the CVE (Common Vulnerabilities and Exposures, which maintains a public record of disclosed security issues) include [66, 67, 68].

At its core, ReDoS arises from backtracking-based regex engines, which may exhibit catastrophic (possibly exponential) backtracking [39]. This behavior has long been known to automata theorists, and an influential book [36] helped disseminate the problem more widely to practitioners. For classical REGEX matching, Cox [16, 17] recommended that practitioners prefer Thompson NFA-based implementations over backtracking-based engines, as the former run in $O(|E|\,|w|)$ time. In contrast, it is unlikely that REWB matching admits such a “silver bullet” solution like the Thompson construction, as this problem is NP-hard in general [2, 9]. This has motivated complexity-theoretic research into the REWB matching problem, including the identification of tractable classes [35, 70, 75].

As an example of ReDoS involving expressions with backreferences, we focus on CVE-2017-16114 [59] and CVE-2019-25103 [60]. Both cases are triggered by an expression that can be abstracted as $E:=(a^{*})_{x}\ b^{*}\,((a+b)^{*}\,b)\,b^{*}\ \mathord{\backslash x}$ , on which backtracking-based engines take cubic time in the worst case. In CVE-2019-25103, the corresponding patch [13] rewrote $E$ to $E_{1}:=(a^{*})_{x}\ ((a+b)^{*}\,b)\ \mathord{\backslash x}$ ; it modified only the “REGEX-part” without touching the “backreference-part”. Consequently, although the ReDoS vulnerability is mitigated, potential vulnerabilities remain, as even the patched version exhibits quadratic time complexity; this issue seems to be an inevitable overhead of backtracking-based engines, as they try all possible prefixes that the variable $x$ captures. In CVE-2017-16114, the corresponding patch [82] rewrote $E$ to $E_{2}:=(a^{*})_{x}\,\bigl(b+(b(a+b)b)\bigr)^{*}\,\mathord{\backslash x}$ . Although $E_{2}$ admits linear-time matching, it alters the accepting language: for example, $E$ and $E_{1}$ accept $a\,ab\,a$ but $E_{2}$ does not. In contrast, the original expression falls within our $A B C B D$ fragment; thus, it can be evaluated in near-linear time by our algorithm without modifying the semantics.

2.2 Hardness of Regular Language Matching Problems

On REGEX

While Thompson’s construction [80] solves REGEX matching in $O(\,|E||w|\,)$ time, Backurs and Indyk [7, Thm.3] proved that $O(\,(|E||w|)^{1-\epsilon}\,)$ time is unachievable under SETH.

Recently, Bringmann et al. introduced the NFA Acceptance Hypothesis [12]: intuitively, for a dense NFA $A$ , the membership problem $w\in\mathbb{L}\left(A\right)$ cannot be solved in $O(\,(|A||w|)^{1-\epsilon}\,)$ time for any $\epsilon>0$ . Bille and Gørtz [10] introduced a parameter called density $\Delta$ (the total number of active states during the simulation on the input $w$ ) and proved that matching for sparse NFAs (or REGEXes) also cannot be solved in $O(\Delta^{1-\epsilon})$ time under SETH. These results suggest that improving upon the textbook $O(|E||w|)$ -time algorithm for REGEX matching is unlikely at present.

On REWB

The REWB matching problem is known to be NP-complete [2, Thm 6.2] when the REWB expression is a part of the input, even over a unary alphabet [9]. Moreover, when parameterized by the number of variables $k$ , the $k$ -REWB matching problem is W[1]-hard [33, Thm. 1]. In fact, W[1]-hardness already holds for a more restricted fragment of REWB called pattern languages [33, Thm. 1][79, Thm. 1]. We briefly recall pattern languages below to relate them to REWB and summarize known algorithmic results.

2.3 Algorithms for Regular Expression Matching Problems

On REWB

The current best-known algorithm for the $k$ -REWB matching problem is based on dynamic programming and runs in $O(|E|\cdot|w|^{1+2k})$ time [25, §IX. C]. Applying this algorithm to the ABCBD problem yields an $O(|E|\cdot|w|^{3})$ -time algorithm. Nogami and Terauchi gave an $O(|E|^{2}|w|^{2})$ -time algorithm, and thereby improved the dependence on $|w|$ from cubic to quadratic. As noted earlier, our Theorem 7 further improves the dependence on $|w|$ to near-linear.

Freydenberger and Schmid [35] considered the matching problem for the class of deterministic REWBs, which is a subclass of REWBs that can deterministically match strings when reading from the left. They gave an $O(k|w|)$ -time algorithm for $k$ -REWB. Schmid [75] extended this result to the wider class of memory-deterministic REWBs and gave an $O(|E|^{c}|w|)$ -time algorithm for some constant $c$ . They also refined the time complexity of the REWB matching problem to $O(|E|\cdot|w|^{O(\alpha)})$ for the cases of small $\alpha$ , where $\alpha\,(\leq k)$ denotes the active variable degree, which represents the maximum number of variables that are “active” at the same time.

Pattern Language and Word Equation

A pattern language is a class of languages generated by patterns, that is, strings that may also contain variables that can be matched to strings. For example, the pattern $P:=01X10X$ over $\Sigma=\{0,1\}$ with a variable $X$ generates the language $\{\,01w10w:w\in\Sigma^{*}\}$ . This concept was introduced by Angluin in the late 1970s in the context of learning theory and has since been studied extensively [5, 6, 57, 77].

Pattern languages can be seen as a very restricted subclass of REWB. Specifically, a pattern language can be expressed as a REWB that: (1) uses a capture group $(\ldots)_{x}$ for the first occurrence of each variable $x$ , (2) uses a backreference $\mathord{\backslash x}$ for all subsequent occurrences, and (3) only allows concatenation as the outermost operator (no union or Kleene star over captures/backreferences). For example, the above pattern $P$ equals the REWB $01(\Sigma^{*})_{X}10\mathord{\backslash X}$ .

The matching problem of pattern languages is NP-complete [5, 6, 29, 51] even for the case with alphabet size $2$ , each variable occurs at most twice, and each variable can be replaced with a string of length in $\{0,1\}$ or $\{1,2,3\}$ [32]. Ibarra et al. gave an $O\left(\frac{(|P|+|w|)|w|^{k-1}}{(k-1)!}\right)$ -time algorithm for the membership problem of $k$ -variable pattern languages, where $P$ is the given pattern expression [47]. In particular, it runs in linear time when $k=1$ . Fernau et al. [30] gave algorithms for several classes of pattern languages with good properties. Particularly, they showed that for the case of non-crossing (i.e., scopes of different variables do not overlap) pattern languages, the matching problem admits an $O(m|w|\log|w|)$ -time algorithm, where $m$ is the number of one-variable blocks occurring in a given pattern [30, Thm 8][31, Thm 4.16]. Observe that our $XY^{\alpha}Z$ problem generalizes the case $m=1$ by allowing arbitrary REGEXes for $X$ , $Y$ , and $Z$ .

Given two pattern languages (possibly sharing variables), the word equation problem asks whether there is a string that matches both of them. The case that one of the languages contains no variables is equal to the pattern language matching problem. In general, the word equation problem is known to be in PSPACE [74]. For the $1$ -variable case, Dąbrowski and Plandowski [23] gave an $O(m\>+\>\#_{X}\log m)$ -time algorithm where $m$ is the total size of given patterns and $\#_{X}$ is the total number of variable occurrences. Later, in the RAM-model setting, Jeż [48] gave an $O(m)$ -time algorithm using the recompression technique introduced by Jeż [49]. Dąbrowski and Plandowski [24] gave an $O(m^{5})$ -time algorithm for the $2$ -variable case. In contrast, the problem becomes significantly harder for $k\geq 3$ variables; even for the $3$ -variable case, it is not even known whether the problem is in NP [50]. Schulz [76] considered a variant of the word equation problem that each variable has a REGEX constraint. They proved this variant is decidable; it was later proved to be PSPACE-complete by Diekert et al. [26].

On REGEX with Lookaround

Lookaround is one of the features that real-world regular expression engines support, which checks whether a specified pattern exists around the current position, without consuming characters. It is folklore that the language class of REGEX equipped with lookaround is regular²²2We can convert it to a two-way alternating finite automaton (2AFA) [14], whose language class is regular [54].; thus, it admits $O(|w|)$ time matching by Thompson’s construction when we only consider the dependence on $|w|$ . Therefore, research concerns the dependence on the expression length $|E|$ , and particularly, focuses on $O(|E|\cdot|w|)$ time algorithms.

Mamouras and Chattopadhyay [56] provided an $O(|E|\cdot|w|)$ time membership algorithm. Chattopadhyay et al. [15] mechanized an algorithm of the same complexity based on [56] and verified its correctness using the proof assistant Rocq (formerly known as Coq). Barrière and Pit-Claudel [8] provided a matching algorithm of the same complexity that is faithful to JavaScript REGEX matching semantics. Fujinami and Hasuo [37] provided a matching algorithm of the same complexity, which also supports atomic grouping, which is a practical extension that does not enlarge the language expressiveness [36, 40]. Uezato [81] proved that the membership problem of REWB equipped with lookahead (lookaround that only examines after the current position) is PSPACE-complete.

Gapped Patterns

Another well-studied regular-language formalism, motivated by practical pattern matching applications (rather than REWB), is that of gapped patterns. A typical gapped pattern $G$ has the form

G\equiv p_{0}\,\Sigma^{[\alpha_{1},\,\beta_{1}]}\,p_{1}\Sigma^{[\alpha_{2},\,% \beta_{2}]}\,\cdots\,\Sigma^{[\alpha_{m},\,\beta_{m}]}\,p_{m},

where each $p_{i}\in\Sigma^{*}$ is a fixed string and $\Sigma^{[\alpha,\beta]}:=\{w\in\Sigma^{*}:\alpha\leq|w|\leq\beta\}$ is the set of strings whose lengths lie between $\alpha$ and $\beta$ . Thus, every gapped pattern denotes a regular language and can be expressed as a classical REGEX. Matching such patterns, including dictionary variants in which a finite set of gapped patterns is matched against a text, has been studied extensively; see, e.g., [69, 34, 11, 44, 46] and the survey [55]. Particularly relevant from a fine-grained perspective is the work of Amir et al. [4] on dictionary matching with one gap. In the uniformly bounded case, a dictionary $\mathcal{D}=\{G_{1},G_{2},\ldots,G_{n}\}$ consists of patterns of the form $G_{i}=p^{i}_{1}\,\Sigma^{[\alpha,\,\beta]}\,p^{i}_{2}$ with common bounds $\alpha,\beta$ . The task is to report their occurrences in an input text $w$ . Under the 3SUM conjecture [38, 72, 52], for suitable dictionaries, they proved a lower bound of $\Omega(|w|(\beta-\alpha)^{1-o(1)}+\mathit{op})$ where $\mathit{op}$ is the output size [4, Thm. 5 and Table 2]. Complementing this, they also gave an online reporting algorithm whose running time depends on structural parameters of dictionaries, in particular the degeneracy of the associated bipartite graph [4, Thm. 9].

3 Technical Overview of Theorem 7

We provide an overview of our algorithm for Theorem 7, which finds a decomposition $w=w_{A}\,w_{B}\,w_{C}\,w_{B}\,w_{D}$ with $w_{\xi}\in\mathbb{L}\left(\xi\right)$ for $\xi\in\{A,B,C,D\}$ . The following figure, Figure 1, summarizes the overall structure.

Figure 1: Overview of the algorithm for Theorem 7.

Remark.

The complete proofs and the full algorithmic details are given in the full version [53]. In this technical overview, we use the subscript $\mathrm{F}$ to refer to section numbers in the full version: for instance, $\S 10_{\mathrm{F}}$ means Section 10 of the full version. Thus, unless explicitly stated otherwise, section references with this subscript refer to the full version rather than to the present conference version.

To streamline our algorithm, we first normalize the input $w$ and expressions so that $\epsilon\not\in\mathbb{L}\left(D\right)$ and the alphabet is binary $\Sigma=\{0,1\}$ in Section 4_F. Then, we can assume $w_{D}\neq\epsilon$ . In Section 5_F, we reduce the ABCBD problem to two subproblems: the XYYZ problem (Section 6_F) and the branching ABCBD problem (Sections 7_F–12_F). In the former problem, we consider the case $w_{C}=\epsilon$ , i.e., $w=w_{A}\,w_{B}\ w_{B}\,w_{D}$ . In the latter problem, we consider the case where two suffixes $w_{C}\,w_{B}\,w_{D}$ and $w_{D}$ satisfy a branching condition; that is, their first letters are distinct. To show that this decomposition covers all cases, we rely on the closure properties of REGEX and the equivalence with nondeterministic finite automata (NFAs), as detailed in Section 5.2_F.

The key structure of the former (XYYZ) problem (our $X\,Y^{\alpha}\,Z$ problem with $\alpha=2$ , Section 6_F) is that, since $w_{C}=\epsilon$ , two occurrences of $w_{B}$ appear consecutively in $w$ as $w=\ldots w_{B}\,w_{B}\ldots$ . We crucially exploit the periodicity of $w$ induced by this immediate repetition $w_{B}w_{B}$ . We use Crochemore’s maximal local power enumeration [19, Sec. 9.2][18] (Section 6.1_F), in combination with the periodic properties of REGEX (Section 6.3_F). This part also yields Theorem 9.

To solve the latter (branching ABCBD) problem (Sections 7_F–12_F), we work with the suffix tree of $w$ , $\mathsf{ST}_{w}$ , or simply $\mathsf{ST}$ (see Section 2_F for the definition). Each leaf $\ell$ has an index $i_{\ell}$ of $w$ and corresponds to the suffix $w[i_{\ell}\,{\!\>..\!\>}\,|w|]$ ( $w=w[1]\,w[2]\,\ldots,w[|w|]$ .) Each inner node $v$ represents the substring given by the path-label from the root. For each $v$ , we maintain the set $\mathscr{I}_{v}$ of all indices $i_{\ell}$ of leaves $\ell$ in the subtree rooted at $v$ . We note that our suffix tree $\mathsf{ST}$ is binary because $\Sigma=\{0,1\}$ .

The key property of the problem is the branching condition. It means that the two paths from the root to $\ell_{w_{B}w_{C}w_{B}w_{D}}$ and to $\ell_{w_{B}w_{D}}$ branch at the node $v$ corresponding to $w_{B}$ (as illustrated in the figure below). Using this property, it suffices to consider the following task:

$(\clubsuit)$ : For each node $v$ , find a pair of suffixes branching at $v$ that induces a feasible decomposition.

We can illustrate our task $(\clubsuit)$ as follows using a suffix tree:

Let $\mathscr{H}_{v}:=\mathscr{I}_{u}$ , where $u$ is a child of $v$ maximizing the size $|\mathscr{I}_{u}|$ , and define $\mathscr{L}_{v}:=\mathscr{I}_{v}\setminus\mathscr{H}_{v}$ . We employ a classical small-to-large (or heavy-light decomposition) strategy: for each $i\in\mathscr{L}_{v}$ we determine whether there exists $j\in\mathscr{H}_{v}$ such that the pair $(i,j)$ induces a feasible decomposition. Since $\sum_{v:\text{node}}|\mathscr{L}_{v}|=O(|w|\log|w|)$ , the remaining task of $(\clubsuit)$ is to find such an index $j\in\mathscr{H}_{v}$ in $O(\log|w|)$ time for each $i\in\mathscr{L}_{v}$ . We then split the task $(\clubsuit)$ into the two cases Right- $B$ and Left- $B$ in Section 7_F.

In Right- $B$ , for each $i\in\mathscr{L}_{v}$ , we consider the case $i<j$ : i.e., the shorter suffix $w_{B}w_{D}$ starts at $j$ . Namely, we search for $j\in\mathscr{H}_{v}$ such that $w[j{\!\>..\!\>}|w|]=w_{B}w_{D}$ , illustrated as follows:

(\clubsuit_{R})\quad w=\underbrace{w[1{\!\>..\!\>}i)}_{w_{A}}\,\underbrace{w[i% {\!\>..\!\>}i+|w_{B}|)}_{w_{B}}\,\underbrace{w[i+|w_{B}|{\!\>..\!\>}j)}_{w_{C}% }\,\underbrace{w[j{\!\>..\!\>}j+|w_{B}|)}_{w_{B}}\,\underbrace{w[j+|w_{B}|{\!% \>..\!\>}|w|]}_{w_{D}}.

In Left- $B$ , we consider the case $j<i$ where $j$ is the starting position of the longer suffix $w_{B}\,w_{C}\,w_{B}\,w_{D}$ . We search for $j\in\mathscr{H}_{v}$ such that $w[j{\!\>..\!\>}|w|]=w_{B}w_{C}w_{B}w_{D}$ , illustrated as follows:

(\clubsuit_{L})\quad w=\underbrace{w[1{\!\>..\!\>}j)}_{w_{A}}\,\underbrace{w[j% {\!\>..\!\>}j+|w_{B}|)}_{w_{B}}\,\underbrace{w[j+|w_{B}|{\!\>..\!\>}i)}_{w_{C}% }\,\underbrace{w[i{\!\>..\!\>}i+|w_{B}|)}_{w_{B}}\,\underbrace{w[i+|w_{B}|{\!% \>..\!\>}|w|]}_{w_{D}}.

To handle both cases, we use the same high-level approach: traverse $\mathsf{ST}$ bottom-up and maintain the sets $\mathscr{H}_{v}$ using suitable data structures. Since the concrete algorithms and data structures differ between the two cases, we present them separately.

Right- $𝑩$ Case (Sections 8_F and 9_F)

Let $v$ be a node of $\mathsf{ST}$ and $w_{B}$ be the string represented by $v$ . Let $i\in\mathscr{L}_{v}$ , where $w[i{\!\>..\!\>}|w|]$ corresponds to $w_{B}w_{C}w_{B}w_{D}$ . We assume $w[1{\!\>..\!\>}i)\in\mathbb{L}\left(A\right)$ and $w_{B}\in\mathbb{L}\left(B\right)$ because otherwise there is no feasible solution. Our task $(\clubsuit_{R})$ is to find an index $j\in\mathscr{H}_{v}$ such that $w[j{\!\>..\!\>}|w|]$ corresponds to $w_{B}w_{D}$ . To treat the constraint $w_{C}\in\mathbb{L}\left(C\right)$ , we manage $\mathscr{H}_{v}$ using a data structure that answers whether there is an index $j\in\mathscr{H}_{v}$ with $i<j$ such that $w[i+|w_{B}|\,{\!\>..\!\>}\,j)\in\mathbb{L}\left(C\right)$ . We call this structure RightEnumerator (Section 9_F).

However, this is not yet sufficient, as we must also enforce the constraint $w_{D}\in\mathbb{L}\left(D\right)$ . Crucially, whether a fixed index $j$ satisfies this constraint depends on the current node $v$ . This is because the substring corresponding to $w_{D}$ begins at $j+|w_{B}|$ , and this starting position shifts as the length $|w_{B}|$ varies with $v$ . Consequently, we must handle the constraints for both $C$ and $D$ simultaneously. To address this, we partition $\mathcal{H}_{v}$ into subsets such that all indices in the same subset share the same validity regarding $D$ (Section 8_F). Leveraging the fact that REGEX admits a finite transition monoid (see Section 2_F for definition), we can ensure that we need to maintain only a constant number of subsets. By maintaining a separate instance of RightEnumerator for each subset and merging them using a disjoint set union data structure, we can resolve the issue and handle this case.

A simple way of constructing RightEnumerator is to use a segment tree, where each node is equipped with the set of elements of transition monoids (Section 9_F). This yields an $O(|w|\log^{3}|w|)$ -time algorithm. In our algorithm, employing a factorization forest (see Section 2_F for definition), we further eliminate one logarithmic factor and achieve $O(|w|\log^{2}|w|)$ time.

Left- $𝑩$ Case (Sections 10_F–12_F)

Let $v$ be a node of $\mathsf{ST}$ and $w_{B}$ be the substring represented by $v$ . Let $i\in\mathscr{L}_{v}$ , where $w[i{\!\>..\!\>}|w|]$ corresponds to $w_{B}w_{D}$ . We assume $w_{B}\in\mathbb{L}\left(B\right)$ and $w_{D}\in\mathbb{L}\left(D\right)$ because otherwise there is no feasible solution. Our task $(\clubsuit_{L})$ is to find an index $j\in\mathscr{H}_{v}$ with $j<i$ such that $w[j{\!\>..\!\>}|w|]$ corresponds to $w_{B}w_{C}w_{B}w_{D}$ . Moreover, we can handle the constraint for $A$ simply by managing only indices $j\in\mathscr{H}_{v}$ with $w[1{\!\>..\!\>}j)\in\mathbb{L}\left(A\right)$ (recall that, unlike the Right- $B$ case, it is independent of $v$ ). The remaining task is to find $j$ satisfying $j+|w_{B}|<i$ and $w[j+|w_{B}|\,{\!\>..\!\>}\,i)\in\mathbb{L}\left(C\right)$ . We treat it as a data structure problem (Section 10.2_F). We note that RightEnumerator is insufficient for our purpose, since the constraint $j+|w_{B}|<i$ depends on $|w_{B}|$ , which varies with the current node $v$ .

To address the problem, we consider the following two subcases separately:

\text{{near-\boldmath$j$:}}\nobreak\ \nobreak\ \text{$j+|w_{B}|\leq i<j+2|w_{B% }|$},\qquad\text{{far-\boldmath$j$:}}\nobreak\ \nobreak\ \text{$j+2|w_{B}|\leq i% $}.

In the near- $j$ case (Section 12_F), we derive a periodicity for $w_{B}$ because, for any two indices $j,j^{\prime}$ in the near- $j$ case, the substrings $w[j\,{\!\>..\!\>}\,j+|w_{B}|)$ and $w[j^{\prime}\,{\!\>..\!\>}\,j^{\prime}+|w_{B}|)$ overlap. With the periodicity inherent to REGEX, we can efficiently solve the near- $j$ case in $O(\log|w|)$ time. On the other hand, in the far- $j$ case, the index $j$ is “sufficiently far” from $i$ . Technically, the condition $j+2|w_{B}|\leq i$ implies that the distance between $j+|w_{B}|$ and $i$ is at least $|w_{B}|$ ; we use this margin for the design of our data structure.

To solve the far- $j$ case, we adopt the following strategy. We first build a data structure AuxiliaryEnumerator (Section 11_F), which maintains intervals $[j{\!\>..\!\>}k)$ as the item $[j,\,k)$ while ensuring $j+|w_{B}|\leq k$ . Given $i$ , it answers whether there is an interval $[j,k)$ such that $w[j+|w_{B}|\,{\!\>..\!\>}\,i)\in\mathbb{L}\left(C\right)$ and $k\leq i$ . For the condition $j+2|w_{B}|\leq i$ , it suffices to ensure $k\leq j+2|w_{B}|$ holds at any moment. The issue is that as we traverse $\mathsf{ST}$ , the node $v$ changes (thus, $|w_{B}|$ decreases), so the condition $k\leq j+2|w_{B}|$ will be violated. To resolve this issue, when the violation occurs (the margin $k-(j+|w_{B}|)$ becomes at least $|w_{B}|$ ), we “re-insert” the new interval $[j,\,k^{\prime})$ to the data structure, where $k^{\prime}:=j+|w_{B}|$ . The total overhead cost is $O(\log|w|)$ time because “re-insertion” happens only after $|w_{B}|$ is halved; this is ensured by the “far- $j$ ” condition.

The remaining task is to construct AuxiliaryEnumerator (Section 11_F). This is similar to RightEnumerator, but requires additional mechanisms to quickly answer queries of $w[j+|w_{B}|\,{\!\>..\!\>}\,i)\in\mathbb{L}\left(C\right)$ , which depends on the current $v$ (and thus, $w_{B}$ ). We adopt a lazy update strategy for this purpose. As in RightEnumerator, using the segment tree leads to the time complexity $O(|w|\log^{3}|w|)$ , which can be accelerated to $O(|w|\log^{2}|w|)$ using the factorization forest.

4 Hardness

We show our three hardness results in this section:

1.

The REWB matching problem is W[2]-hard (Theorem 3) in Section 4.1.
2.

Under a hypothesis for the triangle detection problem, 2-use 2-REWB matching problem cannot be solved in almost linear time (Theorem 4) in Section 4.2.
3.

Under SETH (more technically, k-OV Hypothesis), $k$ -REWB matching problem cannot be solved in $O(n^{2k-\epsilon})$ time (Theorem 5) in Section 4.3.

Remark.

Due to space limitations, we omit proofs in this conference version. The full version contains the complete proofs of all statements in this section.

In Section 4.1 and 4.2, we use the following notation. Let $G=(\mathcal{V},\mathcal{E})$ be an undirected graph without self-loops where $\mathcal{V}$ is a set of vertices and $\mathcal{E}$ is a set of edges. For our constructions, we assume that each vertex $v$ is uniquely encoded as a binary string of length $O(\log n)$ ; that is, $v\in(0+1)^{+}$ , where, for a REWB $R$ , we write $R^{+}:=RR^{*}$ for one or more repetitions of $R$ .

For readability, in this Section 4, we sometimes write $[E]_{x}$ instead of $(E)_{x}$ .

4.1 W[2]-hardness for REWB: Reduction from $𝒌$ -Dominating Set Problem

We prove Theorem 3 by reduction from the following $k$ -dominating set problem ( $k\text{-}\textbf{DSP}$ ).

$k\text{-}\textbf{DSP}$ : $k$ -Dominating Set Problem

Input: An undirected graph $G=(\mathcal{V},\mathcal{E})$ and an integer $k$ .

Task: Deciding if there is a $k$ -dominating set: i.e., a subset $\mathcal{D}\subseteq V$ of size exactly $k$ such that:

\forall v\in\mathcal{V}.\>((v\in\mathcal{D})\lor(\exists u\in\mathcal{D}.(u,v)% \in\mathcal{E})).

We note that, since $G$ is undirected, $(u,v)\in E\iff(v,u)\in E$ . It is known that this problem is $\mathbf{W[2]}$ -complete [27] when parameterized by $k$ . Furthermore, the following is known.

Lemma 10 ([73][22, Thm 14.42]).

Assuming SETH, there is no algorithm running in $O(n^{k-\epsilon})$ time solving $k\text{-}\textbf{DSP}$ for any $\epsilon>0$ .

Our main task is to provide the following reduction from $k\text{-}\textbf{DSP}$ to $k$ -REWB matching problem.

Lemma 11 (Reduction from $k\text{-}\textbf{DSP}$ to $k$ -REWB Matching Problem).

Let $k\geq 1$ be an integer. In time $O(k)$ , we can construct a $k$ -REWB $\Psi_{k}$ of length $O(k)$ satisfying the following.

Let $G=(\mathcal{V},\mathcal{E})$ be an undirected graph. There exists a string $\widetilde{G}$ such that the following holds:

\widetilde{G}\in\mathbb{L}\left(\Psi_{k}\right)\iff\text{ there is a $k$-% Dominating Set $\mathcal{D}$ of $G$}.

In particular, we can construct the string $\widetilde{G}$ in $O((n+m)\log n)$ time with $|\widetilde{G}|=O((n+m)\log n)$ where $n:=|\mathcal{V}|$ is the number of vertices and $m:=|\mathcal{E}|$ is the number of edges.

Remark.

We refer the reader to the full version for the proof of this reduction lemma.

From this lemma, we obtain the following W[2]-hardness result. See 3

Proof.

We give an FPT-reduction from $k\text{-}\textbf{DSP}$ .

Given an instance $(G,k)$ , we output the matching instance $(\Psi_{k},\widetilde{G})$ , where $\Psi_{k}$ is constructed in $O(k)$ time and $\widetilde{G}$ is constructed in $O((n+m)\log n)$ time as in Lemma 11, such that $\widetilde{G}\in\mathbb{L}\left(\Psi_{k}\right)$ iff $G$ has a $k$ -dominating set of size exactly $k$ .

Moreover, the parameter of the output instance satisfies $|\Psi_{k}|=O(k)$ . Hence, this is an FPT-reduction, and the claim follows since $k\text{-}\textbf{DSP}$ is W[2]-hard. $\hfill\blacktriangleleft$ We note that this result is stronger than W[2]-hardness parameterized by the number of variables $k$ , since the number of variables $k$ is at most the expression length $|\Psi_{k}|$ .

4.2 Hardness for $2$ -use $2$ -REWB: Reduction from Triangle Detection Problem

We prove Theorem 4 by reduction from the following triangle detection problem.

Triangle Detection Problem

Input: An undirected graph $G=(\mathcal{V},\mathcal{E})$ with $n:=|\mathcal{V}|$ vertices and $m:=|\mathcal{E}|$ edges.

Task: Deciding whether $G$ contains a triangle, that is, whether there is a set of three distinct vertices $\{a,b,c\}$ with $(a,b),(b,c),(c,a)\in\mathcal{E}$ .

The following is conjectured about the triangle detection problem.

Hypothesis (No-Almost-Linear-Time Hypothesis [1, Conjecture 3]).

There is a constant $\delta>0$ , such that in the Word RAM model with words of $O(\log n)$ bits, any algorithm requires $m^{1+\delta-o(1)}$ time in expectation to detect whether a graph with $m$ edges contains a triangle.

In this section, our main task is to give the following reduction from the triangle detection problem to the $2$ -use $2$ -REWB matching problem.

Lemma 12 (Reduction from Triangle Detection Problem to $2$ -use $2$ -REWB Matching Problem).

There exists a fixed $2$ -use $2$ -REWB expression $\Psi$ that solves the triangle detection problem in the following sense:

Let $G=(\mathcal{V},\mathcal{E})$ be an undirected graph with $n$ vertices and $m$ edges. There exists a string $\widehat{G}$ such that the following holds:

\widehat{G}\in\mathbb{L}\left(\Psi\right)\iff\text{ there is a triangle in $G$}.

In particular, we can construct the string $\widehat{G}$ in $O(m\log n)$ time, and the size of $\widehat{G}$ is $|\widehat{G}|=O(m\log n)$ .

Remark.

We refer the reader to the full version for the proof of this reduction lemma.

We can show our hardness result from Lemma 12. While the proof follows a standard reduction argument, we provide the details below for completeness.

Theorem 4. [Restated, see original statement.]

Proof.

Assume the No-Almost-Linear-Time Hypothesis holds. Let $\delta_{\Delta}>0$ be the constant specified in the hypothesis; that is, any algorithm requires time $m^{1+\delta_{\Delta}-o(1)}$ .

Let $\Psi$ be the fixed $2$ -use $2$ -REWB expression from Lemma 12. For every graph $G$ with $n$ vertices and $m$ edges, we can construct $\widehat{G}$ such that $\widehat{G}\in\mathbb{L}(\Psi)\iff G\text{ has a triangle}$ .

Set $\gamma:=\delta_{\Delta}/2$ . It suffices to rule out algorithms running in time $O(|w|^{1+\gamma})$ , since any $|w|^{1+\gamma-o(1)}$ -time algorithm also runs in time $O(|w|^{1+\gamma})$ . Suppose, for contradiction, that there is an algorithm $\mathcal{A}$ for $\Psi$ running in time $O(|w|^{1+\gamma})$ .

We construct a triangle detection algorithm $\mathcal{T}$ as follows: Given $G$ , remove isolated vertices so that $n\leq 2m$ , construct $\widehat{G}$ , and run the matching algorithm $\mathcal{A}$ on $\widehat{G}$ . The construction of $\widehat{G}$ takes $O(m\log n)$ time and yields $|\widehat{G}|=O(m\log n)$ . Since $n\leq 2m$ , we have $|\widehat{G}|=O(m\log m)$ . Running $\mathcal{A}$ on $\widehat{G}$ takes the following time $T_{\mathcal{A}}(\widehat{G})$ :

T_{\mathcal{A}}(\widehat{G})=O\left((m\log m)^{1+\gamma}\right)=O\left(m^{1+% \gamma}(\log m)^{1+\gamma}\right).

Since $(\log m)^{1+\gamma}=m^{o(1)}$ , the total running time of $\mathcal{T}$ is:

T_{\mathcal{T}}(G)=O(m\log m)+m^{1+\gamma+o(1)}=m^{1+\gamma+o(1)}.

Substituting $\gamma=\delta_{\Delta}/2$ , we get:

T_{\mathcal{T}}(G)=m^{1+\frac{\delta_{\Delta}}{2}+o(1)}.

For sufficiently large $m$ , $1+\frac{\delta_{\Delta}}{2}+o(1)<1+\delta_{\Delta}-o(1)$ . Thus, $\mathcal{T}$ solves the triangle detection problem strictly faster than the hypothesized lower bound $m^{1+\delta_{\Delta}-o(1)}$ , which is a contradiction. Thus, no $O(|w|^{1+\gamma})$ -time algorithm for $\Psi$ exists. In particular, no $|w|^{1+\gamma-o(1)}$ -time algorithm exists. Taking $\delta:=\gamma$ proves the theorem. $\hfill\blacktriangleleft$

4.3 Hardness from $𝒌$ -Orthogonal Vectors Problem Hypothesis

We now prove our $O(n^{2q-\epsilon})$ -time hardness for the $q$ -REWB matching problem, where $n$ denotes the length of input strings, under the $k$ -orthogonal vectors ( $k$ -OV) hypothesis [28, 84], and hence under SETH. To use $k$ for the $k$ -OV and its hypothesis, we use “ $q$ ” to denote the number of variables of REWB in this section.

Let $v_{1},v_{2},\ldots,v_{k}\in\{0,1\}^{d}$ be $d$ -dimensional 0-1 vectors over the ring $\mathbb{Z}$ . The $k$ inner-product is defined as follows:

\mathbf{IP}_{k}(v_{1},v_{2},\ldots,v_{k}):=\sum^{d}_{i=1}\left(\ \prod^{k}_{j=% 1}v_{j}[i]\,\right).

These vectors are $k$ -orthogonal if $\mathbf{IP}_{k}(v_{1},v_{2},\ldots,v_{k})=0$ . In our construction, we use the following equivalent condition: $\displaystyle\bigwedge^{d}_{i=1}\bigvee^{k}_{j=1}(v_{j}[i]=0)$ .

We now consider the $k$ -OV and the $k$ -OV Hypothesis.

$\textbf{\boldmath$k$-OV}_{N,d}$ Problem

Input: $k$ sets $A_{1},\ldots,A_{k}\subseteq\{0,1\}^{d}$ where each set $A_{i}$ has size $|A_{i}|=N$ .

Task: Deciding if the following holds:

\exists v_{1}\in A_{1}.\,\exists\>v_{2}\in A_{2}.\>\ldots\>\exists v_{k}\in A_% {k}.\ \mathbf{IP}_{k}(v_{1},v_{2},\ldots,v_{k})=0.

Hypothesis ( $𝒌$ -OV Hypothesis [28, Hypothesis 2],[84, Hypothesis 4]).

Let $k\geq 2$ be an integer. For any $\epsilon>0$ and every dimension function $d(N)=\omega(\log N)$ (e.g., $d(N)=\lceil\log^{2}N\rceil$ ), $\textbf{\boldmath$k$-OV}_{\!N,\,d(N)}$ cannot be solved in $O(N^{k-\epsilon})$ time.

Remark.

It is known that the $k$ -OV hypothesis is weaker than SETH; indeed, SETH implies the $k$ -OV hypothesis [84, Theorem 3.1] [28, 83].

We provide an efficient reduction from $2k\text{-}\textbf{OV}$ problem to $k$ -REWB matching problem.

Lemma 13.

Let $k\geq 1$ be an integer. There exists a (fixed) $k$ -REWB $\Psi_{k}$ that solves $2k\text{-}\textbf{OV}$ in the following sense: Let $N\geq 1$ be an integer and $A_{1},\ldots,A_{2k}\subseteq\{0,1\}^{d}$ be an instance of $2k$ -OV with $|A_{1}|=\cdots=|A_{2k}|=N$ . There is a string $\mathcal{S}(A_{1},\ldots,A_{2k})$ such that
$\mathcal{S}(A_{1},\ldots,A_{2k})\in\mathbb{L}\left(\Psi_{k}\right)\iff\exists v% _{1}\in A_{1}.\exists v_{2}\in A_{2}.\ \cdots.\exists v_{2k}\in A_{2k}.\ % \mathbf{IP}_{2k}(v_{1},v_{2},\ldots,v_{2k})=0.$

In particular, we can construct $\mathcal{S}(A_{1},\ldots,A_{2k})$ in $O(k\cdot N\cdot d^{2})$ time.

Before providing the proof of this lemma (shown in Section 4.3.1), we here prove Theorem 5 using this lemma. While the proof follows a standard reduction argument, we provide the details below for completeness.

Theorem (Reformulation of Theorem 5).

The $q$ -REWB matching problem cannot be solved in $O(|w|^{2q-\epsilon})$ time for any $\epsilon>0$ under the $𝐤$ -OV hypothesis.

Proof.

We proceed by contradiction. Suppose there exists an algorithm $\mathcal{A}$ solving the problem in time $O(|w|^{2q-\epsilon})$ for some constant $\epsilon>0$ . We construct an efficient algorithm to solve $2q\text{-}\textbf{OV}_{\!N,\,d}$ as follows:

1.

Given an instance of $2q\text{-}\textbf{OV}_{\!N,\,d}$ consisting of $2q$ sets $\{A_{1},A_{2},\ldots,A_{2q}\}$ of $N$ vectors in $\{0,1\}^{d}$ , we first transform it into a string $\mathcal{S}:=\mathcal{S}(A_{1},\ldots,A_{2q})$ by our reduction. By the assumption, this reduction takes $T(N)=O(Nd^{2})$ time, and $n_{\mathcal{S}}:=|\mathcal{S}|\leq c\cdot Nd^{2}$ for some constant $c$ depending on $q$ .
2.

Next, we run the algorithm $\mathcal{A}$ on $\mathcal{S}$ . The running time is

$T_{\mathcal{A}}(n_{\mathcal{S}})=O(n_{\mathcal{S}}^{2q-\epsilon})=O\bigl((Nd^{% 2})^{2q-\epsilon}\bigr).$

Fix the dimension function $d(N):=\lceil\,(\log N)^{2}\,\rceil$ . Since $d(N)=\omega(\log N)$ holds, the $k$ -OV Hypothesis (with $k=2q$ ) applies also to $2q\text{-}\textbf{OV}_{\!N,\,d(N)}$ .

By Step 2 we obtain a $2q\text{-}\textbf{OV}$ algorithm with running time:

T_{\text{total}}(N)=O(Nd^{2})+O\big((Nd^{2})^{2q-\epsilon}\big)=O(Nd^{2})+O% \big(N^{2q-\epsilon}\cdot d^{4q-2\epsilon}\big)\quad\text{where}\ d=d(N).

Since $d=\lceil\,(\log N)^{2}\,\rceil$ , we have $d^{4q-2\epsilon}\leq\bigl((\log{N})^{2}+1\bigr)^{4q-2\epsilon}=(\log{N})^{O(1)% }=N^{o(1)}$ . Thus for any $\delta>0$ and sufficiently large $N$ ,

d^{4q-2\varepsilon}\leq N^{\delta}.

Choose $\delta=\epsilon/2$ . Then

T_{\text{total}}(N)=O(N^{1+o(1)})+O(N^{(2q-\epsilon)+(\epsilon/2)})=O(N^{2q-% \epsilon/2}),

contradicting the $k$ -OV Hypothesis with $k=2q$ . $\hfill\blacktriangleleft$

4.3.1 Proof of Lemma 13

To explain our idea, we first give a reduction from $2\text{-}\textbf{OV}$ to $1$ -REWB matching problem. The reduction can be easily extended to a reduction from $2k\text{-}\textbf{OV}$ to $k$ -REWB.

Lemma 14 (Reduction for $k=1$ ).

There exists a (fixed) $1$ -REWB $\Psi_{1}$ that solves $2\text{-}\textbf{OV}$ in the following sense: Let $N\geq 1$ be an integer and $A_{1},A_{2}\subseteq\{0,1\}^{d}$ be an instance of $2$ -OV with $|A_{1}|=|A_{2}|=N$ . There is a string $\mathcal{S}(A_{1},A_{2})$ such that

\mathcal{S}(A_{1},A_{2})\in\mathbb{L}\left(\Psi_{1}\right)\iff\exists v_{1}\in A% _{1}.\exists v_{2}\in A_{2}.\ \mathbf{IP}(v_{1},v_{2})=0.

In particular, we can construct $\mathcal{S}(A_{1},A_{2})$ in $O(N\cdot d^{2})$ time.

Proof.

We note that the proof presented here can be viewed as the REWB-version of a similar result and construction for 1-turn bounded-height ( $\leq d$ ) pushdown automata [45, Theorem 4].

Let $A_{1}=\{v_{1},v_{2},\ldots,v_{N}\}$ and $A_{2}=\{u_{1},u_{2},\ldots,u_{N}\}$ . We set $\Sigma:=\{0,1,\#,@,\natural\}$ and define the following string $\mathcal{I}$ , which serves as the arena for our construction:

\mathcal{I}:=\#\,\overleftarrow{v_{1}}\,\#\,\overleftarrow{v_{2}}\,\#\ \cdots% \#\,\overleftarrow{v_{N}}\,\#@\#\,u_{1}\,\#\,u_{2}\,\#\cdots\#\,u_{N}\,\#\,\natural

where $\overleftarrow{v}$ means the reversed version of $v$ : i.e., $\overleftarrow{11001}=10011$ . It should be noted that $|\mathcal{I}|=O(d\cdot N)$ .

A key idea of our reduction is to represent a pair of vectors $(v_{i},u_{j})$ with $1\leq i,j\leq N$ by a single substring of $\mathcal{I}$ . A substring $\pi$ of $\mathcal{I}$ represents $(v_{i},u_{j})$ if the following holds:

\mathcal{I}=\cdots\#\,\overleftarrow{v_{i}}\ \overbrace{\#\cdots\#\,@\,\#% \cdots\#}^{\text{\large$\pi$}}\ u_{j}\,\#\cdots\natural.

More formally, let $\pi=\pi(i,j)$ be the factor (substring) of $\mathcal{I}$ that starts right after the occurrence of $\overleftarrow{v_{i}}$ and ends right before the occurrence of $u_{j}$ . It is explicitly given by:

\pi(i,j):=(\#\overleftarrow{v_{i+1}}\#\cdots\#\overleftarrow{v_{N}})\,\#@\#\,(% u_{1}\#\cdots\#u_{j-1}\#)

If $i=N$ , the left part is empty; if $j=1$ , the right part is empty.

For example, if $A_{1}=\{v_{1}=011,v_{2}=001\}$ and $A_{2}=\{u_{1}=101,u_{2}=100\}$ , then our string $\mathcal{I}$ takes the following form:

\mathcal{I}=\#\,110\,\#\,100\,\#\,@\,\#\,101\,\#\,100\,\#\natural.

In this setting, the substring $\pi=\#100\#@\#101\#$ represents $(v_{1},u_{2})$ because it starts right after $\overleftarrow{v_{1}}$ and ends right before $u_{2}$ in $\mathcal{I}$ . Below we write $\tilde{\mathcal{I}}$ to denote $\mathcal{I}$ for this example.

We define the following building block expression $\psi$ and $\varphi_{v},\varphi_{u}$ where

$\blacksquare$

we use $\psi$ by applying it to a copy of $\mathcal{I}$ to nondeterministically select and represent vectors $v_{*}$ from $A_{1}$ and $u_{*}$ from $A_{2}$ ; and
$\blacksquare$

we use $\varphi_{v}$ (resp. $\varphi_{u}$ ) by applying it to a copy of $\mathcal{I}$ to check $v_{*}[\ell]=0$ (resp. $u_{*}[\ell]=0$ ) for each index $\ell\in[1{\!\>..\!\>}d]$ .

We first define our expression $\psi$ as follows:

\psi:=\Gamma^{*}\,(\#\,\Gamma^{*}\,@\,\Gamma^{*}\#)_{x}\,\Gamma^{*}\,\natural

where $\Gamma:=(0+1+\#)$ is the REGEX. We note that $\Gamma$ cannot consume the symbols $@$ and $\natural$ .

We apply $\psi$ to $\mathcal{I}$ to nondeterministically select vectors $v_{*}$ from $A_{1}$ and $u_{*}$ from $A_{2}$ . For our example $A_{1}=\{v_{1}=011,v_{2}=001\}$ and $A_{2}=\{u_{1}=101,u_{2}=100\}$ , applying $\psi$ to $\tilde{\mathcal{I}}$ can generate the following match, in which $v_{*}=v_{1}$ and $u_{*}=u_{2}$ are selected:

\overbrace{\#110}^{\Gamma^{*}}\ \overbrace{\#100\,\#@\#\,101\#}^{(\#\Gamma^{*}% @\Gamma^{*}\#)_{x}}\ \overbrace{100\#\natural}^{\Gamma^{*}\natural}\quad\text{% where $x$ has $\#\,100\,\#@\#\,101\,\#$.}

Another run can select $v_{*}=v_{2}$ and $u_{*}=u_{1}$ as follows:

\overbrace{\#\,110\,\#\,100}^{\Gamma^{*}}\ \overbrace{\#@\#}^{(\#\Gamma^{*}@% \Gamma^{*}\#)_{x}}\ \overbrace{101\,\#\,100\#\natural}^{\Gamma^{*}\natural}.% \quad\text{where $x$ has $\#\,@\,\#$}.

By the above observation, the following is clear.

Proposition 15.

Applying $\psi$ to $\mathcal{I}$ , it completely consumes $\mathcal{I}$ and saves a substring into the variable $x$ , which represents $(v_{i},u_{j})$ for some $1\leq i,j\leq N$ . Moreover, any pair $(v_{i},u_{j})$ can be captured and represented via $x$ by applying $\psi$ to $\mathcal{I}$ .

Next we define our expressions $\varphi_{v}$ and $\varphi_{u}$ as follows:

\varphi_{v}:=\Gamma^{*}\#\mathcal{B}^{*}\,(0\,\mathord{\backslash x}\,\mathcal% {B})_{x}\,\mathcal{B}^{*}\#\Gamma^{*}\,\natural,\qquad\varphi_{u}:=\Gamma^{*}% \#\mathcal{B}^{*}\,(\mathcal{B}\,\mathord{\backslash x}\,0)_{x}\,\mathcal{B}^{% *}\#\Gamma^{*}\,\natural.

where $\mathcal{B}:=(0+1)$ .

The former $\varphi_{v}$ requires $v_{*}[\ell]=0$ and the latter $\varphi_{u}$ requires $u_{*}[\ell]=0$ for some index $\ell\in[1{\!\>..\!\>}d]$ . For example, applying $\varphi_{v}$ to another copy of $\tilde{\mathcal{I}}$ under $x=\#100\#@\#101\#$ , it works as follows:

\overbrace{\phantom{01}}^{\Gamma^{*}}\ \overbrace{\#}^{\#}\ \overbrace{11}^{% \mathcal{B}^{*}}\ \overbrace{0\,\#100\,\#@\#\,101\#\,1}^{(0\,\mathord{% \backslash x}\,\mathcal{B})_{x}}\ \overbrace{00}^{\mathcal{B}^{*}}\ \overbrace% {\#}^{\#}\ \overbrace{\,\natural\,}^{\Gamma^{*}\natural}.

This application also updates $x$ as follows:

x=\#100\,\#@\#\,101\#\leadsto 0\,\#100\,\#@\#\,101\#\,1\nobreak\ .

Since one application of $\varphi_{v}$ and $\varphi_{u}$ extends $x$ by one symbol on each side, we can check $\displaystyle\bigwedge^{d}_{\ell=1}(v_{*}[\ell]=0\lor u_{*}[\ell]=0)$ by repeatedly applying the expression $(\varphi_{v}+\varphi_{u})$ . For example, applying $\varphi_{u}$ to another copy of $\tilde{\mathcal{I}}$ under the updated $x$ , it checks if $u_{*}[2]=0$ and updates $x$ as follows:
$\overbrace{\phantom{01}}^{\Gamma^{*}}\ \overbrace{\#}^{\#}\ \overbrace{1}^{% \mathcal{B}^{*}}\ \overbrace{1\,0\#100\,\#@\#\,101\#1\,0}^{(\mathcal{B}\,% \mathord{\backslash x}\,0)_{x}}\ \overbrace{0}^{\mathcal{B}^{*}}\ \overbrace{% \#}^{\#}\ \overbrace{\,\natural\,}^{\Gamma^{*}\natural},\quad x=0\#100\,\#@\#% \,101\#1\leadsto 1\,0\#100\,\#@\#\,101\#1\,0\nobreak\ .$

By the above observation, the following is clear.

Proposition 16.

Assume the content of $x$ represents $v_{i}[\ell]$ and $u_{j}[\ell]$ for some $1\leq\ell\leq d$ . Then, applying $(\varphi_{v}+\varphi_{u})$ to $\mathcal{I}$ , the following holds: if the application succeeds, then $v_{i}[\ell]\cdot u_{j}[\ell]=0$ and $x$ is updated to represent $v_{i}[\ell+1]$ and $u_{j}[\ell+1]$ (when $\ell<d$ ).

In summary, we employ the following gadgets:

\mathcal{S}(A_{1},A_{2}):=\overbrace{\mathcal{I}\,\mathcal{I}\,\cdots\,% \mathcal{I}}^{\text{$(1+d)${-}copies}},\qquad\Psi_{1}:=\psi\ (\varphi_{v}+% \varphi_{u})^{*}

It should be noted that the expression $\Psi_{1}$ does not depend on the instance $A_{1}$ and $A_{2}$ ; this $\Psi_{1}$ can be used for any $2\text{-}\textbf{OV}$ instances.

By the above argument, it is clear that $\mathcal{S}(A_{1},A_{2})\in\mathbb{L}\left(\Psi_{1}\right)$ iff there are orthogonal vectors in $A_{1}$ and $A_{2}$ . We note that $|\mathcal{S}(A_{1},A_{2})|=O(N\cdot d^{2})$ because $|\mathcal{I}|=O(N\cdot d)$ , and $\mathcal{S}(A_{1},A_{2})$ can be constructed in $O(N\cdot d^{2})$ time. $\hfill\blacktriangleleft$

We can generalize the above reduction to one from $2k\text{-}\textbf{OV}$ to $k$ -REWB.

Lemma 13. [Restated, see original statement.]

In particular, we can construct $\mathcal{S}(A_{1},\ldots,A_{2k})$ in $O(k\cdot N\cdot d^{2})$ time.

Proof.

We extend the construction for Lemma 14 to the case $k\geq 2$ . We represent $2\cdot k$ vectors using $k$ variables $x_{1},x_{2},\ldots,x_{k}$ . We assume the following representation:

\begin{array}[]{l}A_{1}=\{v^{1}_{1},\ldots,v^{1}_{N}\},\ A_{2}=\{u^{1}_{1},% \ldots,u^{1}_{N}\},\\[5.0pt] A_{3}=\{v^{2}_{1},\ldots,v^{2}_{N}\},\ A_{4}=\{u^{2}_{1},\ldots,u^{2}_{N}\},\\ \nobreak\ \vdots\\ A_{2k-1}=\{v^{k}_{1},\ldots,v^{k}_{N}\},\ A_{2k}=\{u^{k}_{1},\ldots,u^{k}_{N}% \}.\end{array}

We change the definition of $\mathcal{I}$ as follows:

\mathcal{I}:=\mathcal{I}_{1}\ \mathcal{I}_{2}\ \cdots\mathcal{I}_{k}\ ,

where

\mathcal{I}_{r}:=\#\,\overleftarrow{v^{r}_{1}}\,\#\cdots\,\#\overleftarrow{v^{% r}_{N}}\,\#@\#\,u^{r}_{1}\,\#\cdots\#u^{r}_{N}\#\,\natural\ .

For example, if $k=2$ ,

\mathcal{I}=\#\overleftarrow{v^{1}_{1}}\#\cdots\#\overleftarrow{v^{1}_{N}}\,\#% @\#\,u^{1}_{1}\#\cdots\#u^{1}_{N}\#\natural\ \ \#\overleftarrow{v^{2}_{1}}\#% \cdots\#\overleftarrow{v^{2}_{N}}\#@\#u^{2}_{1}\#\cdots\#u^{2}_{N}\#\natural\ .

We use the variable $x_{r}$ ( $1\leq r\leq k$ ) to represent $(v^{r}_{i},u^{r}_{j})$ with $1\leq i,j\leq N$ . For example, if $k=2$ , we use $x_{1}$ and $x_{2}$ as follows:

\#\overleftarrow{v^{1}_{1}}\#\overleftarrow{v^{1}_{2}}\overbrace{\#\cdots\#% \overleftarrow{v^{1}_{N}}\,\#@\#}^{x_{1}}u^{1}_{1}\#u^{1}_{2}\#\cdots\#u^{1}_{% N}\#\natural\ \ \#\overleftarrow{v^{2}_{1}}\#\overleftarrow{v^{2}_{2}}% \overbrace{\#\cdots\#\overleftarrow{v^{2}_{N}}\,\#@\#u^{2}_{1}\#}^{x_{2}}u^{2}% _{2}\#\cdots\#u^{2}_{N}\#\natural

To accommodate multiple variables, we below modify $\psi$ , $\varphi_{v}$ , and $\varphi_{u}$ in Lemma 14 (the case $k=1$ ).

We first define $\psi$ to nondeterministically select vectors from $A_{1},A_{2},\ldots,A_{2k}$ and bind them into $x_{1},\ldots x_{k}$ as follows:

\psi:=\psi_{1}\psi_{2}\cdots\psi_{k},\qquad\text{ where }\ \psi_{r}:=\Gamma^{*% }\,(\#\Gamma^{*}@\Gamma^{*}\#)_{x_{r}}\,\Gamma^{*}\natural,\quad\Gamma:=(0+1+% \#).

As with $\psi$ in Lemma 14, the following holds for $\psi$ .

Proposition 17.

Applying $\psi$ to $\mathcal{I}$ , it completely consumes $\mathcal{I}$ and saves substrings to the variables $x_{1},x_{2},\ldots,x_{k}$ where each $x_{r}$ represents $(v^{r}_{i},u^{r}_{j})$ for some $1\leq i,j\leq N$ . Moreover, for each $1\leq r\leq k$ , any pair $(v^{r}_{i},u^{r}_{j})$ can be captured and represented via $x_{r}$ by applying $\psi$ to $\mathcal{I}$ .

We next define $\varphi_{r}$ to check $v_{i}^{r}[\ell]=0$ or $u_{j}^{r}[\ell]=0$ ( $1\leq\ell\leq d$ ) as follows:

\varphi_{r}:=\varphi_{r}^{1}\ \varphi_{r}^{2}\ \cdots\ \varphi_{r}^{k}\qquad(1% \leq r\leq k),

where

\varphi_{r}^{s}:=\begin{cases}\varphi_{s,\top}&(r\neq s),\\ \varphi_{s,v}+\varphi_{s,u}&(r=s),\end{cases}\qquad\begin{array}[]{lcl}\varphi% _{s,v}&:=&\Gamma^{*}\#\mathcal{B}^{*}\ (0\,\mathord{\backslash x_{s}}\,% \mathcal{B})_{x_{s}}\ \mathcal{B}^{*}\#\Gamma^{*}\,\natural\ ,\\ \varphi_{s,u}&:=&\Gamma^{*}\#\mathcal{B}^{*}\ (\mathcal{B}\,\mathord{% \backslash x_{s}}\,0)_{x_{s}}\ \mathcal{B}^{*}\#\Gamma^{*}\,\natural\ ,\\ \varphi_{s,\top}&:=&\Gamma^{*}\#\mathcal{B}^{*}\ (\mathcal{B}\mathord{% \backslash x_{s}}\,\mathcal{B})_{x_{s}}\ \mathcal{B}^{*}\#\Gamma^{*}\,\natural% ,\end{array}\quad\mathcal{B}=(0+1).

Proposition 18.

Assume that, for an index $\ell\in[1..d]$ , every $x_{r}$ represents $v^{r}_{i}[\ell]$ and $u^{r}_{j}[\ell]$ for $1\leq r\leq k$ . If the application of $\varphi_{r}$ to $\mathcal{I}$ succeeds and consumes $\mathcal{I}$ , then either $v^{r}_{i}[\ell]=0$ or $u^{r}_{j}[\ell]=0$ holds. Moreover, every $x_{r}$ is updated to represent $v^{r}_{i}[\ell+1]$ and $u^{r}_{j}[\ell+1]$ (when $\ell<d$ ).

Conversely, if $v^{r}_{i}[\ell]=0$ or $u^{r}_{j}[\ell]=0$ holds, then applying $\varphi_{r}$ to $\mathcal{I}$ must succeed.

Using $\varphi_{1},\ldots,\varphi_{k}$ , we further define $\varphi$ to check the $2k$ -orthogonality condition:

\varphi:=\varphi_{1}+\varphi_{2}+\cdots+\varphi_{k}.

We observe that applying $\varphi$ to $\mathcal{I}$ succeeds iff $\bigl(\prod^{k}_{r=1}(v^{r}_{i}[\ell]\cdot u^{r}_{j}[\ell])\bigr)=0$ when each $x_{r}$ represents $v_{i}^{r}[\ell]$ and $u_{j}^{r}[\ell]$ . Then, we finally define $\mathcal{S}(A_{1},A_{2},\ldots,A_{2k-1},A_{2k})$ and $\Psi_{k}$ as follows:

\mathcal{S}(A_{1},A_{2},\ldots,A_{2k-1},A_{2k}):=\overbrace{\,\mathcal{I}\ % \mathcal{I}\ \ldots\ \mathcal{I}\,}^{(1+d)\text{-copies}},\qquad\Psi_{k}:=\psi% \ \varphi^{*}\nobreak\ .

From the above properties, we observe the following, which completes our proof:

	$\displaystyle\mathcal{S}(A_{1},A_{2},\ldots,A_{2k-1},A_{2k})\in\mathbb{L}\left% (\Psi_{k}\right)\iff\text{the $2k$-{OV}{} instance contains}$
	$\displaystyle\text{$2k$-orthogonal vectors}.\$

$\hfill\blacktriangleleft$

References

[1] Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In FOCS 2014, pages 434–443. IEEE Computer Society, 2014. doi:10.1109/FOCS.2014.53.
[2] Alfred V. Aho. Algorithms for finding patterns in strings. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, pages 255–300. MIT Press, 1990. doi:10.1016/B978-0-444-88071-0.50010-2.
[3] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986. URL: https://www.worldcat.org/oclc/12285707.
[4] Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, and B. Riva Shalom. Mind the gap! online dictionary matching with one gap. Algorithmica, 81:2123–2157, 2019. doi:10.1007/s00453-018-0526-2.
[5] Dana Angluin. Finding patterns common to a set of strings (extended abstract). In STOC 1979, pages 130–141. ACM, 1979. doi:10.1145/800135.804406.
[6] Dana Angluin. Finding patterns common to a set of strings. JCSS, 21(1):46–62, 1980. doi:10.1016/0022-0000(80)90041-0.
[7] Arturs Backurs and Piotr Indyk. Which Regular Expression Patterns Are Hard to Match? In FOCS 2016, pages 457–466. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.56.
[8] Aurèle Barrière and Clément Pit-Claudel. Linear matching of JavaScript regular expressions. Proc. ACM Program. Lang., 8(PLDI), June 2024. doi:10.1145/3656431.
[9] Martin Berglund and Brink van der Merwe. Re-examining regular expressions with backreferences. Theor. Comput. Sci., 940(Part):66–80, 2023. doi:10.1016/j.tcs.2022.10.041.
[10] Philip Bille and Inge Li Gørtz. Sparse regular expression matching. In SODA 2024, pages 3354–3375. SIAM, 2024. doi:10.1137/1.9781611977912.120.
[11] Philip Bille, Inge Li Gørtz, Hjalte Wedel Vildhøj, and David Kofoed Wind. String matching with variable length gaps. Theor. Comput. Sci., 443:25–34, 2012. doi:10.1016/j.tcs.2012.03.029.
[12] Karl Bringmann, Allan Grønlund, Marvin Künnemann, and Kasper Green Larsen. The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. In ITCS 2024, volume 287 of LIPIcs, pages 22:1–22:25. Schloss Dagstuhl, 2024. doi:10.4230/LIPIcs.ITCS.2024.22.
[13] Aria Buckles. simple-markdown: inlinecode: Fix ReDoS & improve escape semantics (commit 89797fe). GitHub commit, 2019. URL: https://github.com/ariabuckles/simple-markdown/commit/89797fe.
[14] Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. Alternation. J. ACM, 28(1):114–133, January 1981. doi:10.1145/322234.322243.
[15] Agnishom Chattopadhyay, Angela W. Li, and Konstantinos Mamouras. Verified and efficient matching of regular expressions with lookaround. In CPP 2025, pages 198–213. ACM, 2025. doi:10.1145/3703595.3705884.
[16] Russ Cox. Regular expression matching can be simple and fast. https://swtch.com/˜rsc/regexp/regexp1.html, January 2007.
[17] Russ Cox. Regular expression matching in the wild. https://swtch.com/~rsc/regexp/regexp3.html, March 2010.
[18] Max Crochemore. An optimal algorithm for computing the repetitions in a word. Inf. Process. Lett., 12(5):244–250, 1981. doi:10.1016/0020-0190(81)90024-7.
[19] Maxime Crochemore, Christophe Hancart, and Thierry Lecroq. Algorithms on Strings. Cambridge University Press, 2007. doi:10.1017/CBO9780511546853.
[20] Scott A. Crosby. Denial of service through regular expressions. Presentation at the 12th USENIX Security Symposium, 2003. URL: https://www.usenix.org/conference/12th-usenix-security-symposium/denial-service-through-regular-expressions.
[21] Scott A. Crosby and Dan S. Wallach. Denial of service via algorithmic complexity attacks. In USENIX Security 03. USENIX Association, 2003. URL: https://www.usenix.org/conference/12th-usenix-security-symposium/denial-service-algorithmic-complexity-attacks.
[22] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
[23] Robert Dąbrowski and Wojciech Plandowski. On word equations in one variable. Algorithmica, 60(4):819–828, August 2011. doi:10.1007/s00453-009-9375-3.
[24] Robert Dąbrowski and Wojtek Plandowski. Solving two-variable word equations (extended abstract). In ICALP 2004, volume 3142 of Lecture Notes in Computer Science, pages 408–419. Springer, 2004. doi:10.1007/978-3-540-27836-8_36.
[25] James C. Davis, Francisco Servant, and Dongyoon Lee. Using selective memoization to defeat regular expression denial of service (ReDoS). In S&P 2021, pages 1–17, 2021. doi:10.1109/SP40001.2021.00032.
[26] Volker Diekert, Claudio Gutierrez, and Christian Hagenah. The existential theory of equations with rational constraints in free groups is PSPACE-complete. Inf. Comput., 202(2):105–140, 2005. doi:10.1016/j.ic.2005.04.002.
[27] Rod G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness i: Basic results. SIAM Journal on Computing, 24(4):873–921, 1995. doi:10.1137/S0097539792228228.
[28] Lech Duraj, Marvin Künnemann, and Adam Polak. Tight conditional lower bounds for longest common increasing subsequence. Algorithmica, 81(10):3968–3992, 2019. doi:10.1007/S00453-018-0485-7.
[29] Andrzej Ehrenfeucht and Grzegorz Rozenberg. Finding a homomorphism between two words in NP-complete. Inf. Process. Lett., 9(2):86–88, 1979. doi:10.1016/0020-0190(79)90135-2.
[30] Henning Fernau, Florin Manea, Robert Mercaş, and Markus L. Schmid. Pattern Matching with Variables: Fast Algorithms and New Hardness Results. In STACS 2015, volume 30 of LIPIcs, pages 302–315. Schloss Dagstuhl, 2015. doi:10.4230/LIPIcs.STACS.2015.302.
[31] Henning Fernau, Florin Manea, Robert Mercaş, and Markus L. Schmid. Pattern matching with variables: Efficient algorithms and complexity results. ACM Trans. Comput. Theory, 12(1), February 2020. doi:10.1145/3369935.
[32] Henning Fernau and Markus L. Schmid. Pattern matching with variables: A multivariate complexity analysis. Inf. Comput., 242:287–305, 2015. doi:10.1016/j.ic.2015.03.006.
[33] Henning Fernau, Markus L. Schmid, and Yngve Villanger. On the parameterised complexity of string morphism problems. Theory of Computing Systems, 59(1):24–51, 2016. doi:10.1007/s00224-015-9635-3.
[34] Kimmo Fredriksson and Szymon Grabowski. Efficient algorithms for pattern matching with general gaps, character classes, and transposition invariance. Information Retrieval, 11:335–357, 2008. doi:10.1007/s10791-008-9054-z.
[35] Dominik D. Freydenberger and Markus L. Schmid. Deterministic regular expressions with back-references. J. Comput. Syst. Sci., 105:1–39, 2019. doi:10.1016/j.jcss.2019.04.001.
[36] Jeffrey Friedl. Mastering Regular Expressions. O’Reilly, 2006. URL: https://www.oreilly.com/library/view/mastering-regular-expressions/0596528124/.
[37] Hiroya Fujinami and Ichiro Hasuo. Efficient matching with memoization for regexes with look-around and atomic grouping. In ESOP 2024, volume 14577 of Lecture Notes in Computer Science, pages 90–118. Springer, 2024. doi:10.1007/978-3-031-57267-8_4.
[38] Anka Gajentaan and Mark H. Overmars. On a class of ${O}(n^{2})$ problems in computational geometry. Computational Geometry, 5(3):165–185, 1995. doi:10.1016/0925-7721(95)00022-2.
[39] Jan Goyvaerts. Runaway Regular Expressions: Catastrophic Backtracking. https://www.regular-expressions.info/catastrophic.html, 2021.
[40] Jan Goyvaerts. Atomic grouping. https://www.regular-expressions.info/atomic.html, 2025.
[41] Jan Goyvaerts. Lookahead and Lookbehind Zero-Length Assertions. https://www.regular-expressions.info/lookaround.html, 2025.
[42] Jan Goyvaerts. Repetition with star and plus. https://www.regular-expressions.info/repeat.html, 2025.
[43] John Graham-Cumming. Details of the Cloudflare outage on July 2, 2019. Cloudflare Blog. Archived at https://web.archive.org/web/20190712160002/https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/, July 2019. URL: https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/.
[44] Tuukka Haapasalo, Panu Silvasti, Seppo Sippu, and Eljas Soisalon-Soininen. Online dictionary matching with variable-length gaps. In Experimental Algorithms, volume 6630 of Lecture Notes in Computer Science, pages 76–87. Springer, 2011. doi:10.1007/978-3-642-20662-7_7.
[45] Jakob Cetti Hansen, Adam Husted Kjelstrøm, and Andreas Pavlogiannis. Tight bounds for reachability problems on one-counter and pushdown systems. Inf. Process. Lett., 171:106135, 2021. doi:10.1016/j.ipl.2021.106135.
[46] Wing-Kai Hon, Tak-Wah Lam, Rahul Shah, Sharma V. Thankachan, Hing-Fung Ting, and Yilin Yang. Dictionary matching with a bounded gap in pattern or in text. Algorithmica, 80:698–713, 2018. doi:10.1007/s00453-017-0288-2.
[47] Oscar H. Ibarra, Ting-Chuen Pong, and Stephen M. Sohn. A note on parsing pattern languages. Pattern Recognit. Lett., 16(2):179–182, 1995. doi:10.1016/0167-8655(94)00091-G.
[48] Artur Jeż. One-variable word equations in linear time. Algorithmica, 74(1):1–48, 2016. doi:10.1007/s00453-014-9931-3.
[49] Artur Jeż. Recompression: A simple and powerful technique for word equations. J. ACM, 63(1), February 2016. doi:10.1145/2743014.
[50] Artur Jeż. Solving Word Equations (And Other Unification Problems) by Recompression. In CSL 2020, volume 152 of LIPIcs, pages 3:1–3:17. Schloss Dagstuhl, 2020. doi:10.4230/LIPIcs.CSL.2020.3.
[51] Tao Jiang, Efim Kinber, Arto Salomaa, Kai Salomaa, and Sheng Yu. Pattern languages with and without erasing. International Journal of Computer Mathematics, 50(3–4):147–163, 1994. doi:10.1080/00207169408804252.
[52] Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In SODA 2016, pages 1272–1287. SIAM, 2016. doi:10.1137/1.9781611974331.ch89.
[53] Soh Kumabe and Yuya Uezato. On the complexity of the matching problem of regular expressions with backreferences, 2026. arXiv:2605.07289.
[54] Richard E. Ladner, Richard J. Lipton, and Larry J. Stockmeyer. Alternating pushdown and stack automata. SIAM Journal on Computing, 13(1):135–155, 1984. doi:10.1137/0213010.
[55] Avivit Levy and B. Riva Shalom. A comparative study of dictionary matching with gaps: Limitations, techniques and challenges. Algorithmica, 84:590–638, 2022. doi:10.1007/s00453-021-00851-6.
[56] Konstantinos Mamouras and Agnishom Chattopadhyay. Efficient matching of regular expressions with lookaround assertions. Proc. ACM Program. Lang., 8(POPL), January 2024. doi:10.1145/3632934.
[57] Alexandru Mateescu and Arto Salomaa. Aspects of classical language theory. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages, Volume 1: Word, Language, Grammar, pages 175–251. Springer, 1997. doi:10.1007/978-3-642-59136-5_4.
[58] MITRE. CWE-1333: Inefficient Regular Expression Complexity. https://cwe.mitre.org/data/definitions/1333.html, 2021. CWE version 4.17. Page last updated: 2025-04-03.
[59] National Vulnerability Database (NVD). CVE-2017-16114, 2017. URL: https://nvd.nist.gov/vuln/detail/CVE-2017-16114.
[60] National Vulnerability Database (NVD). CVE-2019-25103, 2019. URL: https://nvd.nist.gov/vuln/detail/CVE-2019-25103.
[61] National Vulnerability Database (NVD). CVE-2021-21240. https://nvd.nist.gov/vuln/detail/CVE-2021-21240, 2021. GitHub Advisory: https://github.com/advisories/GHSA-93xj-8mrv-444m.
[62] National Vulnerability Database (NVD). CVE-2023-39663. https://nvd.nist.gov/vuln/detail/CVE-2023-39663, 2023. GitHub Advisory: {https://github.com/advisories/GHSA-v638-q856-grg8}.
[63] National Vulnerability Database (NVD). CVE-2023-6159. https://nvd.nist.gov/vuln/detail/cve-2023-6159, 2023. GitLab Security Release: {https://about.gitlab.com/releases/2024/01/25/critical-security-release-gitlab-16-8-1-released/}.
[64] National Vulnerability Database (NVD). CVE-2024-26142. https://nvd.nist.gov/vuln/detail/CVE-2024-26142, 2024. GitHub Advisory: https://github.com/advisories/GHSA-jjhx-jhvp-74wq.
[65] National Vulnerability Database (NVD). CVE-2024-28865. https://nvd.nist.gov/vuln/detail/CVE-2024-28865, 2024. GitHub Advisory: https://github.com/advisories/GHSA-wj85-w4f4-xh8h.
[66] National Vulnerability Database (NVD). CVE-2025-25200. https://nvd.nist.gov/vuln/detail/CVE-2025-25200, 2025. GitHub Advisory: https://github.com/advisories/GHSA-593f-38f6-jp5m.
[67] National Vulnerability Database (NVD). CVE-2025-29907. https://nvd.nist.gov/vuln/detail/CVE-2025-29907, 2025. GitHub Advisory: https://github.com/advisories/GHSA-w532-jxjh-hjhj.
[68] National Vulnerability Database (NVD). CVE-2025-5197. https://nvd.nist.gov/vuln/detail/CVE-2025-5197, 2025. GitHub Advisory: https://github.com/advisories/GHSA-9356-575x-2w9m.
[69] Gonzalo Navarro and Mathieu Raffinot. Fast and simple character classes and bounded gaps pattern matching, with applications to protein searching. Journal of Computational Biology, 10(6):903–923, 2003. doi:10.1089/106652703322756140.
[70] Taisei Nogami and Tachio Terauchi. Efficient matching of some fundamental regular expressions with backreferences. In MFCS 2025, volume 345 of LIPIcs, pages 81:1–81:19. Schloss Dagstuhl, 2025. doi:10.4230/LIPIcs.MFCS.2025.81.
[71] Taisei Nogami and Tachio Terauchi. Hardness of regular expression matching with extensions, 2026. doi:10.48550/arXiv.2601.03020.
[72] Mihai Pătraşcu. Towards polynomial lower bounds for dynamic problems. In STOC 2010, pages 603–610. ACM, 2010. doi:10.1145/1806689.1806772.
[73] Mihai Pătraşcu and Ryan Williams. On the possibility of faster SAT algorithms. In SODA 2010, pages 1065–1075. SIAM, 2010. doi:10.1137/1.9781611973075.86.
[74] Wojciech Plandowski. Satisfiability of word equations with constants is in PSPACE. J. ACM, 51(3):483–496, May 2004. doi:10.1145/990308.990312.
[75] Markus L. Schmid. Regular expressions with backreferences: Polynomial-time matching techniques. J. Autom. Lang. Comb., 29(2-4):321–357, 2024. doi:10.25596/jalc-2024-321.
[76] Klaus U. Schulz. Makanin’s algorithm for word equations - two improvements and a generalization. In Word Equations and Related Topics, First International Workshop, IWWERT ’90, volume 572 of Lecture Notes in Computer Science, pages 85–150. Springer, 1990. doi:10.1007/3-540-55124-7_4.
[77] Takeshi Shinohara. Polynomial time inference of extended regular pattern languages. In RIMS Symposia on Software Science and Engineering, pages 115–127. Springer, 1983. doi:10.1007/3-540-11980-9_19.
[78] Stack Exchange. Outage Postmortem - July 20, 2016. Stack Exchange Network Status Blog. Archived at https://web.archive.org/web/20180801005940/http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016, July 2016. URL: http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016.
[79] Frank Stephan, Ryo Yoshinaka, and Thomas Zeugmann. On the parameterised complexity of learning patterns. In Computer and Information Sciences II, pages 277–281. Springer, 2012. doi:10.1007/978-1-4471-2155-8_35.
[80] Ken Thompson. Programming techniques: Regular expression search algorithm. Commun. ACM, 11(6):419–422, June 1968. doi:10.1145/363347.363387.
[81] Yuya Uezato. Regular Expressions with Backreferences and Lookaheads Capture NLOG. In ICALP 2024, volume 297 of LIPIcs, pages 155:1–155:20. Schloss Dagstuhl, 2024. doi:10.4230/LIPIcs.ICALP.2024.155.
[82] UziTech. marked: fix inline code regex (commit 3271b8b). GitHub commit, 2018. URL: https://github.com/markedjs/marked/commit/3271b8b.
[83] Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357–365, 2005. doi:10.1016/j.tcs.2005.09.023.
[84] Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians (ICM 2018). WORLD SCIENTIFIC, 2019. doi:10.1142/9789813272880_0188.

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

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Background.

Complexity of REGEX matching problems

Definition 1 (Syntax of REGEX).

From REGEX to REWB

Definition 2 (Syntax of REWB).

Classification of REWB

Known algorithmic results for REWB matching

1.1 Our Contribution

1.1.1 Hardness Results for the REWB Matching Problem

Theorem 3.

Theorem 4.

Theorem 5.

1.1.2 Algorithmic Results

Theorem 6.

Theorem 7.

Theorem 8.

Remark: Uniformity.

Theorem 9.

1.1.3 Open Problems

1.1.4 Organization

2 Related Work

2.1 ReDoS

2.2 Hardness of Regular Language Matching Problems

On REGEX

On REWB

2.3 Algorithms for Regular Expression Matching Problems

On REWB

Pattern Language and Word Equation

On REGEX with Lookaround

Gapped Patterns

3 Technical Overview of Theorem 7

Remark.

Right-𝑩 Case (Sections 8F and 9F)

Left-𝑩 Case (Sections 10F–12F)

4 Hardness

Remark.

4.1 W[2]-hardness for REWB: Reduction from 𝒌-Dominating Set Problem

Lemma 10 ([73][22, Thm 14.42]).

Lemma 11 (Reduction from k⁢-DSP to k-REWB Matching Problem).

Remark.

Proof.

4.2 Hardness for 𝟐-use 𝟐-REWB: Reduction from Triangle Detection Problem

Hypothesis (No-Almost-Linear-Time Hypothesis [1, Conjecture 3]).

Lemma 12 (Reduction from Triangle Detection Problem to 2-use 2-REWB Matching Problem).

Remark.

Theorem 4. [Restated, see original statement.]

Proof.

4.3 Hardness from 𝒌-Orthogonal Vectors Problem Hypothesis

Hypothesis (𝒌-OV Hypothesis [28, Hypothesis 2],[84, Hypothesis 4]).

Remark.

Lemma 13.

Theorem (Reformulation of Theorem 5).

Proof.

4.3.1 Proof of Lemma 13

Lemma 14 (Reduction for k=1).

Proof.

Proposition 15.

Proposition 16.

Lemma 13. [Restated, see original statement.]

Proof.

Proposition 17.

Proposition 18.

References

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

Right- $𝑩$ Case (Sections 8_F and 9_F)

Left- $𝑩$ Case (Sections 10_F–12_F)

4.1 W[2]-hardness for REWB: Reduction from $𝒌$ -Dominating Set Problem

Lemma 11 (Reduction from $k\text{-}\textbf{DSP}$ to $k$ -REWB Matching Problem).

4.2 Hardness for $2$ -use $2$ -REWB: Reduction from Triangle Detection Problem

Lemma 12 (Reduction from Triangle Detection Problem to $2$ -use $2$ -REWB Matching Problem).

4.3 Hardness from $𝒌$ -Orthogonal Vectors Problem Hypothesis

Hypothesis ( $𝒌$ -OV Hypothesis [28, Hypothesis 2],[84, Hypothesis 4]).

Lemma 14 (Reduction for $k=1$ ).