Change search
ReferencesLink to record
Permanent link

Direct link
Complexity of logic-based argumentation in Schaefer's framework
LIF, Aix-Marseille Université, France.
LIF, Aix-Marseille Université, France.
2012 (English)In: Computational models of argument, IOS Press, 2012, no 1, 237-248 p.Conference paper (Refereed)
Abstract [en]

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 ΣP 2- 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 ΣP 2-complete. We also obtain a dichotomous classification, P or DP-complete, for the verification problem.

Place, publisher, year, edition, pages
IOS Press, 2012. no 1, 237-248 p.
Frontiers in Artificial Intelligence and Applications, 245
Keyword [en]
Complexity of argumentation, Generalized satisfiability, Logic-based argumentation, Schaefer, Formal logic, Knowledge based systems, Conjunctive normal forms, Finite languages, Logic-based argumentations, Propositional logic, Satisfiability, Verification problems, Computational linguistics
National Category
Computer and Information Science
URN: urn:nbn:se:hj:diva-31621DOI: 10.3233/978-1-61499-111-3-237ISI: 000349004000024ScopusID: 2-s2.0-84876270546ISBN: 9781614991106ISBN: 9781614991113OAI: diva2:957147
4th Conference on Computational Models of Argument (COMMA), Vienna, Austria, September 10-12, 2012
Available from: 2016-09-01 Created: 2016-09-01 Last updated: 2016-09-01Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Schmidt, Johannes
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 10 hits
ReferencesLink to record
Permanent link

Direct link