論文の概要: Complexity in finitary argumentation (extended version)

• arxiv url: http://arxiv.org/abs/2508.16986v1
• Date: Sat, 23 Aug 2025 11:02:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-26 18:43:45.284001
• Title: Complexity in finitary argumentation (extended version)
• Title（参考訳）: 有限論の複雑さ(拡張版)
• Authors: Uri Andrews, Luca San Mauro,
• Abstract要約: 本稿では,無限だが有限の議論フレームワークに関連する計算問題の複雑性について検討する。 多くの推論形式に対して、有限無限 AF は推論の自然な設定を提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Abstract argumentation frameworks (AFs) provide a formal setting to analyze many forms of reasoning with conflicting information. While the expressiveness of general infinite AFs make them a tempting tool for modeling many kinds of reasoning scenarios, the computational intractability of solving infinite AFs limit their use, even in many theoretical applications. We investigate the complexity of computational problems related to infinite but finitary argumentations frameworks, that is, infinite AFs where each argument is attacked by only finitely many others. Our results reveal a surprising scenario. On one hand, we see that the assumption of being finitary does not automatically guarantee a drop in complexity. However, for the admissibility-based semantics, we find a remarkable combinatorial constraint which entails a dramatic decrease in complexity. We conclude that for many forms of reasoning, the finitary infinite AFs provide a natural setting for reasoning which balances well the competing goals of being expressive enough to be applied to many reasoning settings while being computationally tractable enough for the analysis within the framework to be useful.
• Abstract（参考訳）: 抽象的な議論フレームワーク(AF)は、矛盾する情報と多くの種類の推論を分析するフォーマルな設定を提供する。 一般無限 AF の表現性は、様々な推論シナリオをモデル化するための誘惑的なツールであるが、無限 AF を解く計算的難解性は、多くの理論的応用においてもそれらの使用を制限する。 我々は、無限だが有限の議論フレームワーク、すなわち、各議論が有限個の他の議論によって攻撃される無限の AF に関連する計算問題の複雑さについて検討する。 私たちの結果は驚くべきシナリオを明らかにします。 一方、有限であるという仮定は、自動的に複雑性の低下を保証しない。 しかし、アクセシビリティに基づく意味論では、複雑化の劇的な減少を伴う顕著な組合せ制約が見つかる。 多くの推論形式に対して、有限無限 AF は、フレームワーク内の解析が有用であるのに十分な計算的抽出性を持ちながら、多くの推論設定に適用できるような、競合する目的のバランスの取れた推論に対して自然な設定を提供すると結論付けている。

関連論文リスト

• PixelThink: Towards Efficient Chain-of-Pixel Reasoning [70.32510083790069]
  PixelThinkは、外部から推定されるタスクの難しさと内部で測定されたモデルの不確実性を統合する、シンプルで効果的なスキームである。 シーンの複雑さと予測信頼度に応じて推論の長さを圧縮することを学ぶ。 実験により,提案手法は推論効率と全体セグメンテーション性能の両方を改善した。
  論文  参考訳（メタデータ） (2025-05-29T17:55:49Z)
• Facets in Argumentation: A Formal Approach to Argument Significance [18.218298349840023]
  議論は、議論のモデル化と推論のための人工知能(AI)の中心的なサブ領域である。 意思決定と列挙の推論のための新しい概念(顔)を導入する。 複雑さについて検討し、ファセットを含むタスクが拡張を数えるのよりもはるかに容易であることを示す。
  論文  参考訳（メタデータ） (2025-05-16T08:29:38Z)
• 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)
• Training Large Language Models to Reason in a Continuous Latent Space [84.5618790930725]
  我々は,制約のない潜在空間における大規模言語モデル(LLM)推論の可能性を探るため,新しいパラダイムであるCoconut (Chain of Continuous Thought)を導入する。 実験により、ココナッツはいくつかの推論タスクにおいてLLMを効果的に増強できることが示されている。 これらの知見は、潜伏推論の可能性を実証し、将来の研究に価値ある洞察を与える。
  論文  参考訳（メタデータ） (2024-12-09T18:55:56Z)
• Rejection in Abstract Argumentation: Harder Than Acceptance? [18.299322342860513]
  我々は、否定条件(RC)と呼ばれる拡張から引数を推論するための柔軟な条件を考える。 還元AFは非常に表現力が高く、階層の上位層に自然の問題を引き起こす。
  論文  参考訳（メタデータ） (2024-08-20T09:37:04Z)
• Counterfactual and Semifactual Explanations in Abstract Argumentation: Formal Foundations, Complexity and Computation [19.799266797193344]
  議論ベースのシステムは、意思決定プロセスをサポートしながら説明責任を欠くことが多い。 対実的・半実的な説明は解釈可能性のテクニックである。 本稿では,制約の弱いArgumentation Frameworkにおいて,逆ファクトおよび半ファクトのクエリを符号化可能であることを示す。
  論文  参考訳（メタデータ） (2024-05-07T07:27:27Z)
• An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
  有限状態オートマトンをオンザフライで決定する手法の抽象化を確立し, オートマトンにどのように適用できるかを実証する。 我々の発見の特別な例は、多くの非決定論的遷移を持つオートマトンが、ほとんど常に複雑性の決定性を持っていることである。
  論文  参考訳（メタデータ） (2023-08-27T11:51:27Z)
• Admissibility in Strength-based Argumentation: Complexity and Algorithms (Extended Version with Proofs) [1.5828697880068698]
  我々は、適応性に基づく意味論の強度に基づく論証フレームワーク(StrAF)への適応について研究する。 特に文献で定義された強い許容性は望ましい性質、すなわちDungの基本的な補題を満たさないことを示す。 計算(強弱)拡張に対する擬ブール制約の翻訳を提案する。
  論文  参考訳（メタデータ） (2022-07-05T18:42:04Z)
• From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
  本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。 8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
  論文  参考訳（メタデータ） (2020-06-05T10:56:52Z)

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

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