Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Complexity Classifications for Logic-Based Argumentation
Aix Marseille University, France.
Vienna University of Technology, Austria.
Linköpings universitet, Programvara och system.
2014 (English)In: ACM Transactions on Computational Logic, ISSN 1529-3785, E-ISSN 1557-945X, Vol. 15, no 3, 19Article in journal (Refereed) Published
Abstract [en]

We consider logic-based argumentation in which an argument is a pair (Phi, alpha), where the support Phi is a minimal consistent set of formulae taken from a given knowledge base (usually denoted by Delta) that entails the claim alpha (a formula). We study the complexity of three central problems in argumentation: the existence of a support Phi subset of Delta, the verification of a support, and the relevance problem (given psi, is there a support Phi such that psi is an element of Phi?). When arguments are given in the frill language of propositional logic, these problems are computationally costly tasks: the verification problem is DP-complete; the others are Sigma(P)(2)-complete. We study these problems in Schaefers famous framework where the considered propositional formulae are in generalized conjunctive normal form. This means that formulae are conjunctions of constraints built upon a fixed finite set of Boolean relations Gamma (the constraint language). We show that according to the properties of this language Gamma, deciding whether there exists a support for a claim in a given knowledge base is either polynomial, NP-complete, coNP-complete, or Sigma(P)(2)-complete. We present a dichotomous classification, P or DP-complete, for the verification problem and a trichotomous classification for the relevance problem into either polynomial, NP-complete, or Sigma(P)(2)-complete. These last two classifications are obtained by means of algebraic tools.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM) , 2014. Vol. 15, no 3, 19
Keyword [en]
Theory; Computational complexity; generalized satisfiability; logic-based argumentation; Schaefer
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:hj:diva-31616DOI: 10.1145/2629421ISI: 000343693300002Scopus ID: 2-s2.0-84907578385OAI: oai:DiVA.org:hj-31616DiVA: diva2:957120
Note

Funding Agencies|National Graduate School in Computer Science (CUGS), Sweden; Austrian Science Foundation (FWF) [S11409-N23]

Available from: 2014-11-28 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
In the same journal
ACM Transactions on Computational Logic
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 52 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf