An Efficient Algorithm for Computing the Set of Semi-stable Extensions

Argumentation is one of the most relevant fields in the sphere of Artificial Intelligence. In particular, Dung’s abstract argumentation framework (AF) has received much attention in the last twenty years, and many computational issues have been investigated for different argumentation semantics. Specifically, enumerating the sets of arguments prescribed by an argumentation semantics (i.e., extensions) is arguably one of the most challenging problems for AFs, and this is the case also for the well-known semi-stable semantics. In this paper, we propose an algorithm for efficiently computing the set of semi-stable extensions of a given AF. Our technique relies on exploiting the computation of grounded extension to snip some arguments in order to obtain a smaller framework (called cut-AF) over which state-of-the-art solvers for enumerating the semi-stable extensions are called, as needed to return the extensions of the input AF. We experimentally evaluated our technique and found that our approach is orders of magnitude faster than the computation over the whole AF.