Static Analysis of Modularity of β-Reduction in the Hyperbalanced λ-Calculus

Kennaway, J. Richard, Khasidashvili, Zurab and Piperno, Adolfo (2002) Static Analysis of Modularity of β-Reduction in the Hyperbalanced λ-Calculus. In: Rewriting Techniques and Applications. Lecture Notes in Computer Science, 2378 . Springer Berlin / Heidelberg, DNK, pp. 51-65. ISBN 978-3-540-43916-5

Full text not available from this repository. (Request a copy)

Abstract

We investigate the degree of parallelism (or modularity) in the hyperbalanced ?-calculus, ?H, a subcalculus of ?-calculus containing all simply typable terms (up to a restricted ?-expansion). In technical terms, we study the family relation on redexes in ?H, and the contribution relation on redex-families, and show that the latter is a forest (as a partial order). This means that hyperbalanced ?-terms allow for maximal possible parallelism in computation. To prove our results, we use and further refine, for the case of hyperbalanced terms, some well known results concerning paths, which allow for static analysis of many fundamental properties of ß-reduction.

Item Type:	Book Section
Faculty \ School:	Faculty of Science > School of Computing Sciences
Depositing User:	Vishal Gautam
Date Deposited:	28 Jul 2011 09:09
Last Modified:	15 Dec 2022 00:52
URI:	https://ueaeprints.uea.ac.uk/id/eprint/23341
DOI:	10.1007/3-540-45610-4_5

Actions (login required)

View Item