Coherence in finite argument systems.
type: Item
instance of: scholarly article
title: Coherence in finite argument systems.
zbMATH Open document ID: 1043.68098
DOI: 10.1016/S0004-3702(02)00261-8
author: Paul E. Dunne
author: Trevor Bench-Capon
published in: Artificial Intelligence
publication date: 2003-01-21T00:00:00Z
review text: Argument Systems provide a rich abstraction within which divers concepts of reasoning, acceptability and defeasibility of arguments, etc., may be studied using a unified framework. Two important concepts of the acceptability of an argument \(p\) in such systems are credulous acceptance to capture the notion that \(p\) can be `believed'; and sceptical acceptance capturing the idea that if anything is believed, then \(p\) must be. One important aspect affecting the computational complexity of these problems concerns whether the admissibility of an argument is defined with respect to `preferred' or `stable' semantics. One benefit of so-called `coherent' argument systems being that the preferred extensions coincide with stable extensions. In this note we consider complexity-theoretic issues regarding deciding if finitely presented argument systems modelled as directed graphs are coherent. Our main result shows that the related decision problem is \(\Pi_{2}^{(p)}\)-complete and is obtained solely via the graph-theoretic representation of an argument system, thus independent of the specific logic underpinning the reasoning theory.
Mathematics Subject Classification ID: 68T37
Mathematics Subject Classification ID: 68Q55
zbMATH DE Number: 1856154
zbMATH Keywords: Argument Systems
zbMATH Keywords: Coherence
zbMATH Keywords: Credulous reasoning
zbMATH Keywords: Sceptical reasoning
zbMATH Keywords: Computational complexity
Wikidata QID: Q58168648
MaRDI profile type: Publication
cites work: Default reasoning using classical logic
cites work: An abstract, argumentation-theoretic approach to default reasoning
cites work: Q4784873
cites work: Kernels in random graphs
cites work: Graph theoretical structures in logic programs and default theories
cites work: On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and \(n\)-person games
cites work: Q3994882
cites work: Two party immediate response disputes: Properties and efficiency
cites work: Q4536329
cites work: Complete sets and the polynomial-time hierarchy
full work available at URL: s0004-3702(02)00261-8
OpenAlex ID: W2149567024
description: scientific article; zbMATH DE number 1856154