On the Complexity of the Discussion-based Semantics in Abstract Argumentation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910148386095104 |
|---|---|
| author | Blümel, Lydia Sauerwald, Kai Skiba, Kenneth Thimm, Matthias |
| author_facet | Blümel, Lydia Sauerwald, Kai Skiba, Kenneth Thimm, Matthias |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_11480 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Complexity of the Discussion-based Semantics in Abstract Argumentation Blümel, Lydia Sauerwald, Kai Skiba, Kenneth Thimm, Matthias Artificial Intelligence I.2.4 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. |
| title | On the Complexity of the Discussion-based Semantics in Abstract Argumentation |
| topic | Artificial Intelligence I.2.4 |
| url | https://arxiv.org/abs/2604.11480 |