A Four-Label-Based Algorithm for Solving Stable Extension Enumeration in Abstract Argumentation Frameworks

Abstract

In abstract argumentation frameworks, the computation of stable extensions is an important semantic task for evaluating the acceptability of arguments. The current approaches for the computation of stable extensions are typically conducted through methodologies that are either label-based or extension-based. Label-based algorithms operate by assigning labels to each argument, thus reducing the attack relations between arguments to constraint relations among the labels. This paper analyzes the existing two-label and three-label enumeration algorithms for stable extensions through case studies. It is found that both the two-label and three-label algorithms are not precise enough in defining types of arguments. To address these issues, this paper proposes a four-label enumeration algorithm for stable extensions. This method introduces amust_in label to pre-mark certain in-type arguments, thereby achieving a finer classification of in-type arguments. This enhances the labelings’ propagation ability and reduces the algorithm’s search space. Our proposed four-label algorithm was tested on authoritative benchmark sets of abstract argumentation framework problems: ICCMA 2019, ICCMA 2021, and ICCMA 2023. Experimental results show that the four-label algorithm significantly improves solving efficiency compared to existing two-label and three-label algorithms. Additionally, ablation experiments confirm that both the four-label transition strategy and preprocessing strategy enhance the algorithm’s performance.

Keywords

• abstract argumentation framework
• labelings
• stable extensions
• depth-first search