← 研踪 PaperTrailarXiv:2609.16914 · v2
Regular Expression Matching with Ordered Linear Backreferences
首次提交 2026-09-15 17:51
版本更新 2026-11-16 17:51
雷达观测 2026-11-17 17:11
摘要
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 and one or more references . The substring matched by the reference must match the same substring that was matched by the corresponding capturing group. We focus on a subclass, which we call ordered linear rewbs where the references and capturing groups occur only outside star and union operators. Furthermore, we require that all references to a capturing group occur before the next capturing group in the rewb. In full generality, rewb matching is NP-complete, but efficient solutions exist for various subclasses. For linear rewbs with one capturing group and references, Uezato~[CPM 2026] gave an time and space algorithm, where is the length of the regular expression and is the length of the string . For the special case of , Nogami and Terauchi~[MFCS 2025] gave an time and 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 for any assuming the orthogonal vector hypothesis. Our main result is a new improved algorithm that runs in time and uses space, and handles the more general case of ordered linear rewbs with multiple capturing groups.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-16 17:51 · 最新观测版本
Regular Expression Matching with Ordered Linear Backreferences
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 and one or more references . The substring matched by the reference must match the same substring that was matched by the corresponding capturing group. We focus on a subclass, which we call ordered linear rewbs where the references and capturing groups occur only outside star and union operators. Furthermore, we require that all references to a capturing group occur before the next capturing group in the rewb. In full generality, rewb matching is NP-complete, but efficient solutions exist for various subclasses. For linear rewbs with one capturing group and references, Uezato~[CPM 2026] gave an time and space algorithm, where is the length of the regular expression and is the length of the string . For the special case of , Nogami and Terauchi~[MFCS 2025] gave an time and 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 for any assuming the orthogonal vector hypothesis. Our main result is a new improved algorithm that runs in time and uses space, and handles the more general case of ordered linear rewbs with multiple capturing groups.
查看此版本解读 →查看此版本原文 ↗