Complexity of λ-term reductions
RAIRO. Informatique théorique, Volume 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. Informatique th\'eorique},
     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. Informatique théorique
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  - 
%0 Journal Article
%A Dezani-Ciancaglini, M.
%A Ronchi Della Rocca, S.
%A Saitta, L.
%T Complexity of $\lambda $-term reductions
%J RAIRO. Informatique théorique
%D 1979
%P 257-287
%V 13
%N 3
%I EDP-Sciences
%G en
%F ITA_1979__13_3_257_0
Dezani-Ciancaglini, M.; Ronchi Della Rocca, S.; Saitta, L. Complexity of $\lambda $-term reductions. RAIRO. Informatique théorique, Volume 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

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

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

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

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

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 | Numdam | MR | Zbl

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

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

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

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

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

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

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

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