Tech Reports

ULCS-01-006

Coherence in Finite Argument Systems

Paul E. Dunne and Trevor J. M. Bench-Capon

Abstract

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 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.

Keywords: Argument Systems, Coherence, Credulous and Sceptical reasoning, Computational Complexity.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.