Epistemic Abstract Argumentation Framework: Formal Foundations, Computation and Complexity

Dung's Abstract Argumentation Framework (AAF) has emerged as a central formalism in AI for modeling disputes among agents. In this paper, we introduce an extension of Dung's framework, called Epistemic Abstract Argumentation Framework (EAAF), which enhances AAF by allowing the representation of some pieces of epistemic knowledge. We generalize the concept of attack in AAF, introducing strong and weak epistemic attacks in EAAF, whose intuitive meaning is that an attacked argument is epistemically accepted only if the attacking argument is possibly or certainly rejected, respectively. We provide an intuitive semantics for EAAF that naturally extends that for AAF, and give an algorithm that enables the computation of epistemic extensions by using AAF-solvers. Finally, we analyze the complexity of the following argumentation problems: verification, i.e. checking whether a set of arguments is an epistemic extension; existence, i.e. checking whether there is at least one (non-empty) epistemic extension; and acceptance, i.e. checking whether an argument is epistemically accepted, under well-known argumentation semantics (i.e. grounded, complete, and preferred).