The complexity of the probabilistic counterparts of the classical verification and acceptance problems is investigated over probabilistic Abstract Argumentation Frameworks (prAAFs), in a setting more general than that considered in the current literature, where the complexity has been characterized only under the assumption of independence between arguments/defeats. The complexity of the problems is shown to range from FP to FP#P-complete, with FP‖NP-complete cases, depending on the semantics of the extensions, the representation paradigm used for encoding the prAAF, and the imposed correlations between arguments/defeats, thus providing a thorough analysis of the sensitivity to several aspects. In this regard, in order to allow the study of the impact of different forms of correlations between arguments/defeats on the complexity, a new form of prAAF is introduced, called GEN. It is based on the well-known paradigm of world-set descriptors and world-set sets for representing probabilities, and it allows the correlations to be easily and explicitly expressed. Interestingly, the introduction of GEN is shown to be also a standalone contribution as a powerful representation paradigm for prAAFs, owing to its high expressiveness, compactness, and the possibility to support user-friendly mechanisms for defining correlations.

Complexity of fundamental problems in probabilistic abstract argumentation: Beyond independence

Fazzinga, Bettina;Flesca, Sergio;Furfaro, Filippo
2019

Abstract

The complexity of the probabilistic counterparts of the classical verification and acceptance problems is investigated over probabilistic Abstract Argumentation Frameworks (prAAFs), in a setting more general than that considered in the current literature, where the complexity has been characterized only under the assumption of independence between arguments/defeats. The complexity of the problems is shown to range from FP to FP#P-complete, with FP‖NP-complete cases, depending on the semantics of the extensions, the representation paradigm used for encoding the prAAF, and the imposed correlations between arguments/defeats, thus providing a thorough analysis of the sensitivity to several aspects. In this regard, in order to allow the study of the impact of different forms of correlations between arguments/defeats on the complexity, a new form of prAAF is introduced, called GEN. It is based on the well-known paradigm of world-set descriptors and world-set sets for representing probabilities, and it allows the correlations to be easily and explicitly expressed. Interestingly, the introduction of GEN is shown to be also a standalone contribution as a powerful representation paradigm for prAAFs, owing to its high expressiveness, compactness, and the possibility to support user-friendly mechanisms for defining correlations.
Complexity; Probabilistic abstract argumentation; Language and Linguistics; Linguistics and Language; Artificial Intelligence
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11770/289843
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 11
social impact