Abstract argumentation frameworks (AFs) introduced by Dung provide a formal basis for non‑monotonic reasoning. For general infinite AFs most decision problems lie at high levels of the analytical hierarchy ($\Sigma_1^1$ or $\Pi_1^1$). When the framework is restricted to be computably finitary, many of these problems fall into the arithmetical hierarchy. This paper maps the complexity of grounded and preferred semantics in computably finitary AFs for the standard decision problems: credulous acceptance ($\Cred$), skeptical acceptance ($\Skep$), extension existence ($\Ex$), uniqueness ($\Uni$), and non‑empty existence ($\NE$).
For grounded semantics, $\Cred$ and $\Skep$ are already known to be $\Sigma_1^0$‑complete. We show that $\NE$ is also $\Sigma_1^0$‑complete, while $\Ex$ and $\Uni$ become trivial under valid computably finitary representations (always true or always false).
For preferred semantics, using a computably finitely branching computation tree we obtain $\Cred_{\pref}$ in $\Pi_1^0$‑c and $\NE_{\pref}$ in $\Sigma_2^0$‑c. However, universal quantification and global uniqueness cannot be reduced similarly, leaving $\Skep_{\pref}$ in $\Pi_1^1$ and $\Uni_{\pref}$ in $\Sigma_2^1$‑c. These results pinpoint the exact boundary where finitarity lowers reasoning to the arithmetical hierarchy and where second‑order quantification pushes problems back into the analytical hierarchy.
Review