UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

The complexity of the warranted formula problem in propositional argumentation

Hirsch, R; Gorogiannis, N; (2010) The complexity of the warranted formula problem in propositional argumentation. Journal of Logic and Computation , 20 (2) 482 - 499. 10.1093/logcom/exp074.

Full text not available from this repository.

Abstract

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.

Type:Article
Title:The complexity of the warranted formula problem in propositional argumentation
DOI:10.1093/logcom/exp074
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record