유한 논증 프레임워크에서 기저 의미론과 선호 의미론의 복잡도
Complexity of Grounded Semantics and Preferred Semantics in Finitary Argumentation Frameworks
한국어 초록
Dung이 도입한 추상 논증 프레임워크(AF)는 인공지능에서 비단조 추론(non-monotonic reasoning)을 위한 형식적 기초를 제공합니다. 일반적인 무한 AF에 대한 결정 문제(decision problem)는 통상 해석적 위계(analytical hierarchy)의 높은 수준($Σ_1^1$ 또는 $Π_1^1$)에 속하지만, 프레임워크를 계산 가능하게 유한(computably finitary)하도록 제한하면 일부 복잡도를 산술적 위계(arithmetical hierarchy) 수준으로 낮출 수 있습니다. 본 논문에서는 계산 가능하게 유한한 AF에서 기저 의미론(grounded semantics)과 선호 의미론(preferred semantics)에 대해 표준적인 결정 문제들, 즉 신뢰적 수용($\Cred$), 회의적 수용($\Skep$), 확장 존재성($\Ex$), 유일성($\Uni$), 비공집합 존재성($\NE$) 전반에 걸친 복잡도 매핑을 제시합니다. 기저 의미론의 경우 신뢰적 수용과 회의적 수용은 이미 $Σ_1^0$-완전(complete)임이 알려져 있습니다. 본 연구에서는 비공집합 존재성 역시 $Σ_1^0$-완전인 반면, 존재성과 유일성은 자명(trivial)함을 보입니다. 이러한 분류는 유효한 계산 가능 유한 표현의 영역 내에서 이해됩니다. 선호 의미론의 경우, 계산 가능 유한 분기 계산 트리를 사용하여 $\Cred_{\pref}$는 $Π_1^0$-완전이고 $\NE_{\pref}$는 $Σ_2^0$-완전임을 보입니다. 그러나 이는 보편 양화(universal quantification)와 대역적 유일성을 줄이기에는 충분하지 않아, $\Skep_{\pref}$는 $Π_1^1$에 남고 $\UniPref$는 $Σ_2^1$-완전으로 남게 됩니다. 본 결과는 유한성이 추론 복잡도를 산술적 위계로 낮추는 데 성공하는 지점과, 2차 양화가 문제를 다시 해석적 위계로 밀어올리는 정확한 경계를 보여줍니다.
원문 초록
Abstract argumentation frameworks (AFs) introduced by Dung provide a formal foundation for non-monotonic reasoning in artificial intelligence. While decision problems for general infinite AFs typically reside at high levels of the analytical hierarchy ($Σ_1^1$ or $Π_1^1$), restricting the framework to be computably finitary reduces some of the complexity to the arithmetical hierarchy. In this paper, we present a complexity mapping of grounded and preferred semantics in computably finitary AFs across standard decision problems: credulous acceptance ($\Cred$), skeptical acceptance ($\Skep$), extension existence ($\Ex$), uniqueness ($\Uni$), and non-empty existence ($\NE$). For grounded semantics, credulous and skeptical acceptance are already known to be $Σ_1^0$-complete. We show that non-empty existence is also $Σ_1^0$-complete, whereas existence and uniqueness are trivial. These classifications are understood within the domain of valid computably finitary representations. For preferred semantics, using a computably finitely branching computation tree, $\Cred_{\pref}$ is shown to be in $Π_1^0$-c and $\NE_{\pref}$ is $Σ_2^0$-c. However, it is insufficient to reduce universal quantification and global uniqueness, leaving $\Skep_{\pref}$ in $Π_1^1$ and $\UniPref$ in $Σ_2^1$-c. Our results show the precise boundary where finitarity succeeds to bring reasoning down to the arithmetical hierarchy and where second-order quantification forces problems back into the analytical hierarchy.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
15 pages