論文の概要: 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の標準一般化
- Authors: Florent Capelli, YooJung Choi, Stefan Mengel, Martín Muñoz, Guy Van den Broeck,
- 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 が導入した因子幅の概念と,このアプローチの複雑さを関連づける。
関連論文リスト
- 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。