Metraipolis › archive › dc_4bb027732bf1

Improved Regular Expression Matching with Simple Backreferences — arXiv:2609.16914

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.16914
License (as archived)
CC0-1.0
Archived
2026-10-15T21:59:08.320Z
SHA-256 of the archived text
da15a72aca132b8c37d6451459a74181a5a811b465fa13438af08fcfe36aa78a
Stable URL of this page
https://metraipolis.com/documento/dc_4bb027732bf1

How to cite

Improved Regular Expression Matching with Simple Backreferences — arXiv:2609.16914 — arXiv (en), https://arxiv.org/abs/2609.16914 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4bb027732bf1 (Metraipolis archive dc_4bb027732bf1, sha256 da15a72aca132b8c37d6451459a74181a5a811b465fa13438af08fcfe36aa78a)
BibTeX
@misc{dc4bb027732bf1,
  title = {Improved Regular Expression Matching with Simple Backreferences — arXiv:2609.16914},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.16914},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4bb027732bf1; sha256 da15a72aca132b8c37d6451459a74181a5a811b465fa13438af08fcfe36aa78a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.16914. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A regular expression with backreferences (rewb) specifies a set of strings formed by characters combined with concatenation, union, star operators, and backreferences. A backreference consists of a capturing group $(\cdot)_i$ and a reference $\backslash i$. The substring matched by the reference must match the substring matched by the corresponding capturing group. Given a rewb $R$ and a string $Q$, the rewb matching problem is to decide whether $Q$ is one of the strings specified by $R$. In full generality, rewb matching is NP-complete, but efficient solutions exist for various subclasses. In the paper, we focus on rewb containing a single capturing group and $k$ references. For this class, Uezato~[CPM 2026] gave an $O((k n^2 m^2)$ time and $O(n^2m^2)$ space algorithm, where $m$ is the length of the regular expression $R$ and $n$ is the length of the string $Q$. For the special case of $k=1$, Nogami and Terauchi~[MFCS 2025] gave an $O(n^2m^2)$ time and $O(n+ m^2)$ space algorithm. On the other hand, Nogami, Nakamura, and Terauchi~[arXiv 2026] gave a conditional lower bound, showing that we cannot solve the problem in $O(n^{2-\epsilon} \mathrm{poly}(m))$ for any $\epsilon > 0$ assuming the orthogonal vector hypothesis. Our main result is a new algorithm that runs in $O(n^2m)$ time and uses $O(nm)$ space. This improves the above results (by a factor of $km$ and $m$, respectively) and the former's space bound (by a factor of $nm$). We also show how to extend our algorithm to handle a slightly more general class of ordered and single-nested rewbs.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-16 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.16914 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T21:46:54.570Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).