Notice
This item was automatically migrated from a legacy system. It's data has not been checked and might not meet the quality criteria of the present system.
DC Field
Value
Language
dc.contributor.author
Egly, Uwe
-
dc.contributor.author
Creignou, Nadia
-
dc.contributor.author
Schmidt, Johannes
-
dc.contributor.editor
Verheij, Bart
-
dc.contributor.editor
Szeider, Stefan
-
dc.contributor.editor
Woltran, Stefan
-
dc.date.accessioned
2022-08-04T11:48:50Z
-
dc.date.available
2022-08-04T11:48:50Z
-
dc.date.issued
2012
-
dc.identifier.citation
<div class="csl-bib-body">
<div class="csl-entry">Egly, U., Creignou, N., & Schmidt, J. (2012). Complexity of logic-based argumentation in Schaefer’s framework. In B. Verheij, S. Szeider, & S. Woltran (Eds.), <i>Computational Models of Argument</i> (pp. 237–248). IOS Press. http://hdl.handle.net/20.500.12708/54461</div>
</div>
-
dc.identifier.isbn
978-1-61499-110-6
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/54461
-
dc.description.abstract
We consider logic-based argumentation in which an argument is a pair (Φ, α), where the support Φ is a minimal consistent set of formulæof a given knowledge base that entails the formula α. We study the complexity of two different problems: the existence of a support and the verification of the validity of an argument. When arguments are given in the full language of propositional logic these problems are computationally costly tasks, they are respectively ΣP2- and DP-complete. We study these problems in Schaefer's famous framework. We consider the case where formulæare taken from a class of formulæin generalized conjunctive normal form. This means that the propositional formulæ considered are conjunctions of constraints taken from a fixed finite language Γ. We show that according to the properties of this language Γ, deciding whether there exists a support for a claim in a given knowledge base is either polynomial, NP-complete, coNP-complete or ΣP2-complete. We also obtain a dichotomous classification, P or DP-complete, for the verification problem.
en
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.publisher
IOS Press
-
dc.subject
Argumentation
-
dc.subject
complexity
-
dc.title
Complexity of logic-based argumentation in Schaefer's framework
-
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.relation.publication
Computational Models of Argument
-
dc.description.startpage
237
-
dc.description.endpage
248
-
dc.relation.grantno
S 11409-N23
-
dc.type.category
Full-Paper Contribution
-
dc.publisher.place
Frontiers in Artificial Intelligence and Applications, Vol 245
-
tuw.booktitle
Computational Models of Argument
-
tuw.peerreviewed
true
-
tuw.project.title
Quantified Boolean Formulas
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-03 - Forschungsbereich Knowledge Based Systems
-
dc.description.numberOfPages
12
-
tuw.event.name
COMMA - International Conference on Computational Models of Argument
-
tuw.event.startdate
11-09-2006
-
tuw.event.enddate
12-09-2006
-
tuw.event.online
On Site
-
tuw.event.place
Liverpool, UK
-
tuw.event.place
Liverpool, UK
-
tuw.event.country
EU
-
tuw.event.presenter
Creignou, Nadia
-
wb.sciencebranch
Mathematik, Informatik
-
wb.sciencebranch.oefos
11
-
wb.presentation.type
science to science/art to art
-
item.openairetype
conference paper
-
item.grantfulltext
none
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
crisitem.author.dept
E192-03 - Forschungsbereich Knowledge Based Systems
-
crisitem.author.dept
BOKU University
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.project.funder
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)