論文の概要: Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster

• arxiv url: http://arxiv.org/abs/2407.20822v1
• Date: Tue, 30 Jul 2024 13:39:38 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-31 17:10:01.062084
• Title: Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster
• Title（参考訳）: 決定可能な1次論理のフラグメントに円積を加える:複雑性ローラーコアスター
• Authors: Carsten Lutz, Quentin Manière,
• Abstract要約: 単項述語のみを円周的に最小化(あるいは固定化)した場合、論理オントロジーの決定可能性を証明する。 FO$2$の場合、複雑さは$textrmcoNexp$から$textrmTower$-complete、GFでは$textrm2Exp$から$textrmTower$-completeに増加します。
• 参考スコア（独自算出の注目度）: 9.516475567386767
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We study extensions of expressive decidable fragments of first-order logic with circumscription, in particular the two-variable fragment FO$^2$, its extension C$^2$ with counting quantifiers, and the guarded fragment GF. We prove that if only unary predicates are minimized (or fixed) during circumscription, then decidability of logical consequence is preserved. For FO$^2$ the complexity increases from $\textrm{coNexp}$ to $\textrm{coNExp}^\textrm{NP}$-complete, for GF it (remarkably!) increases from $\textrm{2Exp}$ to $\textrm{Tower}$-complete, and for C$^2$ the complexity remains open. We also consider querying circumscribed knowledge bases whose ontology is a GF sentence, showing that the problem is decidable for unions of conjunctive queries, $\textrm{Tower}$-complete in combined complexity, and elementary in data complexity. Already for atomic queries and ontologies that are sets of guarded existential rules, however, for every $k \geq 0$ there is an ontology and query that are $k$-$\textrm{Exp}$-hard in data complexity.
• Abstract（参考訳）: 本研究では、一階述語論理の一階述語論理の表現的決定可能な断片の拡張、特に2変数の断片 FO$^2$, その拡張 C$^2$, そしてガードされたフラグメントGFについて検討する。 単項述語のみを円周的に最小化(あるいは固定化)した場合、論理的帰結の決定性は維持される。 FO$^2$の場合、複雑性は$\textrm{coNexp}$から$\textrm{coNExp}^\textrm{NP}$-completeへ、GFでは$\textrm{2Exp}$から$\textrm{Tower}$-completeへ、そしてC$^2$の場合、複雑さは依然としてオープンである。 また、オントロジーがGF文である囲い込み知識ベースの問合せについても検討し、結合的クエリの和合、$\textrm{Tower}$-completeの複雑さ、データの複雑さの初等的な相違について検討する。 しかし、ガードされた存在ルールの集合であるアトミッククエリやオントロジーはすでに存在するが、$k \geq 0$ごとにオントロジーとクエリがあり、データ複雑性は$k$-$\textrm{Exp}$-hardである。

関連論文リスト

• On the Communication Complexity of Approximate Pattern Matching [2.4167127333650202]
  上界が$O(n/m cdot k log2 m)$ bitsであることを証明する。 また、$O(n/m cdot k log2 m)$ bits は、$k$-error 発生毎に$P$ in $T$ のエンコードを可能にする。
  論文  参考訳（メタデータ） (2024-03-27T17:57:16Z)
• Quantum divide and conquer [6.527258283771695]
  Divide-and-conquerフレームワークは、古典的なアルゴリズム設計で広く使われている。 C_Q(n) leq sqrta, C_Q(n/b) + O(Ctextrmaux_Q(n))$$ の類似反復関係を生じる量子分割・量子化フレームワークについて述べる。
  論文  参考訳（メタデータ） (2022-10-12T17:14:28Z)
• Randomised Composition and Small-Bias Minimax [0.9252523881586053]
  クエリ複雑性に関する2つの結果が、$mathrmR(f)$であることを示す。 まず、「線形化」複雑性測度$mathrmLR$を導入し、内部衝突合成定理を満たすことを示す: $mathrmR(f) geq Omega(mathrmR(f) mathrmLR(g))$ for all partial $f$と$g$。
  論文  参考訳（メタデータ） (2022-08-26T23:32:19Z)
• Complexity and Avoidance [0.0]
  適切な$f$と$p$に対して$q$と$g$があり、$mathrmLUA(q) leq_mathrms mathrmCOMPLEX(f)$と$q$と$g$の成長率があることを示す。 シフト複雑性に関して、$$$q$が$rmLUA(q)$の任意のメンバに対して、$delta$-shift複素列を計算するためにどれだけ遅くなるかという明示的な境界が与えられる。
  論文  参考訳（メタデータ） (2022-04-24T14:36:38Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。