論文の概要: Complexity of Grounded Semantics and Preferred Semantics in Finitary Argumentation Frameworks

• arxiv url: http://arxiv.org/abs/2610.12008v1
• Date: Thu, 08 Oct 2026 14:10:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 02:36:54.070587
• Title: Complexity of Grounded Semantics and Preferred Semantics in Finitary Argumentation Frameworks
• Title（参考訳）: 有限割当て枠組における接地意味論と優先意味論の複雑さ
• Abstract要約: 議論フレームワーク(AF)は、人工知能における非単調推論の正式な基盤を提供する。 本稿では,標準決定問題にまたがる計算可能な有限 AF における基底的および優先的意味論の複雑性マッピングを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Abstract argumentation frameworks (AFs) introduced by Dung provide a formal foundation for non-monotonic reasoning in artificial intelligence. While decision problems for general infinite AFs typically reside at high levels of the analytical hierarchy ($Σ_1^1$ or $Π_1^1$), restricting the framework to be computably finitary reduces some of the complexity to the arithmetical hierarchy. In this paper, we present a complexity mapping of grounded and preferred semantics in computably finitary AFs across standard decision problems: credulous acceptance ($\Cred$), skeptical acceptance ($\Skep$), extension existence ($\Ex$), uniqueness ($\Uni$), and non-empty existence ($\NE$). For grounded semantics, credulous and skeptical acceptance are already known to be $Σ_1^0$-complete. We show that non-empty existence is also $Σ_1^0$-complete, whereas existence and uniqueness are trivial. These classifications are understood within the domain of valid computably finitary representations. For preferred semantics, using a computably finitely branching computation tree, $\Cred_{\pref}$ is shown to be in $Π_1^0$-c and $\NE_{\pref}$ is $Σ_2^0$-c. However, it is insufficient to reduce universal quantification and global uniqueness, leaving $\Skep_{\pref}$ in $Π_1^1$ and $\UniPref$ in $Σ_2^1$-c. Our results show the precise boundary where finitarity succeeds to bring reasoning down to the arithmetical hierarchy and where second-order quantification forces problems back into the analytical hierarchy.
• Abstract（参考訳）: Dungによって導入された抽象的議論フレームワーク(AF)は、人工知能における非単調推論の正式な基盤を提供する。 一般に無限のAFに対する決定問題は解析的階層($Σ_1^1$)の高レベルに存在するが、フレームワークを計算的に有限に制限することは、計算的階層への複雑性の一部を減少させる。 本稿では,信頼的受容(\Cred$),懐疑的受容(「Skep$」),拡張存在(「Ex$」),一意性(「Uni$」),非空存在(「NE$」)の2つの標準決定問題にまたがって,基礎的および優先的な意味論の複雑性マッピングを提案する。 接地的意味論では、確実かつ懐疑的な受容は、既に$Σ_1^0$-完全であることが知られている。 非空存在も$Σ_1^0$-完全であることを示し、一方存在と特異性は自明である。 これらの分類は、有効な計算可能な有限表現の領域内で理解される。 好ましいセマンティクスについては、計算可能な有限分岐計算木を用いて、$\Cred_{\pref}$ は $\_1^0$-c で、$\NE_{\pref}$ は $Σ_2^0$-c で表される。 しかし、普遍的量子化と大域的一意性を減少させるには不十分であり、$Skep_{\pref}$ を $ _1^1$ に、$\UniPref$ を $Σ_2^1$-c に残す。 本結果は,フィニタリティが算術的階層への推論に成功し,二階量子化が問題を解析的階層に戻すという,正確な境界を示す。

関連論文リスト

• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。 我々は悲観的な収束分析を避ける分析を提供する。 我々の成果は、既存の最先端の体制を改善した。
  論文  参考訳（メタデータ） (2026-06-14T14:11:07Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Similarity Field Theory: A Mathematical Framework for Intelligence [0.0]
  本稿では、実体間の類似性値の原則とその進化を定式化する数学的枠組みである「類似性場理論」を紹介する。 高いレベルでは、このフレームワークは、類似性に関する幾何学的な問題として、知性と解釈可能性を再設計する。 我々は、2つの定理を証明している: (i)非対称性は相互包含をブロックし、 (ii)安定性はアンカー座標または準位集合内の最終的な閉じ込めを必要とする。
  論文  参考訳（メタデータ） (2025-09-21T22:34:00Z)
• Bound by semanticity: universal laws governing the generalization-identification tradeoff [8.437463955457423]
  有限分解能の類似性は、単なる玩具・模型の人工物ではなく、基本的な創発的な情報制約であることを示す。 これらの結果は、一般化識別トレードオフの正確な理論を提供し、意味論的解決がディープネットワークや脳の表現能力をどのように形成するかを明らかにする。
  論文  参考訳（メタデータ） (2025-06-01T15:56:26Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster [9.516475567386767]
  単項述語のみを円周的に最小化(あるいは固定化)した場合、論理オントロジーの決定可能性を証明する。 FO$2$の場合、複雑さは$textrmcoNexp$から$textrmTower$-complete、GFでは$textrm2Exp$から$textrmTower$-completeに増加します。
  論文  参考訳（メタデータ） (2024-07-30T13:39:38Z)
• 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)

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

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