Complexity classes of formal languages

1. Baker, T., Gill, J. and Solovay, R., Relativization of the P = ? NP question. SIAM J. Computing, 4(1975), 431–422.

   Article  Google Scholar 

2. Baker, T. and Selman, A., A second step towards the polynomial hierarchy. Theoret. Comput. Sci., to appear.

   Google Scholar 

3. Book, R., Simple representations of certain classes of languages. J. Assoc. Comput. Mach., 25(1978), 23–31.

   Google Scholar 

4. Book, R., Polynomial space and transitive closure. SIAM J. Computing, 8(1979), to appear.

   Google Scholar 

5. Book, R., On languages accepted by space-bounded oracle machines. Acta Informatica, to appear.

   Google Scholar 

6. Book, R., Time, space, and relativizations. In preparation.

   Google Scholar 

7. Book, R., Greibach, S. and Wrathall, C., Reset machines. J. Comput. System Sci., to appear.

   Google Scholar 

8. Book, R. and Nivat, M., Linear languages and the intersection closures of classes of languages. SIAM J. Computing, 7(1978), 167–177.

   Article  Google Scholar 

9. Book, R., Nivat, M. and Paterson, M., Reversal-bounded acceptors and intersections of linear languages. SIAM J. Computing, 3(1974), 283–295.

   Article  Google Scholar 

10. Book, R. and Wrathall, C., On languages specified by relative acceptance. Theoret. Comput. Sci., 7(1978), 185–195.

    Article  Google Scholar 

11. Ginsburg, S., Greibach, S. and Hopcroft, J., Studies in Abstract Families of Languages, Memoir No. 87, Amer. Math. Soc., 1969.

    Google Scholar 

12. Grzegorczyk, A., Some classes of recursive functions. Rozprawy Matematyczne, IV(1953), 1–46.

    Google Scholar 

13. Jones, N., Formal Languages and Rudimentary Attributes, Ph.D. dissertation, University of Western Ontario, 1967.

    Google Scholar 

14. Jones, N., Classes of automata and transitive closure. Info. Control, 13(1968), 207–229.

    Article  Google Scholar 

15. Kleene, S.C., Introduction to Metamathematics. Van Nostrand, Princeton, N.J., 1952.

    Google Scholar 

16. McCloskey, T., Abstract families of length-preserving processors. J. Comput. System Sci., 10(1975), 394–427.

    Google Scholar 

17. Rogers, H., Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.

    Google Scholar 

18. Simon, I., On Some Subrecursive Reducibilities, Ph.D. dissertation, Stanford University, 1977.

    Google Scholar 

19. Simon, I. and Gill, J., Polynomial reducibilities and upwards diagonalizations. Proc. 9th ACM Symp. Theory of Computing (1977), 186–194.

    Google Scholar 

20. Stockmeyer, L., The polynomial-time hierarchy. Theoret. Comput. Sci., 3(1976), 1–22.

    Article  Google Scholar 

21. Wrathall, C., Subrecursive Predicates and Automata, Ph.D. dissertation, Harvard University, 1975.

    Google Scholar 

22. Wrathall, C., Complete sets and the polynomial-time hierarchy. Theoret. Comput. Sci., 3(1976), 23–33.

    Article  Google Scholar 

23. Wrathall, C., Rudimentary predicates and relative computation. SIAM J. Computing, 7(1978), 194–209.

    Article  Google Scholar 

24. Wrathall, C., The linear and polynomial-time hierarchies. In preparation.

    Google Scholar 

Download references