Complexité de la réduction en logique combinatoire
Canal, Richard
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 12 (1978), p. 339-367 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1978__12_4_339_0,
     author = {Canal, Richard},
     title = {Complexit\'e de la r\'eduction en logique combinatoire},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {12},
     year = {1978},
     pages = {339-367},
     mrnumber = {517635},
     zbl = {0432.03012},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/ITA_1978__12_4_339_0}
}

Canal, Richard. Complexité de la réduction en logique combinatoire. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 12 (1978) pp. 339-367. http://gdmltest.u-ga.fr/item/ITA_1978__12_4_339_0/

1.G. Ausiello, Abstract Computational Complexity and Cycling Computations, J.C.S.S., vol. 5, 1971, p. 118-128. | MR 281618 | Zbl 0225.02025

2.G. Ausiello, Computational Complexity. Main Results and a Commentary, Seminaire I.R.I.A., 1972.

3.G. Ausiello, Complessita di Calcolo delleFunzioni. Boringhieri, Ed., 1975.

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

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

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

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

8.C. Bohm, M. CoppoetM. 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. | MR 465807 | Zbl 0358.02025

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

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.R. Canal, Étude de la complexité de calcul en logique combinatoire, Thèse 3e Cycle, Université Paul-Sabatier, 1978.

12.H. B. Curry, R. Feys et W. Craig, Combinatory Logic, vol. 1, North Holland, Amsterdam, 1968. | MR 244051 | Zbl 0175.27601

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.J. R. Hindley, B. LercheretJ. P. Seldin, Introduction to CombinatoryLogic, Cambridge University Press, 1972. | Zbl 0269.02005

15.P. J. Landin, A Lambda-Calculus Approach, Advances in Programming and Non Numerical Computation, Pergamon Press, 1966, p. 97-141. | Zbl 0203.16406

16. J. J. Lévy, Réductions correctes et optimales dans le Lambda-Calcul, Thèse de Doctorat, Université Paris-VII, 1978.

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

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

19. A. Pettorossi, Sulla Terminazione in Classi Subricorsive di Algorithmi, A.I.C.A., Congress Genova, 1975.

20. A. Pettorossi, Combinators as Tree-transducers, Colloque sur les Arbres en Algèbre et en Programmation, Lille, 1977. | Zbl 0364.94033

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

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. | Numdam | MR 502167 | Zbl 0389.68015

23. J. B. Rosser, A Mathematical Logic without Variables, Annals of Maths, n° 2, 36, 1935, p. 127-150. | JFM 61.0056.02 | MR 1503213

24. C. Ruggiu, De l'organigramme à la formule, Thèse de Doctorat, Université Pierre-et-Marie-Curie, Paris, 1974.

25. L. E. Sanchis, Types of Combinatory Logic, Notre-Dame Journal of Formal Logic (5). 1964, p. 161-180. | MR 205849 | Zbl 0158.24704

26. J. Vuillemin, Proof Techniques for Recursive Programs, Ph. D. Thesis, Stanford, 1973.