Fugu-MT 論文翻訳(概要): On the Complexity of the Discussion-based Semantics in Abstraction Argumentation

論文の概要: On the Complexity of the Discussion-based Semantics in Abstraction Argumentation

arxiv url: http://arxiv.org/abs/2604.11480v1
Date: Mon, 13 Apr 2026 13:47:30 GMT
ステータス: 翻訳完了
システム内更新日: 2026-04-14 20:13:16.575226
Title: On the Complexity of the Discussion-based Semantics in Abstraction Argumentation
Title（参考訳）: 抽象論における議論に基づく意味論の複雑さについて
Authors: Lydia Blümel, Kai Sauerwald, Kenneth Skiba, Matthias Thimm,
Abstract要約: 議論に基づくアンゴーとベン=ナイムの意味論に関して、議論 a が議論 b よりも強いかどうかを決定することは、時間内に決定可能であることを示す。我々はオートマタ理論を採用し、この問題をセミリングオートマタの同値問題に還元する。
参考スコア（独自算出の注目度）: 8.893170669739344
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: We show that deciding whether an argument a is stronger than an argument b with respect to the discussion-based semantics of Amgoud and Ben-Naim is decidable in polynomial time. At its core, this problem is about deciding whether, for two vertices in a graph, the number of walks of each length ending in those vertices is the same. We employ results from automata theory and reduce this problem to the equivalence problem for semiring automata. This offers a new perspective on the computational complexity of ranking semantics, an area in which the complexity of many semantics remains open.
Abstract（参考訳）: 議論に基づくアンゴーとベン=ナイムの意味論に関して、議論 a が議論 b よりも強いかどうかを決定することは多項式時間で決定可能であることを示す。問題の中心は、グラフ内の2つの頂点に対して、それぞれの頂点で終わる長さのウォークの数が同じかどうかを決定することである。我々は、オートマトン理論の結果を用いて、セミリングオートマトンにおける同値問題にこの問題を還元する。これは、多くの意味論の複雑さが残っている領域であるランキングセマンティクスの計算複雑性に関する新しい視点を提供する。

関連論文リスト

On the Complexity of the Grounded Semantics for Infinite Argumentation Frameworks [0.0]
数学的論理学、特に計算可能性と集合論の手法を用いて、基底拡張を解析する。この固定点を見つけるには、無限反復が必要である。このことは、基底拡張が時間計算可能である有限の場合と顕著な区別を示している。
論文参考訳（メタデータ） (2025-11-27T12:13:30Z)
Explore Briefly, Then Decide: Mitigating LLM Overthinking via Cumulative Entropy Regulation [82.62935304152239]
大規模言語モデル(LLM)は、長いチェーン・オブ・ソート(CoT)推論を用いた複雑な問題に対する顕著な推論能力を示した。しばしば過度の思考に悩まされ、単純な問題に対して必要以上に長い推論ステップが生じる。本稿では, 推論過程を通じて探索範囲を計測する新しい計量量であるToken Entropy Cumulative Average(TECA)を紹介する。
論文参考訳（メタデータ） (2025-10-02T17:36:50Z)
Towards Solving More Challenging IMO Problems via Decoupled Reasoning and Proving [48.22540519786074]
最近の研究では、非公式な精度は80%を超え、公式な成功はPutnamBenchのようなベンチマークで8%以下である。低レベルの証明生成から高レベルの推論を分離する新しいフレームワークを提案する。提案手法は,2000年以降のIMO問題に対して,従来のオープンソース証明者が未報告の課題として評価した。
論文参考訳（メタデータ） (2025-07-07T22:38:49Z)
A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds [6.6362553223890535]
我々は、見過ごされているように見えるが自然なパラメータ n の下で、難解な誘引問題の複雑さを分析する。 SigmaP$ と NP- および coNP-完全フラグメントに対していくつかの正の値が得られる。我々はこれを低い境界で補い、多くのフラグメントは(強い)指数時間仮説の下で改善を除外する。
論文参考訳（メタデータ） (2025-05-15T11:56:19Z)
Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length? [72.70486097967124]
決定論的有限オートマトン(DFAs)を用いたフレームワークの定式化正しい解を生成する確率が最大になるような推論トークンが最適に存在することを示す。新たな問題に対する推論トークンの最適個数を予測し、最適でない回答をフィルタリングすることで、一貫した精度の向上が得られる。
論文参考訳（メタデータ） (2025-04-02T17:45:58Z)
Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach [0.0]
完全拡張である引数の集合の確率を計算する複雑なタスクのアルゴリズムを開発する。実験的評価は我々のアプローチの可能性を示唆している。
論文参考訳（メタデータ） (2024-07-06T12:08:38Z)
Abstract Weighted Based Gradual Semantics in Argumentation Theory [3.2566808526538873]
段階的意味論と受容可能性度を結びつける4つの重要な問題を導入する。まず、逆問題を再検討し、議論フレームワークの引数重みを特定して、特定の最終的な受容可能性の度合いを導いた。第三に、議論の受理度が考慮されるのではなく、選好時に議論の重みが見つかるかどうかを問う。第4に、この空間に「ギャップ」が存在するかどうかを問う、有効な受容可能性次数の空間の位相を考える。
論文参考訳（メタデータ） (2024-01-21T12:22:48Z)
An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
有限状態オートマトンをオンザフライで決定する手法の抽象化を確立し, オートマトンにどのように適用できるかを実証する。我々の発見の特別な例は、多くの非決定論的遷移を持つオートマトンが、ほとんど常に複雑性の決定性を持っていることである。
論文参考訳（メタデータ） (2023-08-27T11:51:27Z)
The Inverse Problem for Argumentation Gradual Semantics [8.860629791560198]
このような意味論のサブクラス、いわゆる重み付き意味論は、引数に対する初期重みのセットを入力として取る。このような重み付き意味論に対する逆問題を考える。すなわち、議論の枠組みと望ましい議論のランキングが与えられた場合、特定の意味論が与えられたランキングを生成するような初期重みが存在するかどうかを問う。
論文参考訳（メタデータ） (2022-02-01T09:46:23Z)
Relevant OTOC operators: footprints of the classical dynamics [68.8204255655161]
OTOC-RE定理(OTOC-RE theorem)は、作用素の完備な基底にまとめられたOTOCを第二レニイエントロピー(Renyi entropy)に関連付ける定理である。関係作用素の小さな集合に対する和は、エントロピーの非常によい近似を得るのに十分であることを示す。逆に、これは複雑性の別の自然な指標、すなわち時間と関連する演算子の数のスケーリングを提供する。
論文参考訳（メタデータ） (2020-07-31T19:23:26Z)
From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。 8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
論文参考訳（メタデータ） (2020-06-05T10:56:52Z)

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