arXiv:2610.12008v1 cs.AI

유한 논증 프레임워크에서 기저 의미론과 선호 의미론의 복잡도

Complexity of Grounded Semantics and Preferred Semantics in Finitary Argumentation Frameworks

Jinfan Xu, Jieting Luo

제출 2026-10-08

저자 비고

arXiv Comments

15 pages

한국어 초록

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 원문에서 확인하세요.

  1. arXiv:2610.12008v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.