arnold beckmann's pages

On the computational complexity of cut-reduction

File: PDF-File

Author: Klaus T Aehlig and Arnold Beckmann
Title: On the computational complexity of cut-reduction
Journal: APAL 2010, 161(6): 711-736
DOI: 10.1016/j.apal.2009.06.004

Abstract: Using appropriate notation systems for proofs, cut-reduction can often be rendered feasible on these notations, and explicit bounds can be given. Developing a suitable notation system for Bounded Arithmetic, and applying these bounds, all the known results on definable functions of certain such theories can be reobtained in a uniform way.

websites: Arnold Beckmann 2017-08-28 Valid HTML 4.01! Valid CSS!