Hardness of Regular Expression Matching with Extensions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908932332584960 |
|---|---|
| author | Nogami, Taisei Nakamura, Yoshiki Terauchi, Tachio |
| author_facet | Nogami, Taisei Nakamura, Yoshiki Terauchi, Tachio |
| contents | The regular expression matching problem asks whether a given regular expression of length $m$ matches a given string of length $n$. As is well known, the problem can be solved in $O(nm)$ time using Thompson's algorithm. Moreover, recent studies have shown that regular expression matching extended with a practical extension called lookaround can be solved in the same time complexity. In this work, we consider four well-known extensions to regular expressions called backreference, squaring, intersection and complement. We prove a number of novel time complexity lower bounds for regular expression matching with these extensions under the Orthogonal Vectors Conjecture (OVC), $k$-OVC, $k$-Clique Hypothesis, and Combinatorial $k$-Clique Hypothesis. Some highlights of our results include the fact that none of the matching problems with the extensions can be solved in $n^{2-\varepsilon} \mathrm{poly}(m)$ time for any constant $\varepsilon > 0$ (for backreference, even when restricted to one capturing group) under OVC, and that the problem with complement, also known as extended regular expression (ERE) matching, cannot be solved in time $n^{2-\varepsilon}\mathrm{tower}(o(\sqrt{m}))$ under OVC, $n^{ω-\varepsilon}\mathrm{tower}(o(\sqrt{m}))$ under the $k$-Clique Hypothesis (where $ω$ is the matrix multiplication exponent), and $n^{3-\varepsilon}\mathrm{tower}(o(\sqrt{m}))$ under the Combinatorial $k$-Clique Hypothesis, respectively. In particular, the latter two results show that the $O(n^3 m)$-time ERE matching algorithm introduced by Hopcroft and Ullman in 1979 and recently improved by Bille, Gørtz and Jessen to run in $O(n^ωm)$ time using fast matrix multiplication was already optimal in a sense, and shed light on why the theoretical computer science community has struggled to improve the time complexity of ERE matching with respect to $n$ and $m$ for more than 45 years. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_03020 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Hardness of Regular Expression Matching with Extensions Nogami, Taisei Nakamura, Yoshiki Terauchi, Tachio Computational Complexity Data Structures and Algorithms Formal Languages and Automata Theory The regular expression matching problem asks whether a given regular expression of length $m$ matches a given string of length $n$. As is well known, the problem can be solved in $O(nm)$ time using Thompson's algorithm. Moreover, recent studies have shown that regular expression matching extended with a practical extension called lookaround can be solved in the same time complexity. In this work, we consider four well-known extensions to regular expressions called backreference, squaring, intersection and complement. We prove a number of novel time complexity lower bounds for regular expression matching with these extensions under the Orthogonal Vectors Conjecture (OVC), $k$-OVC, $k$-Clique Hypothesis, and Combinatorial $k$-Clique Hypothesis. Some highlights of our results include the fact that none of the matching problems with the extensions can be solved in $n^{2-\varepsilon} \mathrm{poly}(m)$ time for any constant $\varepsilon > 0$ (for backreference, even when restricted to one capturing group) under OVC, and that the problem with complement, also known as extended regular expression (ERE) matching, cannot be solved in time $n^{2-\varepsilon}\mathrm{tower}(o(\sqrt{m}))$ under OVC, $n^{ω-\varepsilon}\mathrm{tower}(o(\sqrt{m}))$ under the $k$-Clique Hypothesis (where $ω$ is the matrix multiplication exponent), and $n^{3-\varepsilon}\mathrm{tower}(o(\sqrt{m}))$ under the Combinatorial $k$-Clique Hypothesis, respectively. In particular, the latter two results show that the $O(n^3 m)$-time ERE matching algorithm introduced by Hopcroft and Ullman in 1979 and recently improved by Bille, Gørtz and Jessen to run in $O(n^ωm)$ time using fast matrix multiplication was already optimal in a sense, and shed light on why the theoretical computer science community has struggled to improve the time complexity of ERE matching with respect to $n$ and $m$ for more than 45 years. |
| title | Hardness of Regular Expression Matching with Extensions |
| topic | Computational Complexity Data Structures and Algorithms Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2601.03020 |