Labeling techniques and typed fixed-point operators
Lists
Only you see this
Abstract
Labeling techniques for untyped lambda calculus were developed by Levy, Hyland, Wadsworth and others in the 1970's. A typical application is the proof of confluence from finiteness of de- velopments: by labeling each subterm with a natural number indicating the maximum number of times this term may participate in a reduction step, we obtain a strongly-normalizing ap- proximation of β, η-reduction. Confluence then follows by a syntactic compactness argument (repeated in the introduction of this paper). This paper presents applications of labeling to typed lambda calculi with fixed-point opera- tors, including confluence and completeness of leftmost reduction for PCF (an applied lambda calculus with fixed-point operators and numeric and boolean operations) and a confluence proof for a variant of typed lambda calculus with subtyping. Labeling is simpler for typed calculi than untyped calculi because the fixed-point operator is the only source of nontermination. We can also use the method of logical relations for the labeled typed calculus, extended with basic operations like addition and conditional. This method would not apply to untyped lambda calculus.
BibTeX
@inproceedings{mitchell1999labeling,
author = {John C. Mitchell and M. Hoang and Brian Howard},
title = {{Labeling techniques and typed fixed-point operators}},
booktitle = {Cambridge},
year = {1999},
}Loading related content...