Search papers, labs, and topics across Lattice.
This paper investigates the computational complexity of determining argument strength within the discussion-based semantics of Amgoud and Ben-Naim. It demonstrates that deciding whether argument 'a' is stronger than argument 'b' is solvable in polynomial time. The key insight involves framing the problem as comparing the number of walks of each length ending at two vertices in a graph, which is then reduced to the equivalence problem for semiring automata.
Ranking arguments based on discussion semantics, previously an open question for computational complexity, can now be done in polynomial time.
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.
