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

Created by

Haebom

저자

Lydia Blumel, Kai Sauerwald, Kenneth Skiba, Matthias Thimm

💡 개요

본 논문은 Amgoud와 Ben-Naim의 토론 기반 의미론(discussion-based semantics) 하에서 두 주장 a와 b의 상대적 강도를 결정하는 문제가 다항 시간 안에 해결 가능함을 증명합니다. 이 문제는 그래프에서 특정 길이의 모든 종료점을 가진 워크(walk)의 수가 같은지를 판별하는 문제로 귀결됩니다. 이를 위해 자동자 이론의 결과를 활용하여 해당 문제를 준환형 자동자(semiring automata)의 동치성 문제로 축소합니다.

🔑 시사점 및 한계

•

기존에 복잡성 분석이 미흡했던 랭킹 의미론(ranking semantics) 분야에 대한 새로운 계산 복잡성 관점을 제시합니다.

•

토론 기반 의미론에서 두 주장의 상대적 강도 결정 문제를 효율적으로 해결할 수 있는 알고리즘적 기반을 마련합니다.

•

본 연구에서 제시된 준환형 자동자 기반의 접근 방식은 향후 다른 랭킹 의미론의 복잡성 분석에도 확장될 수 있는 가능성을 시사합니다.

•

현재 연구는 두 주장 간의 상대적 강도 결정에 집중하고 있으며, 전체 주장 집합에 대한 복잡성 분석은 추가 연구가 필요합니다.

PDF 보기

Made with Slashpage