Strong Normalisation of Cut-Elimination in Classical Logic

Issue title: Typed Lambda Calculi and Applications (TLCA'99)

Article type: Research Article

Authors: Urban, C. | Bierman, G.M.

Abstract: In this paper we present a strongly normalising cut-elimination procedure for classical logic. This procedure adapts Gentzen's standard cut-reductions, but is less restrictive than previous strongly normalising cut-elimination procedures. In comparison, for example, with works by Dragalin and Danos et al., our procedure requires no special annotations on formulae and allows cut-rules to pass over other cut-rules. In order to adapt the notion of symmetric reducibility candidates for proving the strong normalisation property, we introduce a novel term assignment for sequent proofs of classical logic and formalise cut-reductions as term rewriting rules.

Keywords: Classical Logic, Cut-Elimination, Strong Normalisation, Symmetric Reducibility Candidates

Journal: Fundamenta Informaticae, vol. 45, no. 1-2, pp. 123-155, 2001