Ordinal Hierarchies and Naming Complexity Classes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Ordinal Hierarchies and Naming Complexity Classes

Full text

Pdf (1.46 MB)

Source

Journal of the ACM (JACM) archive
Volume 20 , Issue 4 (October 1973) table of contents

Pages: 668 - 686

Year of Publication: 1973

ISSN:0004-5411

Authors

Leonard Bass	Computer Science and Experimental Statistics Department, University of Rhode Island, Kingston, Rhode Island
Paul Young	Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA and Purdue University, Lafayette, Indiana

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 25, Citation Count: 0

Additional Information:

references index terms collaborative colleagues peer to peer

Tools and Actions:	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/321784.321793 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	Giorgio Ausiello, On bounds on the number of steps to compute functions, Proceedings of the second annual ACM symposium on Theory of computing, p.41-47, May 04-06, 1970, Northampton, Massachusetts, United States [doi>10.1145/800161.805148]
	2	AXT, P. On a subrecursive hierarchy and primitive recursive degrees. Trans. Amer. Math. Soc. 92 (1959), 85-105.
	3	Leonard Joel Bass, Hierarchies based on computational complexity and irregularities of classdetermining measured sets, 1970
	4	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]
	5	A. Borodin, Computational Complexity and the Existence of Complexity Gaps, Journal of the ACM (JACM), v.19 n.1, p.158-174, Jan. 1972 [doi>10.1145/321679.321691]
	6	CLEAVE, J.P. A hierarchy of primitive recursive functions. Z. Math. Logik Grundlagen Math. 9 (1963), 331-345.
	7	COBHAM, A. The intrinsic computational difficulty of functions. Proc. 1964 Cong. for Logic Math. and Phil. of Science, North-Holland Pub. Co., Amsterdam, 1965, pp. 24-30.
	8	Robert L. Constable, The Operator Gap, Journal of the ACM (JACM), v.19 n.1, p.175-183, Jan. 1972 [doi>10.1145/321679.321692]
	9	FEFERMAN, S. Classifications of recursive functions by means of hierarchies. Trans. Amer. Math. Soc. 104 (1962), 101-122.
	10	F~FERMAN, ~., AND SPECTOR, (~. Incompleteness along paths in progressions of theories. J. Symbolic Logic P7 (1962), 383-390.
	11	GRZEGOnCZYK, A. Some classes of recursive functions. Rozprany Mat. {Warsaw} (1953), 1-46.
	12	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]
	13	HARTMANIS, J., AND STEARNS, R.E. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117 (1965), 285-306.
	14	HELM, J., MEYER, A., AND YOUNG, P. On orders of enumerations and translations. Pacific J. Math. (to appear).
	15	HELM, J., MEYER A., AND YOUNG, P. Notes on difficulties of enumerations. Computer Sci. Dep. Rep. TR 61, Purude U., Lafayette, Ind., Jan. 1972, 1-16.
	16	KhEEN~., S. Extension of au effectively generated class of functions by enumeration. Colloq. Math. {Warsaw} 6 (1958), 67-78.
	17	KLEENE, S. On the forms of predicates in the theory of constructive ordinals, II. Amer. J. Math. 77 (1955), 405-428.
	18	KREISE~, G. Non-uniqueness results for transfinite progressions. OOR Tech. Rep. No. 4, Stanford U., Stanford, Calif., Feb. 1961; also, Bull. Acad. Polon. Sci. 8 (1960).
	19	L. H. Landweber , E. L. Robertson, Recursive Properties of Abstract Complexity Classes, Journal of the ACM (JACM), v.19 n.2, p.296-308, April 1972 [doi>10.1145/321694.321702]
	20	Edward M. Mccreight, Classes of computable functions defined by bounds on computation, 1969
	21	MEYER, A., AND F~SCHER, P. Computational speed-up by effective operators. J. Symbolic Logic 87 (1972), 5568.
	22	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]
	23	ME~ER, A., AND MCCREIGHT, E. Properties of bounds on computation. Proc. Princeton Symp. on Information Sciences, 1969, pp. 154-156.
	24	MEYER, A., AND MOLL, 1~. Honest bounds for complexity classes of recursive functions. Proj. MAC Rep., MIT, Cambridge, Mass., Apr. 1972, pp. 1-22.
	25	MOLL, R. Complexity classes of recursive functions. Doctoral Diss., MIT, Cambridge, Mass., : {973.
	26	MOSCttOVAKIS, Y. A remark on subrecursive hierarchies, a useful unpublished result proved in 1964 (personal communication).
	27	MEYER, A., Am) R~cmE, D. A classification of functions by computational complexity. Proc. Hawaii Internat. Conf. o11 System Sciences, U. of Hawaii, 1968, pp. 17-19.
	28	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]
	29	PARIKH, R. On non-uniqueness in transfinite progressions. J. Indian Math. Soc. 31 (1967), 23-32.
	30	RAmN, M.O. Degrees of difficulty of computing a function and a partial ordering of recursive sets. Tech. Rep. 2, Hebrew U., Jerusalem, Israel, 1960.
	31	RITCHIE, D.M. Program structure and computational complexity. Doctoral Diss., Harvard U., Cambridge, Mass., 1969.
	32	RlWCmE, R. W. Classes of predictably computable function. Trans. Amer. Math. Soc. 106 (1963), 139-173.
	33	RITCmE, R.W. Classes of recursive functions based on Ackermann's function. Pacific J. Math. 15 (1965), 1027-1044.
	34	l)~o~mN, J. Subrecursive hierarchies. Doctoral Diss., Princeton U., Princeton, N. J., 1965.
	35	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
	36	Paul R. Young, Toward a Theory of Enumerations, Journal of the ACM (JACM), v.16 n.2, p.328-348, April 1969 [doi>10.1145/321510.321525]
	37	YOUNG, P. Easy constructions in complexity theory: gap and speed-up theorems. Proc. Amer. Math. Soc. 87 (1973), 555-563.