Fugu-MT 論文翻訳(概要): Finite Model Theory of the Triguarded Fragment and Related Logics

論文の概要: 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完全性も確立する。