Geodesic
Complexity of λ-term reductions
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 13 (1979) no. 3, pp. 257-287.

Voir la notice de l'article provenant de la source Numdam

@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},
     mrnumber = {554687},
     zbl = {0424.03009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/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
SP  - 257
EP  - 287
VL  - 13
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/item/ITA_1979__13_3_257_0/
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 - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1979
%P 257-287
%V 13
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/item/ITA_1979__13_3_257_0/
%G en
%F ITA_1979__13_3_257_0
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://geodesic.mathdoc.fr/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. | Zbl | MR

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

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

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

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. | mathdoc-id | Zbl | MR | EuDML

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

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

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

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

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

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