Fugu-MT 論文翻訳(概要): Quantum Pattern Matching in Generalised Degenerate Strings

論文の概要: Quantum Pattern Matching in Generalised Degenerate Strings

arxiv url: http://arxiv.org/abs/2603.16297v1
Date: Tue, 17 Mar 2026 09:35:02 GMT
ステータス: 翻訳完了
システム内更新日: 2026-03-18 17:42:07.198747
Title: Quantum Pattern Matching in Generalised Degenerate Strings
Title（参考訳）: 一般化縮退文字列における量子パターンマッチング
Authors: Massimo Equi, Md Rabiul Islam Khan, Veli Mäkinen,
Abstract要約: 縮退文字列は文字の集合の列である。 GD文字列内のパターンの正確な一致を見つけることは、$O(mn+N)$ timeで実現できる。我々はこのアルゴリズムを量子計算モデルの下で動くように修正する。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: A degenerate string is a sequence of sets of characters. A generalized degenerate (GD) string extends this notion to the sequence of sets of strings, where strings of the same set are of equal length. Finding an exact match for a pattern string inside a GD string can be done in $O(mn+N)$ time (Ascone et al., WABI 2024), where $m$ is the pattern length, $n$ is the number of strings and $N$ the total length of strings constituting the GD string. We modify this algorithm to work under a quantum model of computation, achieving running time $\tilde{O}(\sqrt{mnN})$.
Abstract（参考訳）: 縮退文字列は文字の集合の列である。一般化退化(GD)弦は、この概念を、同じ集合の弦が等しい長さである文字列の集合の列に拡張する。 GD文字列内のパターン文字列の正確な一致を見つけるには、$O(mn+N)$ time (Ascone et al , WABI 2024) で、$m$はパターン長、$n$は文字列の数、$N$はGD文字列を構成する文字列の総長さである。このアルゴリズムは計算の量子モデルの下で動作し、実行時間$\tilde{O}(\sqrt{mnN})$を達成する。

関連論文リスト

Quantum Algorithm for the Multiple String Matching Problem [0.0]
我々は$m$文字列のシーケンスを$S$と表現し、それを辞書と呼ぶ。目的は、テキスト内の辞書から文字列のすべてのインスタンスを特定することである。我々は,$O(n+sqrtmLlog nlog n)$クエリ複雑性と$O(n+sqrtmLlog n)=O*(n+sqrtmL)$タイム複雑性を持つ量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-11-22T10:50:43Z)
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)
Efficient Semiring-Weighted Earley Parsing [71.77514972816347]
本稿では,様々なスピードアップを伴うEarey (1970) の文脈自由構文解析アルゴリズムの,推論システムという形での参照記述を提供する。私たちのプレゼンテーションには、Earey氏の$O(N3|GR|)$から、既知の最悪のランタイム改善が含まれています。半重み付き推論への一般化を扱い、Stolcke (1995)のような文法を前処理して推論サイクルを排除し、さらに文プレフィックスの重みを計算するStolckeの手法を一般化する。
論文参考訳（メタデータ） (2023-07-06T13:33:59Z)
Quantum Algorithms for the Shortest Common Superstring and Text Assembling Problems [11.048346250166073]
テキスト集合問題の2つのバージョンについて考察する。文字列のシーケンスは$s1,dots,sn$ of total length $L$ that is a dictionary, string $t$ of length $m$ that is textsです。どちらの問題に対しても、従来の量子アルゴリズムよりもうまく動作する新しい量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-06-18T14:16:49Z)
Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
文字列内のトークンのペア間の関係をモデル化するタスクは、自然言語を理解する上で不可欠な部分である。これらの徹底的な比較は避けられ、さらに、トークン間の関係を文字列上の部分順序としてキャストすることで、複雑さを線形に減らすことができる。提案手法は,文字列中の各トークンの実際の数を並列に予測し,それに従ってトークンをソートすることで,文字列内のトークンの総順序を決定する。
論文参考訳（メタデータ） (2023-05-24T11:47:35Z)
Quantum Algorithm for the Shortest Superstring Problem [0.0]
我々は、最短スーパーストリング問題(SSP)または最短共通スーパーストリング問題(SCS)を考える。
論文参考訳（メタデータ） (2021-12-26T05:37:56Z)
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)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)
Classical and Quantum Algorithms for Constructing Text from Dictionary Problem [0.0]
辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
論文参考訳（メタデータ） (2020-05-28T22:44:01Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。