No label defined (Q4453638)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 2051382
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 2051382

      Statements

      7 March 2004
      0 references
      cut-elimination
      0 references
      normalization
      0 references
      complexity of algorithm
      0 references
      pruning transformation
      0 references
      monotone cut
      0 references
      0 references
      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].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references