Sets of Boolean connectives that make argumentation easier
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)
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
Boolean connectives, Classical propositional logic, Decision problems, Knowledge base, Logic-based formalization, Minimal consistent subset, Artificial intelligence, Knowledge based systems, Boolean functions
Computer and Information Science
IdentifiersURN: urn:nbn:se:hj:diva-31625DOI: 10.1007/978-3-642-15675-5_12ISI: 000312457600012ScopusID: 2-s2.0-78049359073ISBN: 9783642156755ISBN: 9783642156748OAI: oai:DiVA.org:hj-31625DiVA: diva2:957175
12th European Conference, JELIA 2010, Helsinki, Finland, September 13-15, 2010