On the computational complexity of assumption-based argumentation for default reasoning.
type: Item
instance of: scholarly article
title: On the computational complexity of assumption-based argumentation for default reasoning.
zbMATH Open document ID: 1043.68097
DOI: 10.1016/S0004-3702(02)00245-X
author: Yannis Dimopoulos
author: Bernhard Nebel
author: Francesca Toni
published in: Artificial Intelligence
publication date: 2003-01-21T00:00:00Z
review text: Bondarenko et al. have recently proposed an abstract framework for default reasoning. Besides capturing most existing formalisms and proving that their standard semantics all coincide, the framework extends these formalisms by generalising the semantics of admissible and preferred arguments, originally proposed for logic programming only. In this paper we analyse the computational complexity of credulous and sceptical reasoning under the semantics of admissible and preferred arguments for (the propositional variant of) the instances of the abstract framework capturing theorist, circumscription, logic programming, default logic, and autoepistemic logic. Although the new semantics have been tacitly assumed to mitigate the computational hardness of default reasoning under the standard semantics of stable extensions, we show that in many cases reasoning under the admissibility and preferability semantics is computationally harder than under the standard semantics. In particular, in the case of autoepistemic logic, sceptical reasoning under preferred arguments is located at the fourth level of the polynomial hierarchy, whereas the same form of reasoning under stable extensions is located at the second level.
Mathematics Subject Classification ID: 68T37
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1856157
zbMATH Keywords: Non-monotonic reasoning
zbMATH Keywords: Default reasoning
zbMATH Keywords: Assumption-based reasoning
zbMATH Keywords: Abduction
zbMATH Keywords: Argumentation
zbMATH Keywords: Computational complexity
Wikidata QID: Q62039892
MaRDI profile type: Publication
cites work: An abstract, argumentation-theoretic approach to default reasoning
cites work: The complexity of propositional closed world reasoning and circumscription
cites work: A survey of complexity results for non-monotonic logics
cites work: Q4022222
cites work: Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
cites work: Expressive power and complexity of partial models for disjunctive deductive databases
cites work: Q4198056
cites work: Complexity Results for Nonmonotonic Logics
cites work: The complexity of default reasoning under the stationary fixed point semantics
cites work: Q4843185
cites work: Q4273952
cites work: Circumscription - a form of non-monotonic reasoning
cites work: Nonmonotonic Logic II
cites work: Semantical considerations on nonmonotonic logic
cites work: Q4287511
cites work: Q3221403
cites work: A logical framework for default reasoning
cites work: A logic for default reasoning
cites work: The expressive powers of stable models for bound and unbound DATALOG queries
cites work: Q4131648
full work available at URL: s0004-3702(02)00245-x
OpenAlex ID: W2006784674
Recommended article: Q4446263
Recommended article: Declarative Algorithms and Complexity Results for Assumption-Based Argumentation
Recommended article: Computational complexity of flat and generic assumption-based argumentation, with and without probabilities
Recommended article: An abstract, argumentation-theoretic approach to default reasoning
Recommended article: The complexity of reasoning for fragments of default logic
Recommended article: The Complexity of Reasoning for Fragments of Default Logic
Recommended article: An argumentation framework in default logic
description: scientific article; zbMATH DE number 1856157