×

zbMATH — the first resource for mathematics

A hierarchy of primitive recursive sequence functions. (English) Zbl 0402.03041

MSC:
03D55 Hierarchies of computability and definability
03D20 Recursive functions and relations, subrecursive hierarchies
PDF BibTeX XML Cite
Full Text: EuDML
References:
[1] 1. G. AUSIELLO, Complessità di calcolo delle funzioni, Boringhieri, Torino, 1975.
[2] 2. P. AXT, Iteration of Primitive Recursion, Zeisch. f. math. Logik und Grundl. d. Math., Vol. 9, 1965, pp. 253-255. Zbl0144.00201 MR195719 · Zbl 0144.00201 · doi:10.1002/malq.19650110310
[3] 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. Zbl0312.68049 MR432436 · Zbl 0312.68049
[4] 4. J. P. CLEAVE, A Hierarchy of Primitive Recursive Functions, Zeitsch. f. math. Logik und Grundl. d. Math., Vol. 9, 1963, pp. 331-345. Zbl0124.00303 MR159754 · Zbl 0124.00303 · doi:10.1002/malq.19630092202
[5] 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. Zbl0192.08702 MR207561 · Zbl 0192.08702
[6] 6. S. EILENBERG and C. C. ELGOT, Iteration and Recursion, Proc. Nat.Acad. Sci.U.S.A., Vol. 61, 1968pp. 378-379. Zbl0193.31001 MR241291 · Zbl 0193.31001 · doi:10.1073/pnas.61.2.378
[7] 7. S. EILENBERG and C. C. ELGOT, Recursiveness, Academic Press, New York, 1970. Zbl0211.31101 MR268040 · Zbl 0211.31101
[8] 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. Zbl0324.02025 MR363836 · Zbl 0324.02025
[9] 9. G. GERMANO and A. MAGGIOLO-SCHETTINI, Sequence-to-Sequence Recursiveness, Information Processing Lett., Vol. 4, 1975, pp. 1-6. Zbl0311.02047 MR387037 · Zbl 0311.02047 · doi:10.1016/0020-0190(75)90050-2
[10] 10. G. GERMANO and A. MAGGIOLO-SCHETTINI, Proving a Compiler Correct: a Simple Approach, J. Comput. System Sc,. Vol. 10, 1975, pp. 370-383. Zbl0304.68022 MR371136 · Zbl 0304.68022 · doi:10.1016/S0022-0000(75)80007-9
[11] 11. A. GRZEGORCZYK, Some Classes of Recursive Functions, Rozprawy Mathematyczne, Vol. 4, 1953, pp.1-45. Zbl0052.24902 MR60426 · Zbl 0052.24902 · eudml:219317
[12] 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. Zbl0359.68019 MR520895 · Zbl 0359.68019
[13] 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] 14. H. MÜLLER, Characterization of the Elementary Functions in Terms of Nesting of Primitive Recursions, Recursive Function Theory Newsletters, Vol. 5, 1973.
[15] 15. R. W. RITCHIE, Classes of Recursive Functions Based on Ackermann’s Function, Pacific J. Math., Vol. 15, 1965, pp. 1027-1044. Zbl0133.24903 MR193013 · Zbl 0133.24903 · doi:10.2140/pjm.1965.15.1027
[16] 16. H. SCHWICHTENBERG, Rekursionszahlen und die Grzegorczyk Hierarchie, Arch. Math. Logik Grundlagenforsch., Vol. 12, 1969, pp. 85-97. Zbl0213.01801 MR253900 · Zbl 0213.01801 · doi:10.1007/BF01982053 · eudml:137821
[17] 17. D. TSICHRITZIS, A note on Comparison of Subrecursive Hiérarchies, Information Processing Lett., Vol. 1, 1971, pp. 42-44. Zbl0233.68016 MR305995 · Zbl 0233.68016 · doi:10.1016/0020-0190(71)90002-0
[18] 18. D. TSICHRITZIS, The Equivalence Problem of Simple Programs, J. Ass. Comput. Mach, Vol. 17, 1970, pp. 729-738. Zbl0209.02001 MR321346 · Zbl 0209.02001 · doi:10.1145/321607.321621
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.