On the Complexity of the Discussion-based Semantics in Abstract Argumentation
For researchers in abstract argumentation, this provides a polynomial-time algorithm for a previously open complexity problem, though the result is incremental.
The paper proves that deciding argument strength under discussion-based semantics is polynomial-time decidable, reducing it to semiring automata equivalence. This resolves a complexity question for ranking semantics.
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.