Can I read Discriminating Lambda-Terms Using Clocked Boehm Trees on EtoBox?

Discriminating Lambda-Terms Using Clocked Boehm Trees by Endrullis, Joerg; Hendriks, Dimitri; Klop, Jan Willem; Polonsky, Andrew is a scholarly article available to read on EtoBox.

What is Discriminating Lambda-Terms Using Clocked Boehm Trees about?

As observed by Intrigila, there are hardly techniques available in the lambda-calculus to prove that two lambda-terms are not beta-convertible. Techniques employing the usual Boehm Trees are inadequate when we deal with terms having the same Boehm Tree (BT). This is the case in particular for fixed point combinators, as they all have the same BT. Another interesting equation, whose consideration was suggested by Scott, is BY = BYS, an equation valid in the classical model P-omega of lambda-calculus, and hence valid with respect to BT-equality but nevertheless the terms are beta-inconvertible. To prove such beta-inconvertibilities, we employ `clocked' BT's, with annotations that convey information of the tempo in which the data in the BT are produced. Boehm Trees are thus enriched with an intrinsic clock behaviour, leading to a refined discrimination method for lambda-terms. The corresponding equality is strictly intermediate between beta-convertibility and Boehm Tree equality, the equality in the model P-omega. An analogous approach pertains to Levy-Longo and Berarducci Trees. Our refined Boehm Trees find in particular an application in beta-discriminating fixed point combinators (

Author

Endrullis, Joerg; Hendriks, Dimitri; Klop, Jan Willem; Polonsky, Andrew

Published

2012

Language

EN