Acceptance in Incomplete Argumentation Frameworks

Show full item record



Permalink

http://hdl.handle.net/10138/333410

Citation

Baumeister , D , Järvisalo , M , Neugebauer , D , Niskanen , A & Rothe , J 2021 , ' Acceptance in Incomplete Argumentation Frameworks ' , Artificial Intelligence , vol. 295 , 103470 . https://doi.org/10.1016/j.artint.2021.103470

Title: Acceptance in Incomplete Argumentation Frameworks
Author: Baumeister, Dorothea; Järvisalo, Matti; Neugebauer, Daniel; Niskanen, Andreas; Rothe, Jörg
Contributor: University of Helsinki, Department of Computer Science
University of Helsinki, Constraint Reasoning and Optimization research group / Matti Järvisalo
Date: 2021-06
Language: eng
Number of pages: 35
Belongs to series: Artificial Intelligence
ISSN: 0004-3702
URI: http://hdl.handle.net/10138/333410
Abstract: A Abstract argumentation frameworks (AFs), originally proposed by Dung, constitute a central formal model for the study of computational aspects of argumentation in AI. Credulous and skeptical acceptance of arguments in a given AF are well-studied problems both in terms of theoretical analysis-especially computational complexity-and the development of practical decision procedures for the problems. However, AFs make the assumption that all attacks between arguments are certain (i.e., present attacks are known to exist, and missing attacks are known to not exist), which can in various settings be a restrictive assumption. A generalization of AFs to incomplete AFs was recently proposed as a formalism that allows the representation of both uncertain attacks and uncertain arguments in AFs. In this article, we explore the impact of allowing for modeling such uncertainties in AFs on the computational complexity of natural generalizations of acceptance problems to incomplete AFs under various central AF semantics. Complementing the complexity-theoretic analysis, we also develop the first practical decision procedures for all of the NP-hard variants of acceptance in incomplete AFs. In terms of complexity analysis, we establish a full complexity landscape, showing that depending on the variant of acceptance and property/semantics, the complexity of acceptance in incomplete AFs ranges from polynomial-time decidable to completeness for Sigma(p)(3). In terms of algorithms, we show through an extensive empirical evaluation that an implementation of the proposed decision procedures, based on boolean satisfiability (SAT) solving, is effective in deciding variants of acceptance under uncertainties. We also establish conditions for what type of atomic changes are guaranteed to be redundant from the perspective of preserving extensions of completions of incomplete AFs, and show that the results allow for considerably improving the empirical efficiency of the proposed SAT-based counterexample-guided abstraction refinement algorithms for acceptance in incomplete AFs for problem variants with complexity beyond NP. (C) 2021 The Authors. Published by Elsevier B.V.
Subject: 113 Computer and information sciences
Abstract argumentation
Incomplete knowledge
Incomplete argumentation frameworks
Computational complexity
Decision procedures
Empirical evaluation
DETERMINISTIC EXTENSIONS
DYNAMICS
EQUIVALENCE
ALGORITHMS
COMPLEXITY
SYSTEMS
COMPUTATION
REFINEMENT
HARD
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
1_s2.0_S0164121221001473_main.pdf 1.064Mb PDF View/Open

This item appears in the following Collection(s)

Show full item record