证明了讨论式语义中论点强弱判断可在多项式时间内完成。
On the Complexity of the Discussion-based Semantics in Abstract Argumentation
- 将论点强弱问题转化为图中顶点走法数量是否相等
- 通过自动机理论将问题归约为半环自动机等价性判定
- 为排序语义复杂度研究提供了新思路，适合逻辑与计算复杂性研究者
我们证明，在Amgoud和Ben-Naim提出的讨论式语义下，判断论点a是否比论点b更强的问题可在多项式时间内求解。该问题的核心在于判断图中两个顶点在任意长度的路径终点出现次数是否相同。本文利用自动机理论，将此问题转化为半环自动机的等价性判定问题。这一方法为排序语义的计算复杂度研究提供了新视角，而目前许多语义的复杂度仍未知。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。