論文の概要: On the Complexity of the Grounded Semantics for Infinite Argumentation Frameworks
- arxiv url: http://arxiv.org/abs/2511.22376v1
- Date: Thu, 27 Nov 2025 12:13:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-01 19:47:55.551577
- Title: On the Complexity of the Grounded Semantics for Infinite Argumentation Frameworks
- Title（参考訳）: Infinite Argumentation Frameworkにおけるグラウンドド・セマンティクスの複雑さについて
- Authors: Uri Andrews, Luca San Mauro,
- Abstract要約: 数学的論理学、特に計算可能性と集合論の手法を用いて、基底拡張を解析する。
この固定点を見つけるには、無限反復が必要である。
このことは、基底拡張が時間計算可能である有限の場合と顕著な区別を示している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Argumentation frameworks, consisting of arguments and an attack relation representing conflicts, are fundamental for formally studying reasoning under conflicting information. We use methods from mathematical logic, specifically computability and set theory, to analyze the grounded extension, a widely-used model of maximally skeptical reasoning, defined as the least fixed-point of a natural defense operator. Without additional constraints, finding this fixed-point requires transfinite iterations. We identify the exact ordinal number corresponding to the length of this iterative process and determine the complexity of deciding grounded acceptance, showing it to be maximally complex. This shows a marked distinction from the finite case where the grounded extension is polynomial-time computable, thus simpler than other reasoning problems explored in formal argumentation.
- Abstract（参考訳）: 議論と紛争を表す攻撃関係からなる論証フレームワークは、矛盾する情報の下での推論を正式に研究するための基礎となる。
数学的論理学、特に計算可能性と集合論の手法を用いて、自然防衛作用素の最小固定点として定義される最大懐疑的推論の広く使われているモデルである基底拡張を解析する。
追加の制約がなければ、この固定点を見つけるには一定の反復が必要である。
我々は、この反復過程の長さに対応する正確な順序数を特定し、基礎的受容を決定する複雑さを判定し、それを極大に複雑であることを示す。
これは、基底拡大が多項式時間計算可能である有限の場合と顕著な区別を示しており、したがって形式的議論において探索された他の推論問題よりも単純である。
関連論文リスト
- Reasoning is about giving reasons [55.56111618153049]
高い精度の3つの一般的な推論データセットにおいて、自然言語の引数の論理構造を同定し、抽出できることが示される。
我々のアプローチは、自然言語の引数の論理構造に依存するあらゆる推論形式をサポートする。
論文 参考訳（メタデータ） (2025-08-20T07:26:53Z) - CLATTER: Comprehensive Entailment Reasoning for Hallucination Detection [60.98964268961243]
我々は,系統的かつ包括的な推論プロセスを実行するためのモデルを導くことで,モデルがよりきめ細やかで正確な絞り込み決定を実行できることを提案する。
我々は,(i)クレームの分解,(ii)サブクレームの属性と包含分類,および(iii)集約分類から成る3段階の推論プロセスを定義し,そのような導出推論が実際に幻覚検出の改善をもたらすことを示す。
論文 参考訳（メタデータ） (2025-06-05T17:02:52Z) - PixelThink: Towards Efficient Chain-of-Pixel Reasoning [70.32510083790069]
PixelThinkは、外部から推定されるタスクの難しさと内部で測定されたモデルの不確実性を統合する、シンプルで効果的なスキームである。
シーンの複雑さと予測信頼度に応じて推論の長さを圧縮することを学ぶ。
実験により,提案手法は推論効率と全体セグメンテーション性能の両方を改善した。
論文 参考訳（メタデータ） (2025-05-29T17:55:49Z) - Polynomial-Time Relational Probabilistic Inference in Open Universes [14.312814866832804]
本稿では,使用する言語の表現力と推論による計算問題のトラクタビリティを両立させる一階確率推定手法を提案する。
具体的には、期待の2乗論理をリレーショナルセッティングに拡張する。
与えられた次数と大きさの証明によって証明可能な最も厳密な境界を導出し、固定度に対する2乗の総和の完全性を確立することができる。
論文 参考訳（メタデータ） (2025-05-07T04:14:03Z) - Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length? [72.70486097967124]
決定論的有限オートマトン(DFAs)を用いたフレームワークの定式化
正しい解を生成する確率が最大になるような推論トークンが最適に存在することを示す。
新たな問題に対する推論トークンの最適個数を予測し、最適でない回答をフィルタリングすることで、一貫した精度の向上が得られる。
論文 参考訳（メタデータ） (2025-04-02T17:45:58Z) - Dialogue-based Explanations for Logical Reasoning using Structured Argumentation [0.06138671548064355]
我々は、最先端技術の構造的弱点を特定し、これらの問題に対処するための一般的な議論に基づくアプローチを提案する。
我々の研究は、問合せ応答を計算し、説明するための弁証法として対話モデルを提供する。
これにより、既存の説明形式よりも表現的かつ直感的な弁証的証明木を説明として構築することができる。
論文 参考訳（メタデータ） (2025-02-16T22:26:18Z) - Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach [0.0]
完全拡張である引数の集合の確率を計算する複雑なタスクのアルゴリズムを開発する。
実験的評価は我々のアプローチの可能性を示唆している。
論文 参考訳（メタデータ） (2024-07-06T12:08:38Z) - Counterfactual and Semifactual Explanations in Abstract Argumentation: Formal Foundations, Complexity and Computation [19.799266797193344]
議論ベースのシステムは、意思決定プロセスをサポートしながら説明責任を欠くことが多い。
対実的・半実的な説明は解釈可能性のテクニックである。
本稿では,制約の弱いArgumentation Frameworkにおいて,逆ファクトおよび半ファクトのクエリを符号化可能であることを示す。
論文 参考訳（メタデータ） (2024-05-07T07:27:27Z) - MetaLogic: Logical Reasoning Explanations with Fine-Grained Structure [129.8481568648651]
複雑な実生活シナリオにおけるモデルの論理的推論能力を調べるためのベンチマークを提案する。
推論のマルチホップ連鎖に基づいて、説明形式は3つの主成分を含む。
この新たな説明形式を用いて,現在のベストモデルの性能を評価した。
論文 参考訳（メタデータ） (2022-10-22T16:01:13Z) - Admissibility in Strength-based Argumentation: Complexity and Algorithms
(Extended Version with Proofs) [1.5828697880068698]
我々は、適応性に基づく意味論の強度に基づく論証フレームワーク(StrAF)への適応について研究する。
特に文献で定義された強い許容性は望ましい性質、すなわちDungの基本的な補題を満たさないことを示す。
計算(強弱)拡張に対する擬ブール制約の翻訳を提案する。
論文 参考訳（メタデータ） (2022-07-05T18:42:04Z) - A Formalisation of Abstract Argumentation in Higher-Order Logic [77.34726150561087]
本稿では,古典的高階論理へのエンコーディングに基づく抽象的議論フレームワークの表現手法を提案する。
対話型および自動推論ツールを用いた抽象的議論フレームワークのコンピュータ支援評価のための一様フレームワークを提供する。
論文 参考訳（メタデータ） (2021-10-18T10:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。