An Efficient Algorithm for Skeptical Preferred Acceptancein Dynamic Argumentation Frameworks
Abstract
Though there has been an extensive body of work
on efficiently solving computational problems for
static Dung’s argumentation frameworks (AFs), little work has been done for handling dynamic AFs
and in particular for deciding the skeptical acceptance of a given argument. In this paper we devise
an efficient algorithm for computing the skeptical
preferred acceptance in dynamic AFs. More specifically, we investigate how the skeptical acceptance
of an argument (goal) evolves when the given AF is
updated and propose an efficient algorithm for solving this problem. Our algorithm, called SPA, relies
on two main ideas: i) computing a small portion of
the input AF, called “context-based” AF, which is
sufficient to determine the status of the goal in the
updated AF, and ii) incrementally computing the
ideal extension to further restrict the context-based
AF. We experimentally show that SPA significantly
outperforms the computation from scratch, and that
the overhead of incrementally maintaining the ideal
extension pays off as it speeds up the computation