Complexity of λ -term reductions

M. Dezani-Ciancaglini; S. Ronchi Della Rocca; L. Saitta

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1979)

  • Volume: 13, Issue: 3, page 257-287
  • ISSN: 0988-3754

How to cite

top

Dezani-Ciancaglini, M., Ronchi Della Rocca, S., and Saitta, L.. "Complexity of $\lambda $-term reductions." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 13.3 (1979): 257-287. <http://eudml.org/doc/92104>.

@article{Dezani1979,
author = {Dezani-Ciancaglini, M., Ronchi Della Rocca, S., Saitta, L.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {lambda calculus; complexity; reduction of lambda terms; normal forms; Blum's axioms},
language = {eng},
number = {3},
pages = {257-287},
publisher = {EDP-Sciences},
title = {Complexity of $\lambda $-term reductions},
url = {http://eudml.org/doc/92104},
volume = {13},
year = {1979},
}

TY - JOUR
AU - Dezani-Ciancaglini, M.
AU - Ronchi Della Rocca, S.
AU - Saitta, L.
TI - Complexity of $\lambda $-term reductions
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1979
PB - EDP-Sciences
VL - 13
IS - 3
SP - 257
EP - 287
LA - eng
KW - lambda calculus; complexity; reduction of lambda terms; normal forms; Blum's axioms
UR - http://eudml.org/doc/92104
ER -

References

top
  1. 1. S. K. ABDALI, A Lambda Calculus Model of Programming Languages. I. Simple Constructs and II. Jumps and Procedures, J. Comp. Languages, Vol. 1, 1976, pp. 287-301 and 303-320. Zbl0356.68042
  2. 2. H. BARENDREGT, Normed Uniformity Reflexive Structures, in C. BÖHM, Ed., (λ-Calculus and Computer Science Theory, Lecture Notes in Computer Science, No. 37, Springer-Verlag, 1975, pp. 272-286. Zbl0333.02021MR472499
  3. 3. H. BARENDREGT, J. BERGSTRA, J. W. KLOP and M. VOLKEN, Degrees, Reductions and Representability in Lambda Calculus, Preprint, University of Utrecht, Department of Mathematics, 1976. Zbl0399.03013
  4. 4. C. BATINI and A. PETTOROSSI, On Recursiveness in Weak Combinatory Logic, in C. BÖHM, Ed., λ-Calculus and Computer Science Theory, Lecture Notes in Computer Science, No. 37, Springer-Verlag, 1975, pp. 297-311. Zbl0332.02033MR479987
  5. 5. C. BÖHM and M. DEZANI-CIANCAGLINI, λ-terms as Total or Partial Functions on Normal Forms in C. BÖHM, Ed., λ-Calculus and Computer Science Theory, Lecture Notes in Computer Science, Vol. 37, Springer-Verlag, 1975, pp. 96-121. Zbl0342.02017MR485296
  6. 6. M. BLUM, On the Size of Machines, Information and Control, Vol. 11, 1967, pp. 257-265. Zbl0165.02102MR233634
  7. 7. R. CANAL, Complexité de la réduction en logique combinatoire, R.A.I.R.O., Informatique théorique, Vol. 12, 1978, pp.339-367. Zbl0432.03012MR517635
  8. 8. R. CANAL and J. VIGNOLLE, Calculs finis et infinis dans les termes combinatoires in B. ROBINET, Ed., λ-Calcul et Sémantique Formelle des langages de programmation, L.I.T.P.-E.N.S.T.A., 1979, pp. 109-130. 
  9. 9. H.B. CURRY and R. FEYS, Combinatory Logic, Vol. I, North-Holland, Amsterdam, 1958. Zbl0081.24104MR94298
  10. 10. H. B. CURRY, J. R. HINDLEY and J. P. SELDIN, Combinatory Logic, Vol. II, North-Holland, Amsterdam, 1972. Zbl0242.02029
  11. 11. M. DEZANI-CIANCAGLINI and S. RONCHI DELLA ROCCA, Computational Complexity and Structure of ʎ-terms in B. ROBINET, Ed., Programmation, Dunod, Paris, 1976, pp. 160-181. 
  12. 12. M. DEZANI-CIANCAGLINI, S. RONCHI DELLA ROCCA and L. SAITTA, Complexité élémentaire dans le λ-calcul in B. ROBINET, Ed., λ-calcul et Sémantique formelle des langages de programmation, L.I.T.P.-E.N.S.T.A., 1979, pp. 183-212. 
  13. 13. P. J. LANDIN, A Correspondence Between Algol 60and Church's Lambda Notation, Comm. A.C.M., Vol. 8, 1965, pp. 89-158. Zbl0134.33403
  14. 14. Y. MOSCOVAKIS, Axioms for Computation Theories-first draft in R. GANDY and M. YATES, Eds., Logic Colloquium'69, North Holland, Amsterdam, 1971, pp. 199-255. Zbl0243.02034MR281610
  15. 15. G. PLOTKIN, A set Theoretical Definition of Application, School of A.I., Memo, M.I.P.-R-95, Edinburgh,, 1975. 
  16. 16. B. ROBINET, Contribution à l'étude de réalités informatiques, Thèse, Université Paris-VI, 1974. 
  17. 17. D. SCOTT, Continuous Lattices, Lecture Notes in Mathematics, No. 274, Springer-Verlag, 1972, pp. 97-136. Zbl0239.54006MR404073
  18. 18. D. SCOTT, Data Types as Lattices, S.I.A.M. J., Comp., Vol. 5, 1976, pp. 522-587. Zbl0337.02018MR437330
  19. 19. S. STENLUND, Combinators, λ-terms and Proof Theory, D. Reidel Publ. Company, Dordrecht-Holland, 1972. Zbl0248.02032MR505306
  20. 20. C.P. WADSWORTH, Relation between Computational and Denotational Properties for Scott's Doo-Models of the Lambda Calculus S.I.A.M. J. Comp., Vol. 5, 1976, pp. 488-521. Zbl0346.02013MR505308

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.