The complexity of the warranted formula problem in propositional argumentation.
Journal of Logic and Computation
482 - 499.
The notion of warrant or justification is one of the central concepts in formal models of argumentation. The dialectical definition of warrant is expressed in terms of recursive defeat: an argument is warranted if each of its counter-arguments is itself defeated by a warranted counter-argument. However, few complexity results exist on checking whether an argument is warranted in the context of deductive models of argumentation, i.e. models where an argument is a deduction of a claim from a set of premises using some logic. We investigate the computational complexity of checking whether a claim is warranted in propositional argumentation under two natural definitions of warrant and show that it is PSPACE-complete in both cases.
|Title:||The complexity of the warranted formula problem in propositional argumentation|
|UCL classification:||UCL > School of BEAMS > Faculty of Engineering Science > Computer Science|
Archive Staff Only