# On the Complexity of the Discussion-based Semantics in Abstract Argumentation

arXiv: https://arxiv.org/abs/2604.11480 · HTML: https://mlsanity.com/paper/2604.11480/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 35 references that are in the map.
- First posted on arXiv 13 Apr 2026.

## Builds on (most cited first, 4 of 4)

- [A Comparative Study of Ranking-based Semantics for Abstract Argumentation](https://mlsanity.com/paper/1602.01059/) (2016)
- [Explaining Arguments' Strength: Unveiling the Role of Attacks and Supports (Technical Report)](https://mlsanity.com/paper/2404.14304/) (2024)
- [On the Graded Acceptability of Arguments in Abstract and Instantiated Argumentation](https://mlsanity.com/paper/1811.03355/) (2018)
- [Towards Ranking-based Semantics for Abstract Argumentation using Conditional Logic Semantics](https://mlsanity.com/paper/2008.02735/) (2020)

## Abstract (arXiv)

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.