論文の概要: Finite Model Theory of the Triguarded Fragment and Related Logics
- arxiv url: http://arxiv.org/abs/2101.08377v2
- Date: Sat, 23 Jan 2021 08:56:14 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-21 07:49:32.462593
- Title: Finite Model Theory of the Triguarded Fragment and Related Logics
- Title(参考訳): 三ガードフラグメントの有限モデル理論と関連する論理
- Authors: Emanuel Kiero\'nski and Sebastian Rudolph
- Abstract要約: Triguarded Fragment (TGF)は第一次論理の最も表現力のある決定可能な断片の1つである。
そこで, TGF は有限モデル特性を持ち, 有限満足度は N2ExpTime-complete として知られる満足度と一致することを示した。
- 参考スコア(独自算出の注目度): 3.883460584034766
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The Triguarded Fragment (TGF) is among the most expressive decidable
fragments of first-order logic, subsuming both its two-variable and guarded
fragments without equality. We show that the TGF has the finite model property
(providing a tight doubly exponential bound on the model size) and hence finite
satisfiability coincides with satisfiability known to be N2ExpTime-complete.
Using similar constructions, we also establish 2ExpTime-completeness for finite
satisfiability of the constant-free (tri)guarded fragment with transitive
guards.
- Abstract(参考訳): Triguarded Fragment (TGF) は、一階述語論理の最も表現力に富んだ断片であり、その2変数とガードされた断片の両方を等しく仮定している。
TGF は有限モデル特性(モデルサイズに厳密な2倍指数境界を与える)を持ち、したがって有限満足度は N2ExpTime 完全であることが知られている満足度と一致することを示す。
同様の構成を用いると、遷移ガード付き固定自由(tri)ガードフラグメントの有限充足性に対する2ExpTime完全性も確立する。
関連論文リスト
- DNG: Taxonomy Expansion by Exploring the Intrinsic Directed Structure on
Non-Gaussian Space [15.486066629896149]
本稿では,各ノードを継承特徴(構造部分)と拡張特徴(補足部分)の組み合わせとして明示的に記述する。
Darmois-Skitovich Theorem に触発されて、補足的特徴に対する非ガウス的制約により、この可逆性を実装した。
論文 参考訳(メタデータ) (2023-02-22T06:15:02Z) - GFlowNet-EM for learning compositional latent variable models [113.65759013860063]
ラテントの後方のモデリングにおける重要なトレードオフは、表現性とトラクタブルな最適化の間にある。
非正規化密度からサンプリングするアルゴリズムであるGFlowNetsを提案する。
GFlowNetsをトレーニングして、後部から潜伏者へのサンプルをトレーニングすることにより、それらの強度をアモータライズされた変分アルゴリズムとして活用する。
論文 参考訳(メタデータ) (2023-02-13T18:24:21Z) - Digitizing SU(2) Gauge Fields and What to Look Out for When Doing So [0.0]
我々は、SU(2) の非自明な例に対するいくつかの離散化アプローチについて、その結果を提示する。
フィボナッチ・スパイラルの一般化されたバージョンは、特に効率的で最適に近いように見える。
論文 参考訳(メタデータ) (2022-12-19T14:31:47Z) - From Gradient Flow on Population Loss to Learning with Stochastic
Gradient Descent [50.4531316289086]
SGD(Gradient Descent)は、大規模非ルートモデルの学習方法である。
集団損失のGFが収束すると仮定して、総合的な条件 SGD が収束する。
我々は、凸損失のような古典的な設定だけでなく、Retrieval Matrix sq-rootのようなより複雑な問題に対してもGD/SGDを統一的に解析する。
論文 参考訳(メタデータ) (2022-10-13T03:55:04Z) - Temporal Inference with Finite Factored Sets [0.07614628596146598]
有限因子集合は時間的関係を推定するための強力なツールであることを示す。
因子集合に対するd-分離の類似性、条件性を導入する。
論文 参考訳(メタデータ) (2021-09-23T17:33:30Z) - Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable
Approach for Continuous Markov Random Fields [53.31927549039624]
断片的な離散化は既存の離散化問題と矛盾しないことを示す。
この理論を2つの画像のマッチング問題に適用する。
論文 参考訳(メタデータ) (2021-07-13T12:31:06Z) - Fold2Seq: A Joint Sequence(1D)-Fold(3D) Embedding-based Generative Model
for Protein Design [70.27706384570723]
Fold2Seqは特定の標的に条件付きタンパク質配列を設計するための新しいフレームワークである。
Fold2Seqの性能は, シーケンス設計の速度, カバレッジ, 信頼性において向上したか, 同等であったかを示す。
フォールドベースのFold2Seqの独特な利点は、構造ベースのディープモデルやRosettaDesignと比較して、3つの現実世界の課題においてより明確になる。
論文 参考訳(メタデータ) (2021-06-24T14:34:24Z) - On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum
Optimization [1.6973426830397942]
平滑な非有限和最適化における高階法の下限を証明する。
pth-order regularized method は有限和の目的から利益を得ることができないことを示す。
新たな二階平滑性仮定は一階平均二乗平滑性に類似していると考えられる。
論文 参考訳(メタデータ) (2021-03-08T23:33:58Z) - Weighted First-Order Model Counting in the Two-Variable Fragment With
Counting Quantifiers [10.635097939284751]
Van den Broeckらによる[KR, 2014]の研究により、一階モデルの重み付けはドメイン要素の数で時間内に解けることが知られている。
本稿では、この結果を量子化器で数えられる2変数のフラグメントに拡張する。
論文 参考訳(メタデータ) (2020-07-10T21:38:42Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳(メタデータ) (2020-02-24T17:55:10Z) - Best Arm Identification for Cascading Bandits in the Fixed Confidence
Setting [81.70513857417106]
CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。
CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。
その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
論文 参考訳(メタデータ) (2020-01-23T16:47:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。