cs.AI · 2604.11480 Copy arXiv ID · Apr 13, 2026 Save On the Complexity of the Discussion-based Semantics in Abstract Argumentation Authors: Lydia Blümel , Kai Sauerwald , Kenneth Skiba , Matthias Thimm
Organizations: University of Hagen · University of Luxembourg
In 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.
More in this topic Computational argumentation studies how to represent, analyze, and apply arguments and their relationships using formal and computational methods.
See all 99 papers → Also in May 3, 2026 · Uri Andrews, Luca San Mauro, John Spoerl Computational Argumentation
Department of Mathematics, University of Wisconsin–Madison · Dipartimento di Ricerca e Innovazione Umanistica, University of Bari, Italy
Oct 8, 2026 · Jinfan Xu, Jieting Luo Computational Argumentation
School of Philosophy, Zhejiang University
Oct 19, 2026 · Yan Zhang, Kehan Liu Computational Argumentation
May 3, 2026 J/K move · Enter open · S save
Uri Andrews, Luca San Mauro, John Spoerl
Department of Mathematics, University of Wisconsin–Madison · Dipartimento di Ricerca e Innovazione Umanistica, University of Bari, Italy
In Dung-style abstract argumentation, various semantics capture notions of acceptability of arguments. The admissibility semantics capture the notion that an argument can be consistently defended from any potential counterargument. Weak semantics often relax the demands of admissibility by restricting which counterarguments must be taken seriously (e.g., discounting self-defeating or otherwise incoherent attacks). Many prominent proposals for weak semantics remain extension-based in a stronger sense. While these semantics discount attacks from arguments which are considered unreasonable, they still require a uniform defense against all reasonable arguments, even if they are collectively inconsistent. This uniformity can be too demanding when defensibility is inherently strategic, and thus the appropriate reply depends on the opponent's line of attack. We introduce tenability, a family of dialogue-based semantics that formalize when a designated argument (or a set of arguments) can be maintained in debate by a proponent against any conflict-free attack which the opponent may present. The approach is motivated by three natural benchmark patterns: self-defeating attack, floating assignment, and disjunctive reinstatement, on which tenability behaves differently from all weak semantics previously considered in the literature. We define three variants -- static tenability, tenability, and strong tenability -- via monotone commitment games over finite conflict-free moves, differing in the obligations imposed on the disputants. We establish the relative strength of these notions, prove implications and separations with previously studied weak semantics, and we analyze computational complexity on finite frameworks: deciding static tenability is
Π 2 P Π^P_2 Π 2 P -complete, while deciding tenability and strong tenability is PSPACE-complete.