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) pp. 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
Keywords: Argumentation, Complexity, Propositional logic, Warranted formula problem
UCL classification: UCL > School of BEAMS > Faculty of Engineering Science
UCL > School of BEAMS > Faculty of Engineering Science > Computer Science
URI: http://discovery.ucl.ac.uk/id/eprint/1349985
Downloads since deposit
0Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item