Fugu-MT 論文翻訳(概要): Structured d-DNNF Is Not Closed Under Negation

論文の概要: Structured d-DNNF Is Not Closed Under Negation

arxiv url: http://arxiv.org/abs/2402.04832v1
Date: Wed, 7 Feb 2024 13:31:59 GMT
ステータス: 処理完了
システム内更新日: 2024-02-08 15:29:55.579098
Title: Structured d-DNNF Is Not Closed Under Negation
Title（参考訳）: 構造d-DNNFは否定で閉鎖されない
Authors: Harry Vinall-Smeeth
Abstract要約: 構造化d-DNNFとSDDはどちらも、OBDDよりも指数関数的に簡潔である。構造化d-DNNFは、ポリ時間否定、解離、存在的操作をサポートしていないことを示す。また、等価サイズの構造d-DNNFを持つ関数が存在するが、SDDのような表現は存在しないことを示す。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Both structured d-DNNF and SDD can be exponentially more succinct than OBDD. Moreover, SDD is essentially as tractable as OBDD. But this has left two important open questions. Firstly, does OBDD support more tractable transformations than structured d-DNNF? And secondly, is structured d-DNNF more succinct than SDD? In this paper, we answer both questions in the affirmative. For the first question we show that, unlike OBDD, structured d-DNNF does not support polytime negation, disjunction, or existential quantification operations. As a corollary, we deduce that there are functions with an equivalent polynomial-sized structured d-DNNF but with no such representation as an SDD, thus answering the second question. We also lift this second result to arithmetic circuits (AC) to show a succinctness gap between PSDD and the monotone AC analogue to structured d-DNNF.
Abstract（参考訳）: 構造化d-DNNFとSDDはどちらもOBDDよりも指数関数的に簡潔である。さらに、SDDは基本的にOBDDと同じくらい魅力的です。しかし、これは2つの重要な疑問を残している。まず、OBDDは構造化d-DNNFよりもトラクタブルな変換をサポートしていますか? 次に、構造d-DNNFはSDDよりも簡潔か? 本稿では,両質問に対して肯定的回答を行う。最初の質問では、OBDDとは異なり、構造化d-DNNFはポリ時間否定、解離、存在量化操作をサポートしていない。コーナリーとして、等価多項式サイズの構造d-DNNFを持つが、SDDのような表現を持たない関数が存在すると推定し、第二の疑問に答える。また、この第2の結果を算術回路(AC)に引き上げ、PSDDと構造d-DNNFに類似した単調ACとの簡潔さのギャップを示す。

関連論文リスト

Unsupervised Chunking with Hierarchical RNN [62.15060807493364]
本稿では,非階層的手法で単語をグループ化する構文的タスクであるチャンキングに対する教師なしアプローチを紹介する。本稿では,単語-チャンク・チャンク-文合成をモデル化した2層階層型階層型リカレントニューラルネットワーク(HRNN)を提案する。 CoNLL-2000データセットの実験では、既存の教師なし手法よりも顕著な改善が見られ、フレーズF1スコアが最大6ポイント向上した。
論文参考訳（メタデータ） (2023-09-10T02:55:12Z)
Weighted Context-Free-Language Ordered Binary Decision Diagrams [9.483290784772011]
本稿では,emphWeighted Context-Free-Language Ordered BDDs(WCFLOBDDs)と呼ばれる新しいデータ構造を提案する。一部の関数では、WCFLOBDDはWBDDよりも指数関数的に簡潔である。我々は、量子回路シミュレーションにWCFLOBDDを適用し、特定のベンチマークでWBDDよりも優れた性能を発揮することを発見した。
論文参考訳（メタデータ） (2023-05-23T02:16:52Z)
Efficacy of noisy dynamical decoupling [0.0]
動的デカップリング(英: Dynamical Decoupling, DD)とは、量子系における誤りの軽減法である。ノイズパルスが存在する場合、DDは必ずしもエラーを軽減するとは限らない。 DDパルスからの付加ノイズが、元のバックグラウンドノイズを平均化する能力の増大を上回りません。
論文参考訳（メタデータ） (2022-09-19T14:19:11Z)
Differentiable and Transportable Structure Learning [73.84540901950616]
本稿では,新しいアーキテクチャと損失関数により,発見された構造物の輸送性を回復するD-Structを紹介する。 D-Structは依然として微分可能であるため、既存の微分可能アーキテクチャでは容易に適用できる。
論文参考訳（メタデータ） (2022-06-13T17:50:53Z)
Belief Revision in Sentential Decision Diagrams [126.94029917018733]
本研究では,Dalリビジョンの構文的特徴化に基づくSDDの一般的なリビジョンアルゴリズムを開発する。ランダムに生成した知識ベースを用いた予備実験は、SDDフォーマリズム内で直接リビジョンを行う利点を示している。
論文参考訳（メタデータ） (2022-01-20T11:01:41Z)
Recursive Bayesian Networks: Generalising and Unifying Probabilistic Context-Free Grammars and Dynamic Bayesian Networks [0.0]
確率的文脈自由文法 (PCFGs) と動的ベイズネットワーク (DBNs) は相補的な強みと制約を持つシーケンスモデルとして広く使われている。本稿では,PCFGとDBNを一般化・統合するRecursive Bayesian Networks(RBNs)について述べる。
論文参考訳（メタデータ） (2021-11-02T19:21:15Z)
A Lower Bound on DNNF Encodings of Pseudo-Boolean Constraints [3.42658286826597]
疑似ブール制約をSATにエンコーディングする際の2つの大きな考慮事項は、エンコーディングのサイズとその伝播強度である。命令されたBDD(OBDD)表現と推論されたCNFエンコーディングがすべて指数的サイズを持つPB制約が存在することが示されている。
論文参考訳（メタデータ） (2021-01-06T10:25:22Z)
Substructure Substitution: Structured Data Augmentation for NLP [55.69800855705232]
SUB2は、同じラベルを持つサブ構造を置換して新しい例を生成する。より一般的なタスクでは、選挙区解析木に基づくSUB2のバリエーションを示す。ほとんどの場合、SUB2による強化データセットによるトレーニングは、元のトレーニングセットでのトレーニングよりも優れたパフォーマンスを達成する。
論文参考訳（メタデータ） (2021-01-02T09:54:24Z)
Towards Deeper Graph Neural Networks with Differentiable Group Normalization [61.20639338417576]
グラフニューラルネットワーク(GNN)は、隣接するノードを集約することでノードの表現を学習する。オーバースムーシングは、レイヤーの数が増えるにつれてGNNのパフォーマンスが制限される重要な問題のひとつです。 2つのオーバースムースなメトリクスと新しいテクニック、すなわち微分可能群正規化(DGN)を導入する。
論文参考訳（メタデータ） (2020-06-12T07:18:02Z)
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)
Architecture Disentanglement for Deep Neural Networks [174.16176919145377]
ディープニューラルネットワーク(DNN)の内部動作を説明するために,ニューラルアーキテクチャ・ディコンタングルメント(NAD)を導入する。 NADは、訓練済みのDNNを独立したタスクに従ってサブアーキテクチャに切り離すことを学び、推論プロセスを記述する情報フローを形成する。その結果、誤分類された画像は、タスクサブアーキテクチャーに正しいサブアーキテクチャーに割り当てられる確率が高いことが示された。
論文参考訳（メタデータ） (2020-03-30T08:34:33Z)

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