Complexité de la réduction en logique combinatoire

 Access to full text

 Full (PDF)

1. 1. G. AUSIELLO, Abstract Computational Complexity and Cycling Computations, J.C.S.S., vol. 5, 1971, p. 118-128. Zbl0225.02025MR281618
2. 2. G. AUSIELLO, Computational Complexity. Main Results and a Commentary, Seminaire I.R.I.A., 1972. 
3. 3. G. AUSIELLO, Complessita di Calcolo delleFunzioni. Boringhieri, Ed., 1975. 
4. 4. C. BATINI et A. PETTOROSSI, On Subrecursiveness in Weak Combinatory Logic, in λ Calculus and Computer Science Theory, Proceedings of the Symposium held in Rome, C. Bohm, Ed., Springer Verlag, 1975, p. 288-297. Zbl0332.02033MR479987
5. 5. M. BLUM, A Machine Independent Theory of the Complexity of Recursive Functions, J.A.C.M., vol. 14, n° 2, 1967, p. 322-336. Zbl0155.01503MR235912
6. 6. C. BOHMet M. DEZANI-CIANCAGLINI, λ-Terms as Total or Partial Functions on Normal Forms, in λ-Calculus and Computer Science Theory, Proceedings of the Symposium held in Rome, C. Bohm, Ed., Springer Verlag, 1975, p. 96-121. Zbl0342.02017MR485296
7. 7. C. BOHM et M. DEZANI-CIANCAGLINI, Combinatorial Problems, Combinator Equations and Normal Forms, in Automata, Languages and Programming, 2nd Colloquium, University of Saarbrücken, J. Loeckx, Ed., Springer Verlag, 1974, p. 185-199. Zbl0309.68037MR429500
8. 8. C. BOHM, M. COPPOet M. DEZANI-CIANCAGLINI, Terminations Tests inside λ-Calculus, in Automata, Languages and Programming, Fourth Colloquium, University of Turku, A. Salomaa et M. Steinby, Ed., Springer Verlag, 1977, p. 95-110. Zbl0358.02025MR465807
9. 9. C. BOHM, The CUCH as a Formal and Description Language, in Formal Languages, Description Languages for Computer Programming, T. B. Steel, Ed., North Holland, 1966, p. 179-197, 
10. 10. R. CANAL et J. VIGNOLLE, Effet cachant et complexité de réduction en logique combinatoire, Rapport interne Université Paul-Sabatier, Laboratoire « Langages et Systèmes Informatiques », 1978. 
11. 11. R. CANAL, Étude de la complexité de calcul en logique combinatoire, Thèse 3e Cycle, Université Paul-Sabatier, 1978. Zbl0432.03012
12. 12. H. B. CURRY, R. FEYS et W. CRAIG, Combinatory Logic, vol. 1, North Holland, Amsterdam, 1968. Zbl0175.27601MR244051
13. 13. M. DEZANI-CIANCAGLINI et S. RONCHI DELLA ROCA, Computational Complexity and Structures of λ-Terms, in Programmation, Proceedings of the 2nd International Symposium on Programming, B. Robinet, Ed., Dunod, Paris, 1976, p. 160-181. 
14. 14. J. R. HINDLEY, B. LERCHERet J. P. SELDIN, Introduction to CombinatoryLogic, Cambridge University Press, 1972. Zbl0269.02005
15. 15. P. J. LANDIN, A Lambda-Calculus Approach, Advances in Programming and Non Numerical Computation, Pergamon Press, 1966, p. 97-141. Zbl0203.16406
16. 16. J. J. LÉVY, Réductions correctes et optimales dans le Lambda-Calcul, Thèse de Doctorat, Université Paris-VII, 1978. 
17. 17. J. MCCARTHY, Recursive Functions of Symbolic Expressions and their Computat by Machine, Part I, Comm. A.C.M., vol. 3, n° 4, 1960, p. 184-195. Zbl0101.10413
18. 18. L. NOLIN, Logique Combinatoire et Algorithmes, C.R. Académie des Sciences, Paris, t. 272, p. 1435-1438 et p. 1485-1488, série A, 1971. Zbl0217.00805MR285394
19. 19. A. PETTOROSSI, Sulla Terminazione in Classi Subricorsive di Algorithmi, A.I.C.A., Congress Genova, 1975. 
20. 20. A. PETTOROSSI, Combinators as Tree-transducers, Colloque sur les Arbres en Algèbre et en Programmation, Lille, 1977. Zbl0364.94033
21. 21. J. C. REYNOLDS, A simple Typeless Language Based on the Principle of Completeness and the Reference Concept, Comm. A.C.M., vol. 13, n° 5, 1970, p. 308-319. Zbl0193.15101
22. 22. B. ROBINET, Un modèle fonctionnel des structures de contrôle, R.A.I.R.O. Informatique théorique, vol. 11, n° 3, 1977, p. 213-236. Zbl0389.68015MR502167
23. 23. J. B. ROSSER, A Mathematical Logic without Variables, Annals of Maths, n° 2, 36, 1935, p. 127-150. Zbl0011.00201MR1503213JFM61.0056.02
24. 24. C. RUGGIU, De l'organigramme à la formule, Thèse de Doctorat, Université Pierre-et-Marie-Curie, Paris, 1974. 
25. 25. L. E. SANCHIS, Types of Combinatory Logic, Notre-Dame Journal of Formal Logic (5). 1964, p. 161-180. Zbl0158.24704MR205849
26. 26. J. VUILLEMIN, Proof Techniques for Recursive Programs, Ph. D. Thesis, Stanford, 1973. 

1. M. Dezani-Ciancaglini, S. Ronchi Della Rocca, L. Saitta, Complexity of $\lambda$-term reductions