Subrecursive Programming Languages, Part I

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Subrecursive Programming Languages, Part I: efficiency and program structure

Full text

Pdf (1.89 MB)

Source

Journal of the ACM (JACM) archive
Volume 19 , Issue 3 (July 1972) table of contents

Pages: 526 - 568

Year of Publication: 1972

ISSN:0004-5411

Authors

Robert L. Constable	Computer Science Department, Upson Hall, Cornell University, Ithaca, New York
Allan B. Borodin	Department of Computer Science, University of Toronto, Toronto 181, Ontario, Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 17, Citation Count: 10

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321707.321721 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
	2	Manuel Blum, On effective procedures for speeding up algorithms, Proceedings of the first annual ACM symposium on Theory of computing, p.43-53, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805420]
	3	BLUM, M. On the size of machines. Inform. Contr. 11 (1967), 257-265.
	4	BORODIN, A. Complexity classes of recursive functions and the existence of complexity gaps. Conf. Record of ACM Symp. on Theory of Computing, Marina del Rey, Calif., 1969, pp. 67-78.
	5	CLEAVE, JOHN P. A hierarchy of primitive recursive functions. Z. Math. Logik Grund: lagen Math. 9 (1963), 331-345.
	6	COBHAM, A. The intrinsic computational difficulty of functions. Proe. 1964 Internat. Congress for Logic, Methodology, and the Philosophy of Science. North-Holland, Amsterdam, 1965, pp. 24-30.
	7	Robert L. Constable, Upward and Downward Diagonalization over Axiomatic Complexity Classes, Cornell University, Ithaca, NY, 1969
	8	Robert L. Constable, On the size of programs in subrecursive formalisms, Proceedings of the second annual ACM symposium on Theory of computing, p.1-9, May 04-06, 1970, Northampton, Massachusetts, United States [doi>10.1145/800161.805143]
	9	Calvin C. Elgot , Abraham Robinson, Random-Access Stored-Program Machines, an Approach to Programming Languages, Journal of the ACM (JACM), v.11 n.4, p.365-399, Oct. 1964 [doi>10.1145/321239.321240]
	10	ENGLER, ERWIN. Formal Languages; Automata and Structures. Markham Co., Chicago, 1968.
	11	GRZEGORCZYK, A. Some classes of recursive functions. Rozprawy Mathematcyzne, No. 4, Instytut Matematyczny Polskiej Akademie Nauk, Warsaw, Poland, 1953, pp. 1-45.
	12	HARTMANIS, Z., AND STEARNS, R.E. On the computational complexity of algorithms. Trans. AMS 117, 5 (1965), 285-306.
	13	J. Hartmanis , J. E. Hopcroft, An Overview of the Theory of Computational Complexity, Journal of the ACM (JACM), v.18 n.3, p.444-475, July 1971 [doi>10.1145/321650.321661]
	14	KLEENE, S.C. Introduction to Metamathematics. Van Nostrand, Princeton, N. J., 1952.
	15	KNUTH, D., AND FLOYD, R. Notes on avoiding " go to" statements. Inform. Proc. Letters 1 (1971), 23-31.
	16	LEwis, F. D. The enumerability and invariance of complexity classes. J. Comput. Syst. Sci. 5 (1971), 286-303.
	17	E. M. McCreight , A. R. Meyer, Classes of computable functions defined by bounds on computation: Preliminary Report, Proceedings of the first annual ACM symposium on Theory of computing, p.79-88, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805423]
	18	MEYER, A. R., AND FISCHER, P. C. On computational speed-up. IEEE Conf. Record, 9th Annual SWAT, 1968, pp. 351-355.
	19	Albert R. Meyer , Dennis M. Ritchie, The complexity of loop programs, Proceedings of the 1967 22nd national conference, p.465-469, January 1967, Washington, D.C., United States [doi>10.1145/800196.806014]
	20	MEYER, A. R., AND RITCHIE, D. M. A classification of functions by computational complexity. Proc. Hawaii Intern. Conf. on System Sciences, U. of Hawaii Press, 1968, pp. 17-19.
	21	Marvin Lee Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Upper Saddle River, NJ, 1967
	22	RrrCHIE, R.W. Classes of predictably computable functions. Trans. AMS 106 (1963), 139-173.
	23	ROBINSON, R.M. Primitive recursive functions. Bull. AMS 58 (1947), 915-942.
	24	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
	25	SCOTT, DANA. Some definitional suggestions for automata theory. J. Comput. Syst. Sci. I (1967), 187-212.
	26	J. C. Shepherdson , H. E. Sturgis, Computability of Recursive Functions, Journal of the ACM (JACM), v.10 n.2, p.217-255, April 1963 [doi>10.1145/321160.321170]
	27	Peter. Wegner, Programming Languages, Information Structures, and Machine Organization., McGraw Hill Text, 1968

CITED BY 10

	F. G. Pagan, On the teaching of disciplined programming, ACM SIGPLAN Notices, v.8 n.10, October 1973
	A. J. Kfoury, Analysis of simple programs over different sets of primitives, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.56-61, January 28-30, 1980, Las Vegas, Nevada
	John C. Cherniavsky , Samuel N. Kamin, A Complete and Consistent Hoare Axiomatics for a Simple Programming Language, Journal of the ACM (JACM), v.26 n.1, p.119-128, Jan. 1979
	J. Cherniavsky , S. Kamin, A complete and consistent hoare axiomatics for a simple programming language, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-9, January 17-19, 1977, Los Angeles, California
	Dexter Kozen, Indexing of subrecursive classes, Proceedings of the tenth annual ACM symposium on Theory of computing, p.287-295, May 01-03, 1978, San Diego, California, United States
	Robert E. Noonan, Towards a canonical form for computer programs, Proceedings of the 1975 annual conference, p.235-240, January 1975
	Kurt Mehlhorn, Polynomial and abstract subrecursive classes, Proceedings of the sixth annual ACM symposium on Theory of computing, p.96-109, April 30-May 02, 1974, Seattle, Washington, United States
	Eitan M. Gurari , Oscar H. Ibarra, The complexity of the equivalence problem for counter machines, semilinear sets, and simple programs, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.142-152, April 30-May 02, 1979, Atlanta, Georgia, United States
	Eitan M. Gurari , Oscar H. Ibarra, The Complexity of the Equivalence Problem for Simple Programs, Journal of the ACM (JACM), v.28 n.3, p.535-560, July 1981
	Robert L. Constable, Type two computational complexity, Proceedings of the fifth annual ACM symposium on Theory of computing, p.108-121, April 30-May 02, 1973, Austin, Texas, United States