Hostname: page-component-7b7567c8c-48dgx Total loading time: 0 Render date: 2026-11-18T02:53:38.622Z Has data issue: false hasContentIssue false

Upper bounds for standardizations and an application

Published online by Cambridge University Press:  12 March 2014

Hongwei Xi*
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, Pa 15213, USA E-mail: hwxi+@cs.cmu.edu

Abstract

We present a new proof for the standardization theorem in λ-calculus, which is largely built upon a structural induction on λ-terms. We then extract some bounds for the number of β-reduction steps in the standard β-reduction sequence obtained from transforming a given β-reduction sequence, sharpening the standardization theorem. As an application, we establish a super exponential bound for the lengths of β-reduction sequences from any given simply typed λ-terms.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable