A Note on Shortest Developments - Computer Science > Logic in Computer ScienceReportar como inadecuado




A Note on Shortest Developments - Computer Science > Logic in Computer Science - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: De Vrijer has presented a proof of the finite developments theorem which, inaddition to showing that all developments are finite, gives an effectivereduction strategy computing longest developments as well as a simple formulacomputing their length.We show that by applying a rather simple and intuitive principle of dualityto de Vrijer-s approach one arrives at a proof that some developments arefinite which in addition yields an effective reduction strategy computingshortest developments as well as a simple formula computing their length. Theduality fails for general beta-reduction.Our results simplify previous work by Khasidashvili.



Autor: Morten Heine Sørensen

Fuente: https://arxiv.org/







Documentos relacionados