Change search
ReferencesLink to record
Permanent link

Direct link
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, 117-129 p.Conference 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. 117-129 p.
Lecture Notes in Computer Science, ISSN 0302-9743 ; 6341 LNAI
Keyword [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 Science
URN: urn:nbn:se:hj:diva-31625DOI: 10.1007/978-3-642-15675-5_12ISI: 000312457600012ScopusID: 2-s2.0-78049359073ISBN: 9783642156755ISBN: 9783642156748OAI: diva2:957175
12th European Conference, JELIA 2010, Helsinki, Finland, September 13-15, 2010
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: 5 hits
ReferencesLink to record
Permanent link

Direct link