A logical encoding for \(k\)-\(m\)-realization of extensions in abstract argumentation (Q6179525)

The paper is based on the notion of an \textit{argumentation framework} (AF), as defined in [\textit{P. M. Dung}, Artif. Intell. 77, No. 2, 321--357 (1995; Zbl 1013.68556)], namely, as a directed graph \(\mathcal F=(\mathcal A, \mathcal R)\); the members of \(\mathcal A\) are called \textit{arguments} and \(\mathcal R\) is referred to as the \textit{attack relation}, a member of \(a\) of \(\mathcal A\) being said to attack a member \(b\) of \(\mathcal A\) if \(\mathcal R(a,b)\) holds. Say that a subset \(S\) of \(\mathcal A\) is \textit{conflict-free} if or all \(a,b\in S\), \({\mathcal R}(a,b)\) does not hold, and that it \textit{defends} an argument \(c\) if for all \(b\in\mathcal A\setminus S\) such that \(\mathcal R(b,c)\) holds, there exists \(a\in S\) such that \({\mathcal R}(a,b)\) holds. The author reminds the reader of the definition of two semantics: a subset \(S\) of \(\mathcal A\) \begin{itemize} \item belongs to the set \(\mathrm{st}(\mathcal F)\) of \textit{stable extensions} of \(\mathcal F\) if \(S\) is conflict free and for all \(b\in\mathcal A\setminus S\), there exists \(a\in S\) such that \({\mathcal R}(a,b)\) holds; \item belongs to the set \(\mathrm{co}(\mathcal F)\) of \textit{complete extensions} of \(\mathcal F\) if \(S\) is conflict-free, \(S\) defends all its elements, and \(S\) contains every argument it defends. \end{itemize} With \(\sigma\) being either st or co, the paper generalises the question, expressed in [\textit{P. E. Dunne} et al., Artif. Intell. 228, 153--178 (2015; Zbl 1346.68184)], of whether a set \(\mathbb S\) of subsets of \(\mathcal A\) is \textit{\(\sigma\)-realisable}, in the sense that there exists an AF \(\mathcal F\) such that \(\mathrm{st}(\mathcal F)=\mathbb S\), by considering two parameters: \begin{itemize} \item a natural number \(k\) meant to fix the number of extra arguments to be found in \(\mathcal F\) besides those that occur in \(\mathbb S\) (simple \(\sigma\)-realisability lets \(k\) be arbitrary); \item a natural number \(m\) meant to let \(\mathbb S\) be \(\sigma\)-realised by \(m\) AFs rather than only one, thanks to the existence of AFs \(\mathcal F_1\), \dots, \(\mathcal F_m\) such that \(\bigcup_{i=1}^m\sigma(\mathcal F_i)=\mathbb S\). \end{itemize} The key point of the paper is that these questions can be formalised in the form of Quantified Boolean Formulas (QBF), which can then be fed to QBF solvers to not only find out wether a solution exists, but also to compute solutions. Still, no experiment is reported in the paper, which essentially consists of the formalisation of the relevant QBFs, naturally derived from the definitions, making use of Boolean variables of the form \(\mathit{in}_a\) to express that \(a\) is one of the arguments of a target solution, and Boolean variables of the form \(\mathit{att}_{a,b}\) to express that argument \(a\) attacks argument \(b\) in a target solution. The paper ends with a last definition, for a further generalisation where the reported solutions are required to be as close as possible to a given AF \(\mathcal F^\star\) (letting the cardinality of the symmetric difference between the attack relation of \(\mathcal F^\star\) and the attack relation of an AF \(\mathcal F\) measure the distance between \(\mathcal F\) and \(\mathcal F^\star\)). For the entire collection see [Zbl 1528.03006].