Talks and Poster Presentations (with Proceedings-Entry):
U. Egly, N. Creignou, J. Schmidt:
"Complexity of logic-based argumentation in Schaefer's framework";
Talk: COMMA - International Conference on Computational Models of Argument,
- 2012-09-12; in: "Computational Models of Argument",
B. Verheij, St. Szeider, S. Woltran (ed.);
Frontiers in Artificial Intelligence and Applications, Vol 245
We consider logic-based argumentation in which an argument is a pair (Φ, α), where the support Φ is a minimal consistent set of formulæof a given knowledge base that entails the formula α. We study the complexity of two different problems: the existence of a support and the verification of the validity of an argument. When arguments are given in the full language of propositional logic these problems are computationally costly tasks, they are respectively ΣP2- and DP-complete. We study these problems in Schaefer's famous framework. We consider the case where formulæare taken from a class of formulæin generalized conjunctive normal form. This means that the propositional formulæ considered are conjunctions of constraints taken from a fixed finite language Γ. We show that according to the properties of this language Γ, deciding whether there exists a support for a claim in a given knowledge base is either polynomial, NP-complete, coNP-complete or ΣP2-complete. We also obtain a dichotomous classification, P or DP-complete, for the verification problem.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Project Head Uwe Egly:
Quantified Boolean Formulas
Created from the Publication Database of the Vienna University of Technology.