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
Sets of Boolean connectives that make argumentation easier
LIF, Aix-Marseille Université, France.
LIF, Aix-Marseille Université, France.
Institut für Theoretische Informatik, Gottfried Wilhelm Leibniz Universität, Hannover, Germany.
Institut für Informationssysteme, Technische Universität, Wien, Austria.
2010 (English)In: Logics in artificial intelligence: 12th European Conference, JELIA 2010, Helsinki, Finland, September 13-15, 2010. Proceedings / [ed] Tomi Janhunen, Ilkka Niemelä, Berlin: Springer, 2010, p. 117-129Conference paper, Published paper (Refereed)
Abstract [en]

Many proposals for logic-based formalizations 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 most scenarios, arguments are given in the full language of classical propositional logic which makes reasoning in such frameworks 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 formulae 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.

Place, publisher, year, edition, pages
Berlin: Springer, 2010. p. 117-129
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 6341 LNAI
Keywords [en]
Boolean connectives, Classical propositional logic, Decision problems, Knowledge base, Logic-based formalization, Minimal consistent subset, Artificial intelligence, Knowledge based systems, Boolean functions
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:hj:diva-31625DOI: 10.1007/978-3-642-15675-5_12ISI: 000312457600012Scopus ID: 2-s2.0-78049359073ISBN: 9783642156755 (print)ISBN: 9783642156748 (print)OAI: oai:DiVA.org:hj-31625DiVA, id: diva2:957175
Conference
12th European Conference, JELIA 2010, Helsinki, Finland, September 13-15, 2010
Available from: 2016-09-01 Created: 2016-09-01 Last updated: 2018-01-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Schmidt, Johannes

Search in DiVA

By author/editor
Schmidt, Johannes
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
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