On the Complexity of the Discussion-based Semantics in Abstract Argumentation
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Discussion Graph Semantics of First-Order Logic with Equality for Reasoning about Discussion and Argumentation
We formulate discussion graph semantics of first-order logic with equality for reasoning about discussion and argumentation as naturally as we would reason about sentences. While there are a few existing proposals to use…
Formal LogicCounting Complexity for Reasoning in Abstract Argumentation
In this paper, we consider counting and projected model counting of extensions in abstract argumentation for various semantics. When asking for projected counts we are interested in counting the number of extensions of a…
Abstract ArgumentationThe Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation
We study the computational complexity of problems that arise in abstract argumentation in the context of dynamic argumentation, minimal change, and aggregation. In particular, we consider the following problems where alw…
Abstract ArgumentationNon-flat ABA is an Instance of Bipolar Argumentation
Assumption-based Argumentation (ABA) is a well-known structured argumentation formalism, whereby arguments and attacks between them are drawn from rules, defeasible assumptions and their contraries. A common restriction …
Abstract ArgumentationRanking-based Argumentation Semantics Applied to Logical Argumentation (full version)
In formal argumentation, a distinction can be made between extension-based semantics, where sets of arguments are either (jointly) accepted or not, and ranking-based semantics, where grades of acceptability are assigned …
Abstract Argumentation