On the complexity of beta-reduction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of beta-reduction

Full text

Pdf (797 KB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

St. Petersburg Beach, Florida, United States

Pages: 110 - 118

Year of Publication: 1996

ISBN:0-89791-769-3

Author

Andrea Asperti

Dipartimento di Matematica, P.zza di Porta S. Donato 5, Bologna, Italy

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 21, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237721.237742 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	As94	A. Asperti. Li#ear Logic, Comonads, and Optimal Reduclions. Fundamenta Informaticae, Special Issue devoted to Categories in Computer Science, Vol. 22, n.1, pp.3-22. 1995.
	As95	Andrea Asperti, deltao!Epsilon = 1 - Optimizing Optimal lambda-Calculus Implementations, Proceedings of the 6th International Conference on Rewriting Techniques and Applications, p.102-116, April 05-07, 1995
	AGN95	A. Asperti , C. Giovannetti , A. Naletto, The Bologna Optimal Higher-Order Machine, University of Bologna, 1995
	AL93	Andrea Asperti , Cosimo Laneve, Paths, computations and labels in the &lgr;-calculus, Theoretical Computer Science, v.142 n.2, p.277-297, May 15, 1995
	AL93b	A. Asperti , C. Laneve, Interaction Systems II: The Practice of Optimal Reductions, University of Bologna, 1993
	ADLR94	A. Asperti, V. Danos, C. Laneve, L. Regnier. Paths in the ;#-calculus: three years of communications w#thout understandings. Proceedings of LICS'94. Paris. 1994.
	DR95	V. Danos, L. Regnier. Reversible and Irreversible Computations: GO{ and iX-machines. Draft. 1995.
	GAL92a	Georges Gonthier , Martín Abadi , Jean-Jacques Lévy, The geometry of optimal lambda reduction, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.15-26, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143172]
	GAL92b	G. Gonthier, M. Abadi, J.a. L#vy. Linear Logic without boxes. Proc. of the 7th Annual Symposium on Logic in Computer Science (LICS'92). 1992.
	Laf90	Yves Lafont, Interaction nets, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.95-108, December 1989, San Francisco, California, United States [doi>10.1145/96709.96718]
	Lam89	J. Lamping. An algorithm for optimal lambda calculus reductions. Xerox PARC Internal Report. 1989.
	Lam90	John Lamping, An algorithm for optimal lambda calculus reduction, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.16-30, December 1989, San Francisco, California, United States [doi>10.1145/96709.96711]
	Le78	a.a.Levy. R#duc/ions correctes et opt#males clans le lambda-calcul. Th#se de doctorat d'#tat, Universit# de Paris VII. 1978.
	Le80	J. J. L#vy. Optimal reductions #n the lambdacalculus. In J.P. Seldin and J.R. Hindley, editors, To H.B. Curry, Essays on Comb#natory Logic, Lambda Calculus and Formalism, pages 159- 191. Academic Press. 1980.
	LM92	X. Leroy, M.Mauny. The Caml Light system, release 0.5. Documentatzon and user's manual. IN- RIA Technical Report. September 1992.
	Ya94	The Yale Haskell Group. The Yale Haskell Users Manual. Yale University. October 1994.

CITED BY 7

	Andrea Asperti , Harry G. Mairson, Parallel beta reduction is not elementary recursive, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.303-315, January 19-21, 1998, San Diego, California, United States
	Andrea Asperti , Paolo Coppola , Simone Martini, (Optimal) duplication is not elementary recursive, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.96-107, January 19-21, 2000, Boston, MA, USA
	Julia L. Lawall , Harry G. Mairson, Optimality and inefficiency: what isn't a cost model of the lambda calculus?, ACM SIGPLAN Notices, v.31 n.6, p.92-101, June 15, 1996
	Julia L. Lawall , Harry G. Mairson, On global dynamics of optimal graph reduction, ACM SIGPLAN Notices, v.32 n.8, p.188-195, Aug. 1997
	Andrea Asperti , Paolo Coppola , Simone Martini, (Optimal) duplication is not elementary recursive, Information and Computation, v.193 n.1, p.21-56, 25 August 2004
	Andrea Aspetri , Harry G. Mairson, Parallel beta reduction is not elementary recursive, Information and Computation, v.170 n.1, p.49-80, October 10, 2001
	Ugo Dal Lago , Simone Martini, The weak lambda calculus as a reasonable machine, Theoretical Computer Science, v.398 n.1-3, p.32-50, May, 2008