A hierarchy of primitive recursive sequence functions
Fachini, E. ; Maggiolo-Schettini, A.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 13 (1979), p. 49-67 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1979__13_1_49_0,
     author = {Fachini, E. and Maggiolo-Schettini, A.},
     title = {A hierarchy of primitive recursive sequence functions},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {13},
     year = {1979},
     pages = {49-67},
     mrnumber = {525457},
     zbl = {0402.03041},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1979__13_1_49_0}
}

Fachini, E.; Maggiolo-Schettini, A. A hierarchy of primitive recursive sequence functions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 13 (1979) pp. 49-67. http://gdmltest.u-ga.fr/item/ITA_1979__13_1_49_0/

1. G. Ausiello, Complessità di calcolo delle funzioni, Boringhieri, Torino, 1975.

2. P. Axt, Iteration of Primitive Recursion, Zeisch. f. math. Logik und Grundl. d. Math., Vol. 9, 1965, pp. 253-255. | MR 195719 | Zbl 0144.00201

3. H. Beck, Zur Entscheidbarkeit der funktionalen Aquivalenz, Automata Theory and Formal Languages 2nd GI Conference, Lecture Notes in Computer Science, Vol. 33, 1975, pp. 127-133. | MR 432436 | Zbl 0312.68049

4. J. P. Cleave, A Hierarchy of Primitive Recursive Functions, Zeitsch. f. math. Logik und Grundl. d. Math., Vol. 9, 1963, pp. 331-345. | MR 159754 | Zbl 0124.00303

5. A. Cobham, The Intrinsic Computational Difficulty of Functions, Proc. Congress on Logic, Methodology and Philosophy of Science, Haifa, Israel, 1964, North-Holland, Amsterdam, 1964, pp. 24-30. | MR 207561 | Zbl 0192.08702

6. S. Eilenberg and C. C. Elgot, Iteration and Recursion, Proc. Nat.Acad. Sci.U.S.A., Vol. 61, 1968pp. 378-379. | MR 241291 | Zbl 0193.31001

7. S. Eilenberg and C. C. Elgot, Recursiveness, Academic Press, New York, 1970. | MR 268040 | Zbl 0211.31101

8. G. Germano and A. Maggiolo-Schettini, Quelques caractérisations des fonctions récursives partielles, C. R. Acad. Sc. Paris, t. 276, série A, 1973, pp. 1325-1327. | MR 363836 | Zbl 0324.02025

9. G. Germano and A. Maggiolo-Schettini, Sequence-to-Sequence Recursiveness, Information Processing Lett., Vol. 4, 1975, pp. 1-6. | MR 387037 | Zbl 0311.02047

10. G. Germano and A. Maggiolo-Schettini, Proving a Compiler Correct: a Simple Approach, J. Comput. System Sc,. Vol. 10, 1975, pp. 370-383. | MR 371136 | Zbl 0304.68022

11. A. Grzegorczyk, Some Classes of Recursive Functions, Rozprawy Mathematyczne, Vol. 4, 1953, pp.1-45. | MR 60426 | Zbl 0052.24902

12. H. Huwig and V. Claus, Das Äquivalenzproblem für spezielle Klassen von LOOP-Programmen, Theoretical Computer Science 3rd GI Conference, Lecture Notes in Computer Science, Vol. 48, 1977, pp. 73-82. | MR 520895 | Zbl 0359.68019

13. A. R. Meyer and D. M. Ritchie, The Complexity of LOOP Programs, Proc. 22nd A.C.M. Nat: Conference, Washington, D.C., 1968, pp. 465-469.

14. H. Müller, Characterization of the Elementary Functions in Terms of Nesting of Primitive Recursions, Recursive Function Theory Newsletters, Vol. 5, 1973.

15. R. W. Ritchie, Classes of Recursive Functions Based on Ackermann's Function, Pacific J. Math., Vol. 15, 1965, pp. 1027-1044. | MR 193013 | Zbl 0133.24903

16. H. Schwichtenberg, Rekursionszahlen und die Grzegorczyk Hierarchie, Arch. Math. Logik Grundlagenforsch., Vol. 12, 1969, pp. 85-97. | MR 253900 | Zbl 0213.01801

17. D. Tsichritzis, A note on Comparison of Subrecursive Hiérarchies, Information Processing Lett., Vol. 1, 1971, pp. 42-44. | MR 305995 | Zbl 0233.68016

18. D. Tsichritzis, The Equivalence Problem of Simple Programs, J. Ass. Comput. Mach, Vol. 17, 1970, pp. 729-738. | MR 321346 | Zbl 0209.02001