Fugu-MT 論文翻訳(概要): A canonical generalization of OBDD

論文の概要: A canonical generalization of OBDD

arxiv url: http://arxiv.org/abs/2604.05537v1
Date: Tue, 07 Apr 2026 07:36:21 GMT
ステータス: 翻訳完了
システム内更新日: 2026-04-08 17:42:09.693321
Title: A canonical generalization of OBDD
Title（参考訳）: OBDDの標準一般化
Abstract要約: OBDDを一般化するブール関数のモデルとして、ツリー決定図(TDD)を紹介します。 TDDは、モデルカウント、列挙、条件付け、適用など、OBDDと同じトラクタビリティ特性を持ち、より簡潔です。木幅$k$のCNF式は、OBDDでは不可能であることが知られているFPTサイズのTDDで表せることを示す。
参考スコア（独自算出の注目度）: 30.681714489260898
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We introduce Tree Decision Diagrams (TDD) as a model for Boolean functions that generalizes OBDD. They can be seen as a restriction of structured d-DNNF; that is, d-DNNF that respect a vtree $T$. We show that TDDs enjoy the same tractability properties as OBDD, such as model counting, enumeration, conditioning, and apply, and are more succinct. In particular, we show that CNF formulas of treewidth $k$ can be represented by TDDs of FPT size, which is known to be impossible for OBDD. We study the complexity of compiling CNF formulas into deterministic TDDs via bottom-up compilation and relate the complexity of this approach with the notion of factor width introduced by Bova and Szeider.
Abstract（参考訳）: OBDDを一般化するブール関数のモデルとして、ツリー決定図(TDD)を紹介します。それらは構造付き d-DNNF の制限と見なすことができ、すなわち vtree $T$ を尊重する d-DNNF である。私たちは、TDDがモデルカウント、列挙、条件付け、適用など、OBDDと同じトラクタビリティ特性を享受していることを示し、より簡潔であることを示します。特に,木幅$k$のCNF式は,OBDDでは不可能であることが知られているFPTサイズのTDDで表せることを示す。ボトムアップコンパイルによってCNF式を決定論的TDDにコンパイルする複雑性について検討し,Bova と Szeider が導入した因子幅の概念と,このアプローチの複雑さを関連づける。

関連論文リスト

Compile to Compress: Boosting Formal Theorem Provers by Compiler Outputs [48.390500145598544]
大型言語モデル (LLM) は形式定理の証明において大きな可能性を証明している。我々は形式的検証において情報的構造を利用する: コンパイラが多様な証明の試みの広大な空間をマッピングする観察である。我々は,この圧縮を利用して効率的な学習と証明探索を行う,学習と再定義のためのフレームワークを提案する。
論文参考訳（メタデータ） (2026-03-13T01:33:20Z)
Learning Decision Trees as Amortized Structure Inference [59.65621207449269]
本稿では,予測決定木アンサンブルを学習するためのハイブリッドアモータイズされた構造推論手法を提案する。提案手法であるDT-GFNは,標準分類ベンチマークにおける最先端決定木やディープラーニング手法よりも優れていることを示す。
論文参考訳（メタデータ） (2025-03-10T07:05:07Z)
Compilation and Fast Model Counting beyond CNF [31.620928650659586]
本稿では,関数のクラスを効率的にd-DNNFに変換するか,あるいはコンパイルするかに関する理論的知識を強化する。問題の制約は、すべての変数順序付けに対して、定数幅順序付きバイナリ決定図(OBDD)で表現可能なすべての関数である。制約のサブファミリーに適用し,コンパイルを必要としないモデルカウントのためのより効率的なFPTアルゴリズムを提案する。
論文参考訳（メタデータ） (2025-02-01T14:00:04Z)
Structural Entropy Guided Probabilistic Coding [52.01765333755793]
構造エントロピー誘導型確率的符号化モデルSEPCを提案する。我々は、構造エントロピー正規化損失を提案することにより、潜在変数間の関係を最適化に組み込む。分類タスクと回帰タスクの両方を含む12の自然言語理解タスクに対する実験結果は、SEPCの優れた性能を示す。
論文参考訳（メタデータ） (2024-12-12T00:37:53Z)
Canonical Decision Diagrams Modulo Theories [0.19285000127136376]
決定図は命題公式を表現する強力なツールである。いくつかの形式(例えば OBDD や SDD など)は標準的であり、(原子リスト上の与えられた条件の下では)公式の同値類を単項的に表す。 DDをSMTレベルに活用する新しい手法を提案する。
論文参考訳（メタデータ） (2024-04-25T09:34:49Z)
Structured d-DNNF Is Not Closed Under Negation [0.0]
構造化d-DNNFとSDDはどちらも、OBDDよりも指数関数的に簡潔である。構造化d-DNNFは、ポリ時間否定、解離、存在的操作をサポートしていないことを示す。また、等価サイズの構造d-DNNFを持つ関数が存在するが、SDDのような表現は存在しないことを示す。
論文参考訳（メタデータ） (2024-02-07T13:31:59Z)
Efficient Computation of Counterfactual Bounds [44.4263314637532]
我々は,構造因果モデルのサブクラスにおけるクレダルネットのアルゴリズムを用いて,正確な反ファクト境界を計算する。近似の精度を信頼性のある間隔で評価する。
論文参考訳（メタデータ） (2023-07-17T07:59:47Z)
DPO: Dynamic-Programming Optimization on Hybrid Constraints [26.704502486686128]
ベイズ推定において、最も可能性の高い説明(MPE)問題は、いくつかの証拠から最も高い確率で変数のインスタンス化を要求する。ブール MPE は (部分重み付き) MaxSAT への還元によって解けることが知られている。我々はDPMC上に構築し,MPEを正確に解く動的プログラミングであるDPOを導入する。
論文参考訳（メタデータ） (2022-05-17T21:18:54Z)
Belief Revision in Sentential Decision Diagrams [126.94029917018733]
本研究では,Dalリビジョンの構文的特徴化に基づくSDDの一般的なリビジョンアルゴリズムを開発する。ランダムに生成した知識ベースを用いた予備実験は、SDDフォーマリズム内で直接リビジョンを行う利点を示している。
論文参考訳（メタデータ） (2022-01-20T11:01:41Z)
Contextualized Semantic Distance between Highly Overlapped Texts [85.1541170468617]
テキスト編集や意味的類似性評価といった自然言語処理タスクにおいて、ペア化されたテキストに重複が頻繁に発生する。本稿では,マスク・アンド・予測戦略を用いてこの問題に対処することを目的とする。本稿では,最も長い単語列の単語を隣接する単語とみなし,その位置の分布を予測するためにマスク付き言語モデリング(MLM)を用いる。セマンティックテキスト類似性の実験では、NDDは様々な意味的差異、特に高い重なり合うペアテキストに対してより敏感であることが示されている。
論文参考訳（メタデータ） (2021-10-04T03:59:15Z)
A Lower Bound on DNNF Encodings of Pseudo-Boolean Constraints [3.42658286826597]
疑似ブール制約をSATにエンコーディングする際の2つの大きな考慮事項は、エンコーディングのサイズとその伝播強度である。命令されたBDD(OBDD)表現と推論されたCNFエンコーディングがすべて指数的サイズを持つPB制約が存在することが示されている。
論文参考訳（メタデータ） (2021-01-06T10:25:22Z)
Supervised Learning for Non-Sequential Data: A Canonical Polyadic Decomposition Approach [85.12934750565971]
特徴相互作用の効率的なモデリングは、非順序的タスクに対する教師あり学習の基盤となる。この問題を緩和するため、モデルパラメータをテンソルとして暗黙的に表現することが提案されている。表現性を向上するため,任意の高次元特徴ベクトルに特徴写像を適用できるようにフレームワークを一般化する。
論文参考訳（メタデータ） (2020-01-27T22:38:40Z)

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