論文の概要: On the Complexity of the Matching Problem of Regular Expressions with Backreferences
- arxiv url: http://arxiv.org/abs/2605.07289v1
- Date: Fri, 08 May 2026 05:55:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-11 19:43:38.838129
- Title: On the Complexity of the Matching Problem of Regular Expressions with Backreferences
- Title（参考訳）: 逆参照を伴う正規表現のマッチング問題の複雑さについて
- Abstract要約: 本稿では,バックREWBを用いた正規表現における文字列マッチング問題の微妙な複雑さについて検討する。
我々は最近,野上と寺内による$O(n2k-)$-timeを改良した$O(n2k-)$-time for $1$use REWBsを提案する(MFCS,2025)。
本アルゴリズムは, 接尾辞木, 遷移モノイドEX, 分解林データ構造, 弦の周期性など, 様々な手法を用いている。
- 参考スコア（独自算出の注目度）: 0.7305019142196582
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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 are provably efficient, running in (near-)linear time in the length of the input string? For classical regular expressions (REGEX), Thompson's construction yields a linear-time algorithm. However, practical engines support powerful features such as backreferences, which strictly extend the expressive power of REGEX but unfortunately increase 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. On the hardness side, we show that the string matching problem for $k$-REWBs cannot be solved in $O(n^{2k-ε})$ time for any $ε> 0$ under SETH. We also prove that this problem is \textbf{W[2]}-hard when parameterized by the length of the REWB expression, strengthening the previous \textbf{W[1]}-hardness. 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, which significantly improves upon the recent $O(n^2)$-time algorithm by Nogami and Terauchi (MFCS, 2025). Our algorithm employs several techniques including suffix trees, transition monoids of REGEXes, factorization forest data structures, and periodicity of strings.
- Abstract（参考訳）: ReDoSはアルゴリズムの複雑性攻撃としてよく知られており、敵は悪意のある文字列を正規表現マッチングエンジンに供給し、システムの計算資源を消費することを目的としている。
Stack Overflow(2016年)とCloudflare(2019年)の大規模な機能停止が示すように、マッチするエンジンの二次的な動作でさえ、攻撃の成功に活用されている。
これらのインシデントは基本的な問題である: 入力文字列の長さで(ほぼ)線形時間で実行しながら、証明可能な効率のよいマッチングエンジンを構築することは可能か?
古典正規表現(REGEX)では、トンプソンの構成は線形時間アルゴリズムを生成する。
しかし、実用的なエンジンはバックリフレクションのような強力な機能をサポートしており、REGEXの表現力は厳密に拡張するが、残念ながらReDoS攻撃のリスクは増大する。
本稿では,バックリフレクション付き正規表現における文字列マッチング問題(REWB)の微細な複雑さについて検討する。
具体的には、$r$-use $k$-REWBsを考える。
硬度側では、$k$-REWBsの文字列マッチング問題は、SETHの下での任意の$ε> 0$に対して$O(n^{2k-ε})$ timeでは解決できない。
また、REWB式の長さによってパラメータ化された場合、この問題は \textbf{W[2]}-hard であることが証明され、以前の \textbf{W[1]}-hardness が強化された。
さらに、この問題を$n^{1+o(1)}$時間で解けない$$2$2$-REWBsでは、その時点で三角形検出問題が解けなければ解けないことを示す。
アルゴリズム面では、1ドル使用のREWBに対して$O(n \log^2 n)$-timeアルゴリズムが提案され、野上と寺内による最近の$O(n^2)$-timeアルゴリズム(MFCS, 2025)により大幅に改善されている。
本アルゴリズムは,接尾辞木,REGEXの遷移モノイド,分解森林データ構造,弦の周期性など,いくつかの手法を用いる。
関連論文リスト
- Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations [10.282294365033785]
適応性は、(おそらく無制限の)前処理時間による暗号解析時空間トレードオフにおいて、かなりの余分なパワーを提供することを示す。
本稿では,検索と決定の幅広い問題に対して,非適応的前処理アルゴリズムを解析できる新しいモデルを提案する。
論文 参考訳（メタデータ） (2025-05-01T22:17:11Z) - Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching [2.4167127333650202]
パターンマッチングにおけるハミング距離と、編集によるパターンマッチングにおける編集距離の2つを考える。
時間的複雑性は$tildeO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Mismatchesと$hatO(sqrtnk+sqrtn/mcdot k3.5)$ for Pattern Matching with Editsである。
論文 参考訳（メタデータ） (2024-10-09T12:05:26Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文 参考訳（メタデータ） (2023-10-23T18:26:00Z) - Longest Common Substring and Longest Palindromic Substring in
$\ ilde{\mathcal{O}}(\sqrt{n})$ Time [0.0]
LCS(Longest Common Substring)とLPS(Longest Palindromic Substring)は、コンピュータ科学における古典的な問題である。
計算回路モデルにおいて, LCS と LPS の双方に対する量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-03T19:27:57Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Fast and Efficient Matching Algorithm with Deadline Instances [6.969116920943907]
まず、$mathrmdeadline$の市場モデルを紹介します。
最適化された2つのアルゴリズム(textscFastGreedy と textscFastPostponedGreedy)を提示する。
同時に、我々のアルゴリズムは元の2つのアルゴリズムよりも高速に動作します。
論文 参考訳（メタデータ） (2023-05-15T05:21:20Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Near-Optimal Quantum Algorithms for String Problems [0.5736353542430439]
ほぼ最適なクエリ複雑度と時間複雑度を持つ基本文字列問題に対する量子アルゴリズムを提案する。
これらの問題には、Longest Common Substring、Lexicographically Minimal String Rotation、Longest Square Substringが含まれる。
我々の手法は、Longest Repeated Substring、Longest Lyndon Substring、Minimmal Suffixといった他の関連する文字列問題に自然に拡張する。
論文 参考訳（メタデータ） (2021-10-19T02:32:18Z) - Online Sub-Sampling for Reinforcement Learning with General Function
Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。
複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。
少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文 参考訳（メタデータ） (2021-06-14T07:36:25Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。