In this paper we discuss Incomplete Bipolar Argumentation Frameworks (iBAFs) proposed in [1]. iBAFs are the extension of Dung's Abstract Argumentation Frameworks (AAFs) allowing the simultaneous presence of supports (borrowed from BAFs - Bipolar AAFs) and of uncertain elements of the argumentation graph (borrowed from iAAFs - incomplete AAFs). We discuss the computational complexity of verification problem (under the possible perspective) and the acceptance problem, by showing how it varies depending on the semantics of supports and the semantics of extensions. On the one hand, we show that adding supports on top of incompleteness does not affect the complexity of the acceptance. On the other hand, surprisingly, we show that the joint use of bipolarity and incompleteness has a deep impact on the complexity of the verification: for the semantics under which the verification over AAFs is polynomialtime solvable, although moving from AAFs to BAFs or to iAAFs does not change the complexity, the complexity of the verification over iBAFs may increase up to NP-complete.
On Merging Incompleteness and Bipolarity in Abstract Argumentation
Fazzinga B.;Flesca S.;Furfaro F.;Monterosso G.
2023-01-01
Abstract
In this paper we discuss Incomplete Bipolar Argumentation Frameworks (iBAFs) proposed in [1]. iBAFs are the extension of Dung's Abstract Argumentation Frameworks (AAFs) allowing the simultaneous presence of supports (borrowed from BAFs - Bipolar AAFs) and of uncertain elements of the argumentation graph (borrowed from iAAFs - incomplete AAFs). We discuss the computational complexity of verification problem (under the possible perspective) and the acceptance problem, by showing how it varies depending on the semantics of supports and the semantics of extensions. On the one hand, we show that adding supports on top of incompleteness does not affect the complexity of the acceptance. On the other hand, surprisingly, we show that the joint use of bipolarity and incompleteness has a deep impact on the complexity of the verification: for the semantics under which the verification over AAFs is polynomialtime solvable, although moving from AAFs to BAFs or to iAAFs does not change the complexity, the complexity of the verification over iBAFs may increase up to NP-complete.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.