論文の概要: From Exponential to Polynomial Complexity: Efficient Permutation Counting with Subword Constraints

• arxiv url: http://arxiv.org/abs/2411.16744v1
• Date: Sat, 23 Nov 2024 19:52:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-27 13:33:43.373910
• Title: From Exponential to Polynomial Complexity: Efficient Permutation Counting with Subword Constraints
• Title（参考訳）: 指数から多項式への複雑性:単語制約を考慮した効率的な置換数
• Authors: Martin Mathew, Javier Noda,
• Abstract要約: 置換による異なる置換を数えることは、特に複数のサブワードを含む場合、分析における長年の課題である。 本稿では,置換による異なる置換を計算するための閉形式式を示す新しいフレームワークを提案する。 次に、新たな式を開発することにより、基本公式を複数のサブワードを扱うように拡張する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Counting distinct permutations with replacement, especially when involving multiple subwords, is a longstanding challenge in combinatorial analysis, with critical applications in cryptography, bioinformatics, and statistical modeling. This paper introduces a novel framework that presents closed-form formulas for calculating distinct permutations with replacement, fundamentally reducing the time complexity from exponential to linear relative to the sequence length for single-subword calculations. We then extend our foundational formula to handle multiple subwords through the development of an additional formula. Unlike traditional methods relying on brute-force enumeration or recursive algorithms, our approach leverages novel combinatorial constructs and advanced mathematical techniques to achieve unprecedented efficiency. This comprehensive advancement in reducing computational complexity not only simplifies permutation counting but also establishes a new benchmark for scalability and versatility. We also demonstrate the practical utility of our formulas through diverse applications, including the simultaneous identification of multiple genetic motifs in DNA sequences and complex pattern analysis in cryptographic systems, using a computer program that runs the proposed formulae.
• Abstract（参考訳）: 複数のサブワードを含む場合、置換による異なる置換をカウントすることは、暗号、バイオインフォマティクス、統計モデリングにおいて重要な応用を持つ、組合せ分析における長年にわたる課題である。 本稿では,置換による異なる置換を計算するための閉形式公式を新たに提案し,単文計算の列長に対する指数関数から線形への時間複雑性を根本的に低減する手法を提案する。 次に、新たな式を開発することにより、基本公式を複数のサブワードを扱うように拡張する。 ブルートフォース列挙法や再帰的アルゴリズムを頼りにしている従来の手法とは異なり、我々の手法は、前例のない効率を達成するために、新しい組合せ構造と高度な数学的手法を活用する。 この計算複雑性の削減における包括的な進歩は、置換カウントを単純化するだけでなく、スケーラビリティと汎用性のための新しいベンチマークを確立する。 また,DNA配列における複数の遺伝的モチーフの同時同定や,暗号システムにおける複雑なパターン解析など,多種多様な応用による我々の公式の実用性を,提案式を実行するコンピュータプログラムを用いて実証した。

関連論文リスト

• A novel framework for systematic propositional formula simplification based on existential graphs [1.104960878651584]
  本稿では、パースの実在グラフの推論と含意グラフの規則から導かれる命題論理の単純化計算について述べる。 我々の規則は、ネスト形式の命題論理式に適用でき、同値保存であり、単調に減少する変数、節、リテラルの数を保証し、構造的問題情報の保存を最大化することができる。
  論文  参考訳（メタデータ） (2024-05-27T11:42:46Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• A Hybrid System for Systematic Generalization in Simple Arithmetic Problems [70.91780996370326]
  本稿では,記号列に対する合成的および体系的推論を必要とする算術的問題を解くことができるハイブリッドシステムを提案する。 提案システムは,最も単純なケースを含むサブセットでのみ訓練された場合においても,ネストした数式を正確に解くことができることを示す。
  論文  参考訳（メタデータ） (2023-06-29T18:35:41Z)
• A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithms [64.3064050603721]
  本研究では,リカレントニューラルネットワーク (R2N2) にランゲ・クッタニューラルネットワークを一般化し,リカレントニューラルネットワークを最適化した反復アルゴリズムの設計を行う。 本稿では, 線形方程式系に対するクリロフ解法, 非線形方程式系に対するニュートン・クリロフ解法, 常微分方程式に対するルンゲ・クッタ解法と類似の繰り返しを計算問題クラスの入力・出力データに対して提案した超構造内における重みパラメータの正規化について述べる。
  論文  参考訳（メタデータ） (2022-11-22T16:30:33Z)
• Set Interdependence Transformer: Set-to-Sequence Neural Networks for Permutation Learning and Structure Prediction [6.396288020763144]
  セット・ツー・シーケンス問題は自然言語処理、コンピュータビジョン、構造予測において発生する。 それまでの注意に基づく手法では、n$-次関係を明示的に表すために、セット変換の$n$層を必要とする。 本稿では,集合の置換不変表現を任意の濃度の集合内のその要素に関連付けることのできる,集合間距離変換器と呼ばれる新しいニューラルセット符号化法を提案する。
  論文  参考訳（メタデータ） (2022-06-08T07:46:49Z)
• Permutation Invariant Representations with Applications to Graph Deep Learning [8.403227482145297]
  本稿では、任意の任意の列列置換が与えられた行列によって生成される商空間のユークリッド埋め込みについて述べる。 ほぼ至るところで、最小冗長性と計算コストの低いインジェクティブスキームを実装できる。
  論文  参考訳（メタデータ） (2022-03-14T23:13:59Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
  動的プログラミング(動的プログラミング、英: Dynamic Programming、DP)は、難解問題の効率的かつ正確な解法のためのアルゴリズム設計パラダイムである。 本稿では,セミリングに基づくDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
  論文  参考訳（メタデータ） (2021-07-05T00:51:02Z)
• Analyzing the Nuances of Transformers' Polynomial Simplification Abilities [11.552059052724907]
  我々は、Transformerが数値乗算に一貫して苦労していることを示します。 そこで我々は,カリキュラムの学習と記号計算のアプローチという2つの方法を検討した。 どちらのアプローチも、バニラトランスフォーマーベースのベースラインを大きく上回っている。
  論文  参考訳（メタデータ） (2021-04-29T03:52:46Z)
• Isometric Multi-Shape Matching [50.86135294068138]
  形状間の対応を見つけることは、コンピュータビジョンとグラフィックスの基本的な問題である。 アイソメトリーは形状対応問題においてしばしば研究されるが、マルチマッチング環境では明確には考慮されていない。 定式化を解くのに適した最適化アルゴリズムを提案し,コンバージェンスと複雑性解析を提供する。
  論文  参考訳（メタデータ） (2020-12-04T15:58:34Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。