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.

[Full Paper]