A Comprehensive Analysis of the cf2 Argumentation Semantics: From Characterization to Implementation

Sarah Alice GagglSarah Alice Gaggl

Sarah Alice Gaggl
A Comprehensive Analysis of the cf2 Argumentation Semantics: From Characterization to Implementation
Phd thesis, TU Wien, 2013/03/04

Details
Bibtex

KurzfassungAbstract
Argumentation is one of the major fields in Artificial Intelligence (AI). Numerous applications in diverse domains like legal reasoning, multi-agent systems, social networks, e-government, decision support and many more make this topic very interdisciplinary and lead to a wide range of different formalizations. Out of them the concept of abstract Argumentation Frameworks (AFs) is one of the most popular approaches to capture certain aspects of argumentation. This very simple yet expressive model has been introduced by Phan Minh Dung in 1995. Arguments and a binary attack relation between them, denoting conflicts, are the only components one needs for the representation of a wide range of problems and the reasoning therein.
Nowadays numerous semantics exist to solve the inherent conflicts between the arguments by selecting sets of “acceptable” arguments. Depending on the application, acceptability is defined in different ways. Some semantics are based on the idea to defend arguments against attacks, while others treat arguments like different choices and the solutions stand for consistent sets of arguments. A systematic analysis of these semantics on a theoretical and practical level is indispensable for the development of competitive systems. This includes a complete complexity analysis to develop appropriate algorithms and systems, the verification of the behavior on concrete instances as well as the identification of possible redundancies for specific semantics to simplify the frameworks. In this thesis we exemplify such an analysis on the cf2 semantics which does not require to defend arguments against attacks but is based on a decomposition of the framework along its strongly connected components (SCCs). This allows to treat cycles in a more sensitive way than others and to overcome some problems which arise with odd- and even-length cycles. Due to the quite complicated definition of this semantics it has not been studied very intensively.
To facilitate further investigation steps we first introduce an alternative characterization of the cf2 semantics. Then we propose a small modification of this semantics to overcome a particular problematic behavior on specific instances which results in the sibling semantics stage2 . After a complete complexity analysis and the investigation of equivalences for these two semantics, we apply the obtained results on two different implementation methods, namely the reduction-based approach of answer-set programming and the direct implementation in terms of labeling-based algorithms.
Forschungsgruppe:Research Group: Computational LogicComputational Logic, Logische Programmierung und ArgumentationLogic Programming and Argumentation

@phdthesis{G2013,
  author = {Sarah Alice Gaggl},
  title  = {A Comprehensive Analysis of the cf2 Argumentation Semantics: From
            Characterization to Implementation},
  school = {TU Wien},
  year   = {2013}
}