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 of logic-based argumentation in Post's framework
Aix-Marseille Université, France.
Aix-Marseille Université, France.
TWT GmbH, Germany.
Institut für Informationssysteme, Technische Universität Wien, Austria.
2011 (English)In: Argument and Computation, ISSN 1946-2166, Vol. 2, no 2-3, 107-129 p.Article in journal (Refereed) Published
Abstract [en]

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 Σ 2 p-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.

Place, publisher, year, edition, pages
2011. Vol. 2, no 2-3, 107-129 p.
Keyword [en]
complexity, counting, enumeration, logic based argumentation, Post's lattice, Knowledge based systems, Boolean functions
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:hj:diva-31619DOI: 10.1080/19462166.2011.629736ScopusID: 2-s2.0-84863410712OAI: oai:DiVA.org:hj-31619DiVA: diva2:957130
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: 12 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