pipette
ENEnglish

Complexity of Grounded Semantics and Preferred Semantics in Finitary Argumentation Frameworks

Jinfan Xu, Jieting Luo

Preprint

En palabras de los autores

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 ( or ), 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 (), skeptical acceptance (), extension existence (), uniqueness (), and non-empty existence (). For grounded semantics, credulous and skeptical acceptance are already known to be -complete. We show that non-empty existence is also -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, is shown to be in -c and is -c. However, it is insufficient to reduce universal quantification and global uniqueness, leaving in and in -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.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 15 pages