Hierarchies of recursive computationsFootnote†

†This research was supported in part by NSF grant MCS 74-02338.

References

• Cook , S.A. 1971 . The complexity of theorem-proving procedures . Proceedings of the Third Annual ACM Symposium on Theory of Computing . 1971 . pp. 151 – 158 .
   Google Scholar
• Cook , S.A. 1971 . Characterizations of pushdown machines in terms of time-bounded computers . J. ACM , 18 : 4 – 18 .
   Web of Science ®Google Scholar
• Fischer , M.J. and Rosenberg , A.L. Limited random access Turing machines . Proceedings of the Ninth Annual Symposium on Switching and Automata Theory . pp. 356 – 367 . IEEE .
   Google Scholar
• Hopcroft , J.E. and Ullman , J.D. 1969 . Formal Languages and Their Relation to Automata , Reading, Massachusetts : Addison-Wesley .
   Google Scholar
• Savitch , W.J. 1970 . Relationships between nondeterministic and deterministic tape complexities . J. Comput. Syst. Scis , 4 : 177 – 192 .
   Google Scholar
• Savitch , W.J. 1977 . Recursive Turing Machines . Intern. J. Computer Math , 6 : 3 – 31 .
   Web of Science ®Google Scholar
• Savitch , W.J. and Stimson , M.J. The complexity of recursive algorithms . Proceedings of the 1975 Conference on Information Sciences and Systems . April , pp. 269 – 275 . Maryland : The Johns Hopkins University .
   Google Scholar
• Seifera s , J.I. , Fischer , M.J. and Meyer , A.R. 1973 . Refinements of the nondeterministic time and space hierarchies . Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory . 1973 . pp. 130 – 137 .
   Google Scholar
• Stimson , M.J. June 1976 . “ The Complexity of Parallel Algorithms ” . In Ph.D. Thesis , June , University of California at San Diego .
   Google Scholar
• Stimson , M.J. and Savitch , W.J. Time Hierarchies of recursive computations . Proceedings of the 1977 Conference on Information Sciences and Systems . April , pp. 6 – 7 . Baltimore, Maryland : The Johns Hopkins University .
   Google Scholar