Canal, Richard Complexite de la reduction en logique combinatoire. (French) Zbl 0432.03012 RAIRO, Inf. Théor. 12, 339-367 (1978). Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 2 Documents MSC: 03B40 Combinatory logic and lambda calculus Keywords:weak combinatory logic; reduction complexity; rewriting process; reduction of applicative combinations of proper combinators; upper and lower bounds on the length of the reduction; normal form Citations:Zbl 0081.241; Zbl 0332.02033; Zbl 0364.94033 × Cite Format Result Cite Review PDF Full Text: EuDML References: [1] 1. G. AUSIELLO, Abstract Computational Complexity and Cycling Computations, J.C.S.S., vol. 5, 1971, p. 118-128. Zbl0225.02025 MR281618 · Zbl 0225.02025 · doi:10.1016/S0022-0000(71)80030-2 [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 \lambda Calculus and Computer Science Theory, Proceedings of the Symposium held in Rome, C. Bohm, Ed., Springer Verlag, 1975, p. 288-297. Zbl0332.02033 MR479987 · Zbl 0332.02033 [5] 5. M. BLUM, A Machine Independent Theory of the Complexity of Recursive Functions, J.A.C.M., vol. 14, n^\circ 2, 1967, p. 322-336. Zbl0155.01503 MR235912 · Zbl 0155.01503 · doi:10.1145/321386.321395 [6] 6. C. BOHMet M. DEZANI-CIANCAGLINI, \lambda -Terms as Total or Partial Functions on Normal Forms, in \lambda -Calculus and Computer Science Theory, Proceedings of the Symposium held in Rome, C. Bohm, Ed., Springer Verlag, 1975, p. 96-121. Zbl0342.02017 MR485296 · Zbl 0342.02017 [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.68037 MR429500 · Zbl 0309.68037 [8] 8. C. BOHM, M. COPPOet M. DEZANI-CIANCAGLINI, Terminations Tests inside \lambda -Calculus, in Automata, Languages and Programming, Fourth Colloquium, University of Turku, A. Salomaa et M. Steinby, Ed., Springer Verlag, 1977, p. 95-110. Zbl0358.02025 MR465807 · Zbl 0358.02025 [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. · Zbl 0432.03012 [12] 12. H. B. CURRY, R. FEYS et W. CRAIG, Combinatory Logic, vol. 1, North Holland, Amsterdam, 1968. Zbl0175.27601 MR244051 · Zbl 0175.27601 [13] 13. M. DEZANI-CIANCAGLINI et S. RONCHI DELLA ROCA, Computational Complexity and Structures of \lambda -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 · Zbl 0269.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 · Zbl 0203.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^\circ 4, 1960, p. 184-195. Zbl0101.10413 · Zbl 0101.10413 · doi:10.1145/367177.367199 [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.00805 MR285394 · Zbl 0217.00805 [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 · Zbl 0364.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^\circ 5, 1970, p. 308-319. Zbl0193.15101 · Zbl 0193.15101 · doi:10.1145/362349.362364 [22] 22. B. ROBINET, Un modèle fonctionnel des structures de contrôle, R.A.I.R.O. Informatique théorique, vol. 11, n^\circ 3, 1977, p. 213-236. Zbl0389.68015 MR502167 · Zbl 0389.68015 [23] 23. J. B. ROSSER, A Mathematical Logic without Variables, Annals of Maths, n^\circ 2, 36, 1935, p. 127-150. MR1503213 JFM61.0056.02 · Zbl 0011.00201 · doi:10.2307/1968669 [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.24704 MR205849 · Zbl 0158.24704 · doi:10.1305/ndjfl/1093957876 [26] 26. J. VUILLEMIN, Proof Techniques for Recursive Programs, Ph. D. Thesis, Stanford, 1973. This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.