Complexity of λ-term reductions
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 13 (1979) no. 3, pp. 257-287.
@article{ITA_1979__13_3_257_0,
     author = {Dezani-Ciancaglini, M. and Ronchi Della Rocca, S. and Saitta, L.},
     title = {Complexity of $\lambda $-term reductions},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {257--287},
     publisher = {EDP-Sciences},
     volume = {13},
     number = {3},
     year = {1979},
     zbl = {0424.03009},
     mrnumber = {554687},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1979__13_3_257_0/}
}
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
DA  - 1979///
SP  - 257
EP  - 287
VL  - 13
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1979__13_3_257_0/
UR  - https://zbmath.org/?q=an%3A0424.03009
UR  - https://www.ams.org/mathscinet-getitem?mr=554687
LA  - en
ID  - ITA_1979__13_3_257_0
ER  - 
Dezani-Ciancaglini, M.; Ronchi Della Rocca, S.; Saitta, L. Complexity of $\lambda $-term reductions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 13 (1979) no. 3, pp. 257-287. http://www.numdam.org/item/ITA_1979__13_3_257_0/

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. | Zbl 0356.68042

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. | MR 472499 | Zbl 0333.02021

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.

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. | MR 479987 | Zbl 0332.02033

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. | MR 485296 | Zbl 0342.02017

6.M. Blum, On the Size of Machines, Information and Control, Vol. 11, 1967, pp. 257-265. | MR 233634 | Zbl 0165.02102

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. | EuDML 92085 | Numdam | MR 517635 | Zbl 0432.03012

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.H.B. Curry and R. Feys, Combinatory Logic, Vol. I, North-Holland, Amsterdam, 1958. | MR 94298 | Zbl 0081.24104

10.H. B. Curry, J. R. Hindley and J. P. Seldin, Combinatory Logic, Vol. II, North-Holland, Amsterdam, 1972. | Zbl 0242.02029

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.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.P. J. Landin, A Correspondence Between Algol 60and Church's Lambda Notation, Comm. A.C.M., Vol. 8, 1965, pp. 89-158. | Zbl 0134.33403

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. | MR 281610 | Zbl 0243.02034

15.G. Plotkin, A set Theoretical Definition of Application, School of A.I., Memo, M.I.P.-R-95, Edinburgh,, 1975.

16.B. Robinet, Contribution à l'étude de réalités informatiques, Thèse, Université Paris-VI, 1974.

17.D. Scott, Continuous Lattices, Lecture Notes in Mathematics, No. 274, Springer-Verlag, 1972, pp. 97-136. | MR 404073 | Zbl 0239.54006

18.D. Scott, Data Types as Lattices, S.I.A.M. J., Comp., Vol. 5, 1976, pp. 522-587. | MR 437330 | Zbl 0337.02018

19.S. Stenlund, Combinators, λ-terms and Proof Theory, D. Reidel Publ. Company, Dordrecht-Holland, 1972. | MR 505306 | Zbl 0248.02032

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. | MR 505308 | Zbl 0346.02013