Complexity of logic-based argumentation in Post's framework

Argument and Computation 2 (2-3):107 - 129 (2011)


Many proposals for logic-based formalisations of argumentation consider an argument as a pair (Φ,α), where the support Φ is understood as a minimal consistent subset of a given knowledge base which has to entail the claim α. In case the arguments are given in the full language of classical propositional logic reasoning in such frameworks becomes a computationally costly task. For instance, the problem of deciding whether there exists a support for a given claim has been shown to be -complete. In order to better understand the sources of complexity (and to identify tractable fragments), we focus on arguments given over formulæ in which the allowed connectives are taken from certain sets of Boolean functions. We provide a complexity classification for four different decision problems (existence of a support, checking the validity of an argument, relevance and dispensability) with respect to all possible sets of Boolean functions. Moreover, we make use of a general schema to enumerate all arguments to show that certain restricted fragments permit polynomial delay. Finally, we give a classification also in terms of counting complexity

Download options


    Upload a copy of this work     Papers currently archived: 72,855

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

12 (#816,713)

6 months
1 (#386,001)

Historical graph of downloads
How can I increase my downloads?

Similar books and articles

An Event-Based Fragment of First-Order Logic Over Intervals.Savas Konur - 2011 - Journal of Logic, Language and Information 20 (1):49-68.
A System of Relational Syllogistic Incorporating Full Boolean Reasoning.Nikolay Ivanov & Dimiter Vakarelov - 2012 - Journal of Logic, Language and Information 21 (4):433-459.
Tailoring Recursion for Complexity.Erich Grädel & Yuri Gurevich - 1995 - Journal of Symbolic Logic 60 (3):952-969.
Argumentation Without Arguments.Henry Prakken - 2011 - Argumentation 25 (2):171-184.
Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.