論文の概要: Weighted Context-Free-Language Ordered Binary Decision Diagrams

• arxiv url: http://arxiv.org/abs/2305.13610v1
• Date: Tue, 23 May 2023 02:16:52 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-24 19:42:51.120543
• Title: Weighted Context-Free-Language Ordered Binary Decision Diagrams
• Title（参考訳）: 重み付き文脈自由言語順序付き二項決定図
• Authors: Meghana Sistla, Swarat Chaudhuri, Thomas Reps
• Abstract要約: 重み付けされたCFLOBDDは、WBDDやCFLOBDDよりも指数関数的に簡潔であることを示す。 また、量子回路シミュレーションのためのWCFLOBDDの評価を行い、ほとんどのベンチマークでWBDDやCFLOBDDよりも優れた性能を示した。
• 参考スコア（独自算出の注目度）: 7.638042073679073
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Over the years, many variants of Binary Decision Diagrams (BDDs) have been developed to address the deficiencies of vanilla BDDs. A recent innovation is the Context-Free-Language Ordered BDD (CFLOBDD), a hierarchically structured decision diagram, akin to BDDs enhanced with a procedure-call mechanism, which allows substructures to be shared in ways not possible with BDDs. For some functions, CFLOBDDs are exponentially more succinct than BDDs. Unfortunately, the multi-terminal extension of CFLOBDDs, like multi-terminal BDDs, cannot efficiently represent functions of type B^n -> D, when the function's range has many different values. This paper addresses this limitation through a new data structure called Weighted CFLOBDDs (WCFLOBDDs). WCFLOBDDs extend CFLOBDDs using insights from the design of Weighted BDDs (WBDDs) -- BDD-like structures with weights on edges. We show that WCFLOBDDs can be exponentially more succinct than both WBDDs and CFLOBDDs. We also evaluate WCFLOBDDs for quantum-circuit simulation, and find that they perform better than WBDDs and CFLOBDDs on most benchmarks. With a 15-minute timeout, the number of qubits that can be handled by WCFLOBDDs is 1,048,576 for GHZ (1x over CFLOBDDs, 256x over WBDDs); 262,144 for BV and DJ (2x over CFLOBDDs, 64x over WBDDs); and 2,048 for QFT (128x over CFLOBDDs, 2x over WBDDs).
• Abstract（参考訳）: 長年にわたり、バニラBDDの欠陥に対応するために、多くのバイナリ決定図(BDD)が開発されてきた。 最近のイノベーションはCFLOBDD(Context-Free-Language Ordered BDD)である。これは階層的に構造化された決定図で、プロシージャコール機構によって拡張されたBDDに似ている。 一部の関数では、CFLOBDDはBDDよりも指数関数的に簡潔である。 残念ながら、CFLOBDDのマルチ端末拡張は、多端末BDDと同様に、関数の範囲が多くの異なる値を持つ場合、B^n -> D型の関数を効率的に表現することはできない。 本稿では、この制限を、Weighted CFLOBDDs (WCFLOBDDs)と呼ばれる新しいデータ構造を通じて解決する。 WCFLOBDDはCFLOBDDを拡張し、重み付けされたBDD(WBDD) -- エッジに重みを持つBDDのような構造の設計から洞察を得る。 WCFLOBDDはWBDDやCFLOBDDよりも指数関数的に簡潔であることを示す。 また、量子回路シミュレーションのためのWCFLOBDDの評価を行い、ほとんどのベンチマークでWBDDやCFLOBDDよりも優れた性能を示した。 15分間のタイムアウトで、WCFLOBDDsで処理可能なキュービットの数は、GHZで1,048,576(CFLOBDDで1倍、WBDDで256倍)、BVとDJで262,144(CFLOBDDで2倍、WBDDで64倍)、QFTで2,048(CFLOBDDで128倍、WBDDで2倍)である。

関連論文リスト

• Exploiting Pre-trained Models for Drug Target Affinity Prediction with Nearest Neighbors [58.661454334877256]
  薬物-標的結合親和性(DTA)予測は、薬物発見に不可欠である。 DTA予測へのディープラーニング手法の適用にもかかわらず、達成された精度は依然として準最適である。 事前学習したDTA予測モデルに適用した非表現埋め込みに基づく検索手法である$k$NN-DTAを提案する。
  論文  参考訳（メタデータ） (2024-07-21T15:49:05Z)
• Buffer of Thoughts: Thought-Augmented Reasoning with Large Language Models [65.48185395952788]
  Buffer of Thoughts (BoT) は、斬新で多目的な思考補足的推論手法である。 そこで我々はメタバッファーを提案し,一連の情報的高レベルの思考を記憶する。 各問題に対して、関連する思考タイミングを検索し、特定の推論構造で適応的にインスタンス化する。
  論文  参考訳（メタデータ） (2024-06-06T17:22:08Z)
• Variants of Tagged Sentential Decision Diagrams [6.891570850234007]
  最近提案されたブール関数の標準形式、すなわちタグ付き逐次決定図(TSDD)は、標準およびゼロ抑圧トリミングルールの両方を利用する。 本稿では,トリミング規則の順序を逆転することで,標準TSDD(STSDD)と呼ぶTSDDの変種について述べる。 次に、STSDDの正準性を証明し、TSDD上でのバイナリ演算のアルゴリズムを示す。
  論文  参考訳（メタデータ） (2023-11-16T12:29:25Z)
• Exploiting Asymmetry in Logic Puzzles: Using ZDDs for Symbolic Model Checking Dynamic Epistemic Logic [0.0]
  我々は、動的疫学論理で使用されるクリプキモデルを象徴的に符号化するためにZDDを使用する。 BDDを適切なZDDに置き換えることで、メモリ使用量を大幅に削減できることを示す。 これはZDDがマルチエージェントシステムのモデル検査に有用なツールであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-11T07:13:09Z)
• Direct Diffusion Bridge using Data Consistency for Inverse Problems [65.04689839117692]
  拡散モデルに基づく逆問題解法は優れた性能を示したが、速度は制限されている。 いくつかの最近の研究は、拡散プロセスを構築し、クリーンで破損したものを直接ブリッジすることでこの問題を緩和しようと試みている。 微調整を必要とせずにデータの一貫性を強制する改良された推論手順を提案する。
  論文  参考訳（メタデータ） (2023-05-31T12:51:10Z)
• Belief Revision in Sentential Decision Diagrams [126.94029917018733]
  本研究では,Dalリビジョンの構文的特徴化に基づくSDDの一般的なリビジョンアルゴリズムを開発する。 ランダムに生成した知識ベースを用いた予備実験は、SDDフォーマリズム内で直接リビジョンを行う利点を示している。
  論文  参考訳（メタデータ） (2022-01-20T11:01:41Z)
• ADAPT: Mitigating Idling Errors in Qubits via Adaptive Dynamical Decoupling [3.2505361717998227]
  キュービットはアイドル状態にあり、アクティブな操作を行わないときに発生するアイドルエラーの影響を受けやすい。 既存の動的デカップリングプロトコルは主に個々の量子ビットに対して研究されている。 本稿では,各キュービットの組み合わせに対するDDの有効性を推定するソフトウェアフレームワークであるAdaptive Dynamical Decoupling (ADAPT)を提案する。
  論文  参考訳（メタデータ） (2021-09-11T16:15:24Z)
• Double Forward Propagation for Memorized Batch Normalization [68.34268180871416]
  バッチ正規化(BN)は、ディープニューラルネットワーク(DNN)の設計における標準コンポーネントである。 より正確でロバストな統計値を得るために,複数の最近のバッチを考慮に入れた記憶型バッチ正規化(MBN)を提案する。 関連する手法と比較して、提案したMBNはトレーニングと推論の両方において一貫した振る舞いを示す。
  論文  参考訳（メタデータ） (2020-10-10T08:48:41Z)
• DynaBERT: Dynamic BERT with Adaptive Width and Depth [55.18269622415814]
  我々は新しい動的BERTモデル(DynaBERTと略される)を提案する。 適応的な幅と深さを選択することで、サイズとレイテンシを柔軟に調整できる。 既存のBERT圧縮手法よりずっと優れています。
  論文  参考訳（メタデータ） (2020-04-08T15:06:28Z)
• Variable Shift SDD: A More Succinct Sentential Decision Diagram [10.91026094237478]
  Sentential Decision Diagram (SDD) はブール関数の抽出可能な表現である。 可変シフトSDD(VS-SDD)という,より簡潔なSDD変種を提案する。 我々は,VS-SDDがSDDよりも大きくなることはなく,VS-SDDのサイズがSDDよりも指数関数的に小さいケースがあることを示した。
  論文  参考訳（メタデータ） (2020-04-06T09:18:19Z)

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

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