scientific article; zbMATH DE number 2051382

From MaRDI portal
Publication:4453638





The complexity of a cut-elimination algorithm is an important issue from the point of view of interpreting the reduction of logical proofs to a normal form as a computation of a value of a program. Generally it is hyper-exponential in the worst case, while for monotone formulas they have been proved by \textit{M. Baaz} and \textit{A. Leitsch} [Ann. Pure Appl. Log. 97, 127--177 (1999; Zbl 0940.03062)] to be eliminable under an almost exponential bound. In this paper the author shows by applying pruning transformations that monotone cuts (of derivations in a slightly restricted class) can be eliminated with still smaller blow-up, which simplifies significantly both the proof and the cut-elimination algorithm employed by Baaz and Leitsch. For the entire collection see [Zbl 1026.00013].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4453638)