The Role of Quantifier Alternations in Cut Elimination

Philipp Gerhardy

December 2003

Abstract:

Extending previous results from the author's master's thesis, subsequently published in the proceedings of CSL 2003, on the complexity of cut elimination for the sequent calculus LK, we discuss the role of quantifier alternations and develope a measure to describe the complexity of cut elimination in terms of quantifier alternations in cut formulas and contractions on such formulas

Available as PostScript, PDF, DVI.

 

Last modified: 2004-02-02 by webmaster.