Coherence in finite argument systems

摘要

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 pcan be ‘believed’; and sceptical acceptance capturing the idea that if anything is believed, then pmust 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 Π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.