Argument and Computation 2 (2-3):107 - 129 (2011)
AbstractMany 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
Added to PP
Historical graph of downloads
References found in this work
On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and N-Person Games.Phan Minh Dung - 1995 - Artificial Intelligence 77 (2):321-357.
On the Evaluation of Argumentation Formalisms.Martin Caminada & Leila Amgoud - 2007 - Artificial Intelligence 171 (5-6):286-310.
The Two-Valued Iterative Systems of Mathematical Logic.Emil Leon Post - 1941 - London: Oxford University PRess.
Instantiating Abstract Argumentation with Classical Logic Arguments: Postulates and Properties.Nikos Gorogiannis & Anthony Hunter - 2011 - Artificial Intelligence 175 (9-10):1479-1497.
A Logic-Based Theory of Deductive Arguments☆☆This is an Extended Version of a Paper Entitled “Towards a Logic-Based Theory of Argumentation” Published in the Proceedings of the National Conference on Artificial Intelligence (AAAI'2000), Austin, TX, MIT Press, Cambridge, MA, 2000. [REVIEW]Philippe Besnard & Anthony Hunter - 2001 - Artificial Intelligence 128 (1-2):203-235.
Citations of this work
Constructing Argument Graphs with Deductive Arguments: A Tutorial.Philippe Besnard & Anthony Hunter - 2014 - Argument and Computation 5 (1):5-30.
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.
Complexity Results for Modal Dependence Logic.Peter Lohmann & Heribert Vollmer - 2013 - Studia Logica 101 (2):343-366.
A System of Relational Syllogistic Incorporating Full Boolean Reasoning.Nikolay Ivanov & Dimiter Vakarelov - 2012 - Journal of Logic, Language and Information 21 (4):433-459.
Bounded Arithmetic, Propositional Logic and Complexity Theory.Jan Krajíček - 1995 - Cambridge University Press.
Tailoring Recursion for Complexity.Erich Grädel & Yuri Gurevich - 1995 - Journal of Symbolic Logic 60 (3):952-969.
Answer-Set Programming Encodings for Argumentation Frameworks.Uwe Egly, Sarah Alice Gaggl & Stefan Woltran - 2010 - Argument and Computation 1 (2):147-177.
On the Degree of Complexity of Sentential Logics.II. An Example of the Logic with Semi-Negation.Jacek Hawranek & Jan Zygmunt - 1984 - Studia Logica 43 (4):405 - 413.
An Abstract Framework for Argumentation with Structured Arguments.Henry Prakken - 2010 - Argument and Computation 1 (2):93-124.
Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
A Sound and Complete Tableau Calculus for Reasoning About Only Knowing and Knowing at Most.Riccardo Rosati - 2001 - Studia Logica 69 (1):171-191.
Coherence and Computational Complexity of Quantifier-Free Dependence Logic Formulas.Jarmo Kontinen - 2013 - Studia Logica 101 (2):267-291.