pith. sign in

arxiv: 2604.11480 · v2 · submitted 2026-04-13 · 💻 cs.AI

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

Lydia Bl\"umel , Kai Sauerwald , Kenneth Skiba , Matthias Thimm This is my paper

Pith reviewed 2026-05-10 16:30 UTC · model grok-4.3

classification 💻 cs.AI
keywords abstract argumentationranking semanticsdiscussion-based semanticscomputational complexitysemiring automatawalk countingpolynomial time
0
0 comments X

The pith

Deciding whether one argument is stronger than another under discussion-based semantics is possible in polynomial time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that the strength comparison problem for the discussion-based semantics of Amgoud and Ben-Naim reduces to checking whether two vertices in a directed graph have exactly the same number of walks of every finite length ending at them. This graph problem is then solved by reducing it to the equivalence problem for semiring automata, which admits a polynomial-time decision procedure. A reader would care because ranking semantics in abstract argumentation have mostly unknown or high computational complexity, and this result places one concrete semantics in P.

Core claim

The authors prove that, for the discussion-based semantics, argument a is stronger than argument b if and only if the two corresponding vertices have identical numbers of walks of each length; they establish this equivalence and then reduce the resulting walk-count equality problem to semiring automata equivalence, which is known to be solvable in polynomial time.

What carries the argument

Reduction of walk-count equality between two vertices to equivalence testing of semiring automata over the appropriate semiring of walk enumerations.

If this is right

  • The strength comparison problem for this semantics lies in P.
  • The same reduction technique supplies an explicit polynomial-time algorithm via automata construction.
  • The result gives a new, automata-theoretic lens on the complexity of ranking semantics in general.
  • Other walk-based ranking methods may admit similar polynomial-time comparisons.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same automata reduction might be lifted to decide other properties expressible by regular walk languages.
  • Implementation of the semiring automata construction would allow direct empirical checks on large argumentation frameworks.
  • If other ranking semantics can be shown to reduce to comparable walk or path-count problems, their complexity might also fall into P.

Load-bearing premise

The strength ordering of the discussion-based semantics is exactly captured by equality of the number of walks of each length ending at the two arguments.

What would settle it

A concrete pair of arguments in a small attack graph where the two vertices have identical walk counts of every length yet receive different strength values according to the definition of the semantics.

Figures

Figures reproduced from arXiv: 2604.11480 by Kai Sauerwald, Kenneth Skiba, Lydia Bl\"umel, Matthias Thimm.

Figure 1
Figure 1. Figure 1: AAF F1 from Example 3.5 and the respective discussion count until 3. a b c d e f g x Dis1(x) Dis2(x) Dis3(x) a −2 4 −4 b −2 2 −4 c −2 2 −4 d −1 2 −4 e −1 2 −4 f −1 2 −4 g −1 2 −4 [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 4
Figure 4. Figure 4: Automata Aa and Ah (left) and the linear representation ⟨α−, M−, η−⟩ of the automaton A− (right) from Example 7.2. Left side: An edge with label s: 1 indicates that transitioning from the source to the target when reading s has weight 1. Edges with weight zero are omitted. Initial weights and final weights of the states are not explicitly represented; each state has an initial weight of 1, and each state h… view at source ↗
Figure 5
Figure 5. Figure 5: AAF F4 from Example 7.5 and its adjacency matrix. Algorithm 2: Algorithm for deciding EQUIVDIS. Input: AAF F = (A, R) and arguments a, b ∈ A. Output: Yes, if a ≃dbs F b holds; otherwise, No. i ← 1; M ← AdjacencyMatrix(F); while i ≤ 2|A| − 1 do // Theorem 7.3 if M[b] ̸= M[a] then return No; M ← M · AdjacencyMatrix(F) ; // Mi+1 i ← i + 1; return Yes; integers, which is also in PTIME [Béal et al., 2005]. Howe… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that deciding whether argument a is stronger than argument b under the discussion-based semantics of Amgoud and Ben-Naim is in P. The central reduction shows that strength comparison is equivalent to equality of the sequences counting walks of each length ending at the two vertices; this is then reduced to equivalence of N-weighted automata (states = arguments, transitions = edges weighted 1), whose equivalence is solvable in polynomial time via iterative linear-algebraic comparison of the generated power series.

Significance. If the result holds, it supplies a concrete polynomial-time algorithm for one ranking semantics whose complexity was previously open, using a standard linear-size automata construction with no exponential blowup. The approach leverages independently known results on semiring automata equivalence (via Hankel-matrix rank or simultaneous minimization) and thereby gives a new automata-theoretic perspective on the complexity landscape of argumentation semantics. The reduction is direct and preserves the exact walk-count semantics without hidden parameters or circularity.

minor comments (2)
  1. §2: the precise inductive definition of the discussion-based strength ordering (Amgoud & Ben-Naim) is referenced but not restated; adding a short self-contained paragraph would improve readability for readers outside the immediate sub-area.
  2. §4, after the automata construction: the claim that the reduction is 'linear size' is correct but would benefit from an explicit statement of the state and transition cardinalities in terms of |A| and |R|.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The summary accurately captures the main contribution: a direct polynomial-time reduction from strength comparison under discussion-based semantics to equivalence of N-weighted automata.

Circularity Check

0 steps flagged

No significant circularity; derivation reduces to external automata result

full rationale

The paper's central claim is that strength comparison under the discussion-based semantics reduces to checking equality of per-length walk counts between two vertices, which is then reduced via a standard linear-size construction to the equivalence problem for semiring automata (known to be in P by independent automata-theoretic results). No step equates a derived quantity to its own fitted input, renames a known pattern, or relies on a load-bearing self-citation whose content is unverified; the cited definition originates from Amgoud and Ben-Naim (distinct authors) and the automata equivalence is an external, previously established fact. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard definition of discussion-based semantics as walk counting and on established results about semiring automata equivalence; no free parameters or invented entities are introduced.

axioms (2)
  • domain assumption Discussion-based semantics strength is defined by equality of walk counts of each length
    Invoked in the abstract as the core of the problem
  • standard math Equivalence of semiring automata is decidable in polynomial time
    Cited result from automata theory used for the reduction

pith-pipeline@v0.9.0 · 5390 in / 1169 out tokens · 48093 ms · 2026-05-10T16:30:11.909754+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    Ranking-based semantics for argumentation frameworks

    [Amgoud and Ben-Naim, 2013] Leila Amgoud and Jonathan Ben-Naim. Ranking-based semantics for argumentation frameworks. In Weiru Liu, V . S. Subrahmanian, and Jef Wijsen, editors,Proceedings of the Seventh International Conference on Scalable Uncertainty Management, SUM 2013, Washington, DC, USA, September 16-18, 2013, vol- ume 8078 ofLecture Notes in Compu...

    work page 2013

  2. [2]

    Computational Complexity - A Modern Approach

    [Arora and Barak, 2009] Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cam- bridge University Press,

    work page 2009

  3. [3]

    From fine-grained properties to broad prin- ciples for gradual argumentation: A principled spectrum

    [Baroniet al., 2019 ] Pietro Baroni, Antonio Rago, and Francesca Toni. From fine-grained properties to broad prin- ciples for gradual argumentation: A principled spectrum. Int. J. Approx. Reason., 105:252–286,

    work page 2019

  4. [4]

    On the equivalence of Z-automata

    8 [Béalet al., 2005 ] Marie-Pierre Béal, Sylvain Lombardy, and Jacques Sakarovitch. On the equivalence of Z-automata. In Luís Caires, Giuseppe F. Italiano, Luís Monteiro, Catuscia Palamidessi, and Moti Yung, editors,Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, volume 3580 ...

    work page 2005

  5. [5]

    Springer,

    [Berstel and Reutenauer, 1988] Jean Berstel and Christophe Reutenauer.Rational series and their languages, volume 12 ofEATCS monographs on theoretical computer science. Springer,

    work page 1988

  6. [6]

    A ranking semantics for abstract argumentation based on serialisability

    [Blümel and Thimm, 2022] Lydia Blümel and Matthias Thimm. A ranking semantics for abstract argumentation based on serialisability. InProceedings of the 9th Interna- tional Conference on Computational Models of Argument (COMMA’22), September

    work page 2022

  7. [7]

    Argumentation ranking semantics based on propagation

    [Bonzonet al., 2016a ] Elise Bonzon, Jerome Delobelle, Se- bastien Konieczny, and Nicolas Maudet. Argumentation ranking semantics based on propagation. InProceedings of the 6th International Conference on Computational Models of Argument (COMMA-2016),

    work page 2016

  8. [8]

    Combining extension-based semantics and ranking-based semantics for abstract argumentation

    [Bonzonet al., 2018 ] Elise Bonzon, Jerome Delobelle, Se- bastien Konieczny, and Nicolas Maudet. Combining extension-based semantics and ranking-based semantics for abstract argumentation. InProceedings of the Sixteenth International Conference on Principles of Knowledge Rep- resentation and Reasoning (KR 2018),

    work page 2018

  9. [9]

    An empirical and axiomatic comparison of ranking-based semantics for abstract argumentation.Journal of Applied Non-Classical Logics, 33(3–4):328–386,

    [Bonzonet al., 2023 ] Elise Bonzon, Jérôme Delobelle, Sébastien Konieczny, and Nicolas Maudet. An empirical and axiomatic comparison of ranking-based semantics for abstract argumentation.Journal of Applied Non-Classical Logics, 33(3–4):328–386,

    work page 2023

  10. [10]

    Graduality in argumen- tation.Journal of Artificial Intelligence Research, 23:245– 297,

    [Cayrol and Lagasquie-Schiex, 2005] Claudette Cayrol and Marie-Christine Lagasquie-Schiex. Graduality in argumen- tation.Journal of Artificial Intelligence Research, 23:245– 297,

    work page 2005

  11. [11]

    PhD thesis, Centre de Recherche en Informatique de Lens,

    [Delobelle, 2017] Jerome Delobelle.Ranking-based Seman- tics for Abstract Argumentation. PhD thesis, Centre de Recherche en Informatique de Lens,

    work page 2017

  12. [12]

    Ranking semantics based on subgraphs analysis

    [Dondio, 2018] Pierpaolo Dondio. Ranking semantics based on subgraphs analysis. InProceedings of the 17th Interna- tional Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018),

    work page 2018

  13. [13]

    On the acceptability of argu- ments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games.Artificial Intelli- gence, 77(2):321–358,

    [Dung, 1995] Phan Minh Dung. On the acceptability of argu- ments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games.Artificial Intelli- gence, 77(2):321–358,

    work page 1995

  14. [14]

    Systems of distinct repre- sentatives and linear algebra.Journal of Research of the National Bureau of Standards, 71B(4):241–245,

    [Edmonds, 1967] Jack Edmonds. Systems of distinct repre- sentatives and linear algebra.Journal of Research of the National Bureau of Standards, 71B(4):241–245,

    work page 1967

  15. [15]

    Simulation vs

    [Ésik and Maletti, 2010] Zoltán Ésik and Andreas Maletti. Simulation vs. equivalence. In Hamid R. Arabnia, George A. Gravvanis, and Ashu M. G. Solo, editors,Pro- ceedings of the 2010 International Conference on Founda- tions of Computer Science, FCS 2010, July 12-15, 2010, Las Vegas, Nevada, USA, pages 119–124. CSREA Press,

    work page 2010

  16. [16]

    Cambridge University Press,

    [Flajolet and Sedgewick, 2009] Philippe Flajolet and Robert Sedgewick.Analytic Combinatorics. Cambridge University Press,

    work page 2009

  17. [17]

    On the graded acceptability of arguments in abstract and instantiated argumentation.Artificial Intelligence, 275:138– 173, October

    [Grossi and Modgil, 2019] Davide Grossi and Sanjay Modgil. On the graded acceptability of arguments in abstract and instantiated argumentation.Artificial Intelligence, 275:138– 173, October

    work page 2019

  18. [18]

    Hopcroft, Rajeev Motwani, and Jeffrey D

    [Hopcroftet al., 2007 ] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman.Introduction to automata theory, languages, and computation, 3rd Edition. Pearson interna- tional edition. Addison-Wesley,

    work page 2007

  19. [19]

    Notes on equivalence and min- imization of weighted automata.CoRR, abs/2009.01217,

    [Kiefer, 2020] Stefan Kiefer. Notes on equivalence and min- imization of weighted automata.CoRR, abs/2009.01217,

    work page arXiv 2020

  20. [20]

    Argument, i choose you! preferences and ranking seman- tics in abstract argumentation

    [Mailly and Rossit, 2020] Jean-Guy Mailly and Julien Rossit. Argument, i choose you! preferences and ranking seman- tics in abstract argumentation. InProceedings of the 17th International Conference on Principles of Knowledge Rep- resentation and Reasoning (KR’20),

    work page 2020

  21. [21]

    Open-mindedness of gradual ar- gumentation semantics

    [Potyka, 2019] Nico Potyka. Open-mindedness of gradual ar- gumentation semantics. In Nahla Ben Amor, Benjamin Qu- ost, and Martin Theobald, editors,Proceedings of the 13th International Conference on Scalable Uncertainty Man- agement (SUM’19), volume 11940 ofLecture Notes in Computer Science, pages 236–249. Springer,

    work page 2019

  22. [22]

    Rabin and Dana Scott

    [Rabin and Scott, 1959] Michael O. Rabin and Dana Scott. Finite automata and their decision problems.IBM Journal of Research and Development, 3(2):114–125,

    work page 1959

  23. [23]

    Springer Berlin Heidelberg, Berlin, Heidelberg,

    [Sakarovitch, 2009] Jacques Sakarovitch.Rational and Recognisable Power Series, pages 105–174. Springer Berlin Heidelberg, Berlin, Heidelberg,

    work page 2009

  24. [24]

    Texts and Monographs in Computer Science

    [Salomaa and Soittola, 1978] Arto Salomaa and Matti Soit- tola.Automata-Theoretic Aspects of Formal Power Se- ries. Texts and Monographs in Computer Science. Springer,

    work page 1978

  25. [25]

    On the definition of a family of automata.Inf

    [Schützenberger, 1961] Marcel Paul Schützenberger. On the definition of a family of automata.Inf. Control., 4(2-3):245– 270,

    work page 1961

  26. [26]

    Towards ranking-based semantics for abstract argumentation using conditional logic semantics

    [Skiba and Thimm, 2020] Kenneth Skiba and Matthias Thimm. Towards ranking-based semantics for abstract argumentation using conditional logic semantics. InPro- ceedings of the International Workshop on Computational Argumentation and Cognition (COGNITAR’20), August

    work page 2020

  27. [27]

    Rank- ing extensions in abstract argumentation

    [Skibaet al., 2021 ] Kenneth Skiba, Tjitze Rienstra, Matthias Thimm, Jesse Heyninck, and Gabriele Kern-Isberner. Rank- ing extensions in abstract argumentation. In Zhi-Hua Zhou, 9 editor,Proceedings of the 30th International Joint Con- ference on Artificial Intelligence (IJCAI’21), pages 2047– 2053, August

    work page 2021

  28. [28]

    Stockmeyer and Al- bert R

    [Stockmeyer and Meyer, 1973] Larry J. Stockmeyer and Al- bert R. Meyer. Word problems requiring exponential time: Preliminary report. In Alfred V . Aho, Allan Borodin, Robert L. Constable, Robert W. Floyd, Michael A. Har- rison, Richard M. Karp, and H. Raymond Strong, editors, Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30 - ...

    work page 1973

  29. [29]

    Gaussian elimination is not optimal.Numer

    [Strassen, 1969] V olker Strassen. Gaussian elimination is not optimal.Numer. Math. (Heidelb.), 13(4):354–356, August

    work page 1969

  30. [30]

    Probabilistic graded semantics

    [Thimmet al., 2018 ] Matthias Thimm, Federico Cerutti, and Tjitze Rienstra. Probabilistic graded semantics. In Sanjay Modgil, Katarzyna Budzynska, and John Lawrence, editors, Proceedings of the Seventh International Conference on Computational Models of Argumentation (COMMA’18), volume 305 ofFrontiers in Artificial Intelligence and Ap- plications, pages 3...

    work page 2018

  31. [31]

    Computing Supple- menta

    [Tinhoferet al., 1990 ] Gottfried Tinhofer, Rudolf Albrecht, Ernst Mayr, Hartmut Noltemeier, and Maciej M Syslo, editors.Computational Graph Theory. Computing Supple- menta. Springer, Vienna, Austria, April

    work page 1990

  32. [32]

    On path equivalence of non- deterministic finite automata.Inf

    [Tzeng, 1996] Wen-Guey Tzeng. On path equivalence of non- deterministic finite automata.Inf. Process. Lett., 58(1):43– 46,

    work page 1996

  33. [33]

    Explaining arguments’ strength: Unveiling the role of attacks and supports

    [Yinet al., 2024 ] Xiang Yin, Nico Potyka, and Francesca Toni. Explaining arguments’ strength: Unveiling the role of attacks and supports. InProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI 2024, Jeju, South Korea, August 3-9, 2024, pages 3622–3630. ijcai.org,

    work page 2024

  34. [34]

    Viewpoints using ranking- based argumentation semantics

    [Yunet al., 2018 ] Bruno Yun, Srdjan Vesic, Madalina Croitoru, and Pierre Bisquert. Viewpoints using ranking- based argumentation semantics. InProceedings of the 7th International Conference on Computational Models of Ar- gumentation (COMMA’18),

    work page 2018