×

Polynomial and abstract subrecursive classes. (English) Zbl 0329.68049


MSC:

68Q25 Analysis of algorithms and problem complexity
68W99 Algorithms in computer science
68Q45 Formal languages and automata
03D20 Recursive functions and relations, subrecursive hierarchies
03D25 Recursively (computably) enumerable sets and degrees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullmann, J. D., (The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Mass.)
[2] Axt, P., On a subrecursive hierarchy and primitive recursive degrees, Trans. Amer. Math. Soc., 92 (1959) · Zbl 0087.01102
[3] Bennet, J. H., On spectra, (Doctoral Dissertation (1962), Princeton University) · Zbl 0057.35903
[4] Blum, M., A machine-independent theory of the complexity of recursive functions, J. Assoc. Comput. Mach., 14 (1967) · Zbl 0155.01503
[5] Cobham, A., The intrinsic computational difficulty of functions, (“Logic, Methodology and Philosophy of Science”, Proceedings of 1964 Conference (1965), North-Holland: North-Holland Amsterdam) · Zbl 0192.08702
[6] R. L. Constable; R. L. Constable · Zbl 0468.68060
[7] Constable, R. L., Type two computational complexity, (Proceedings of the Fifth ACM Symposium on the Theory of Computing (1973)), 108-122
[8] Constable, R. L.; Borodin, A. B., Subrecursive programming languages. I. Efficiency and program structure, J. Assoc. Comput. Mach., 19 (1972) · Zbl 0259.68036
[9] Cook, S. A., The complexity of theorem proving procedures, (Proceedings of the Third ACM Symposium on the Theory of Computing (1971)) · Zbl 0363.68125
[10] Grzegorczyk, A., Some classes of recursive functions, Rozprawy Mat. Warsaw, 4 (1953) · Zbl 0224.02029
[11] J. Hartmanis; J. Hartmanis
[12] Hartmanis, J.; Hopcroft, J. E., An overview of the theory of computational complexity, J. Assoc. Comput. Mach., 18 (1971) · Zbl 0226.68024
[13] Hartmanis, J.; Stearns, R. E., On the computational complexity of algorithms, Trans. Amer. Math. Soc., 117 (May 1965)
[14] Hopcroft, J. E.; Ullman, J. D., (Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, Mass.) · Zbl 0196.01701
[15] Hunt, H. B., On the time and tape complexity of languages, I, (Proceedings of the Fifth ACM Symposium on the Theory of Computing (1973)) · Zbl 0357.68090
[16] Jones, N. D., Reducibility among combinatorial problems, (Princeton Conference (1973)) · Zbl 0317.02039
[17] Kleene, S. C., Extension of an effectively enumerated class of functions by enumeration, Colloq. Math., 6 (1958) · Zbl 0085.24602
[18] Ladner, R. E., On the structure of polynomial time reducibility, J. Assoc. Comput. Mach., 22, 155-171 (1975) · Zbl 0322.68028
[19] N. LynchTrans. Amer. Math. Soc.A. Meyer and M. Fisher; N. LynchTrans. Amer. Math. Soc.A. Meyer and M. Fisher
[20] Machtey, M., Augmented loop languages and classes of computable functions, J. Comput. System Sci., 6 (1972) · Zbl 0312.68028
[21] Machtey, M., On the density of honest subrecursive classes, J. Comput. System Sci., 10, 183-199 (1975) · Zbl 0336.02031
[22] Machtey, M., The honest subrecursive classes are a lattice, Inform. Contr., 24, 247-263 (1974) · Zbl 0291.02026
[23] Machtey, M., On a notion of helping, (Proceedings of the 14th IEEE SWAT Conference (1973))
[24] Machtey, M., Helping and the meet of pairs of honest subrecursive classes, Inform. Contr., 28, 76-89 (1975) · Zbl 0301.68057
[25] Machtey, M., Honesty techniques and polynomial degrees, (Project MAC Conference on Concrete Complexity (1973)), (No printed proceedings.) · Zbl 0218.02034
[26] M. MachteyTheoretical Computer Science; M. MachteyTheoretical Computer Science · Zbl 0332.68040
[27] McCreight, E. M.; Meyer, A. R., Classes of computable functions defined by bounds on computation, (Proceedings of the First ACM Symposium on the Theory of Computing (1969)) · Zbl 1283.03074
[28] Mehlhorn, K., On the size of sets of computable functions, (Proceedings of the 14th IEEE SWAT Conference (1973))
[29] Mehlhorn, K., The “almost all” theory of subrecursive degrees is decidable, (Proceedings of the Second Colloquium on Automata, Languages and Programming. Proceedings of the Second Colloquium on Automata, Languages and Programming, Springer Lecture Notes (1974), Springer-Verlag: Springer-Verlag New York/Berlin) · Zbl 0284.68041
[30] Meyer, A. R., Weak monadic second order theory of succesor is not elementary recursive, Project MAC, Technical Memorandum, 38 (1973)
[31] Meyer, A. R.; Ritchie, D. M., A classification of the recursive functions, Z. Math. Logik Grundlagen Math., 18 (1972) · Zbl 0247.02037
[32] Meyer, A. R.; Stockmeyer, L. I., Word problems requiring exponential time, (Proceedings of the Fifth ACM Symposium on Theory of Computing (1973)) · Zbl 0359.68050
[33] Moll, R., Complexity classes of recursive functions, Project MAC TP-110 (1973)
[34] Mostowski, A., Ueber gewisse universelle Relationen, Ann. Soc. Polon. Math., 17 (1938)
[35] Post, E., Recursively enumerable sets and their decision problems, Bull. Amer. Math. Soc., 50 (1944) · Zbl 0063.06328
[36] Ritchie, R. W., Classes of predictably computable functions, Trans. Amer. Math. Soc., 106, 139-173 (1963) · Zbl 0107.01001
[37] Rogers, H., (Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York) · Zbl 0183.01401
[38] Rogers, H., Gödel numberings of partial recursive functions, J. Symbolic Logic, 23, 331-341 (1958) · Zbl 0088.01602
[39] Strong, H. R., Algebraically generalized recursive function theory, IBM J. Res. Develop. (Nov. 1968)
[40] Wagner, E. G., Uniformly reflexive structures: An axiomatic approach to computability, (“Logic, Computability, and Automata”, Proceedings of the Joint RADC-HAC Symposium, Trinkaus Manor. “Logic, Computability, and Automata”, Proceedings of the Joint RADC-HAC Symposium, Trinkaus Manor, Oriskany, N.Y. (1965))
[41] Weihrauch, K., (Doctoral Dissertation (1972), Bonn University)
[42] Sacks, G. E., (Degrees of Unsolvability (1963), Princeton University: Princeton University Princeton, N.J.) · Zbl 0143.25302
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.