×

On languages specified by relative acceptance. (English) Zbl 0385.68061


MSC:

68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Baker, T.; Gill, J.; Solovay, R., Relativizations of the P = ? NP question, SIAM J. comput., 4, 431-442, (1975) · Zbl 0323.68033
[2] T. Baker and A. Selman, A second step towards the polynomial hierarchy, Theoret. Comput. Sci. (to appear). · Zbl 0397.03023
[3] Book, R., Simple representations of certain classes of languages, J. assoc. comput. Mach., 25, 23-31, (1978) · Zbl 0364.68073
[4] Book, R.; Greibach, S.; Wegbreit, B., Time-and tape-bounded Turing acceptors and afls, J. comput. syst. sci., 4, 606-621, (1970) · Zbl 0206.28702
[5] Book, R.; Nivat, M., Linear languages and the intersection closures of classes of languages, SIAM J. comput., 7, (1978), to appear · Zbl 0376.68049
[6] Ginsburg, S.; Greibach, S., Abstract families of languages, (), 1-32, Memoir No. 87 · Zbl 0308.68058
[7] Greibach, S., Control sets on context-free grammar forms, J. comput. syst. sci., 15, 35-98, (1977) · Zbl 0359.68093
[8] Greibach, S., One-way finite visit automata, Theoret. comput. sci., 6, 175-221, (1978) · Zbl 0368.68059
[9] Grzegorczyk, A., Some classes of recursive functions, Rozprawy matematyczne, IV, 1-46, (1953)
[10] Itoga, S., Comparing language operations, Math. syst. theory, 10, 305-321, (1977) · Zbl 0369.68042
[11] Jones, N., Space-bounded reducibility among combinatorial problems, J. comput. syst. sci., 11, 68-85, (1975) · Zbl 0317.02039
[12] K. Klingenstein, Structures of bounded languages in certain families of languages, Information and Control (to appear).
[13] K. Klingenstein, ϱ-matrix languages, Theoret. Comput. Sci. (to appear).
[14] Ladner, R., On the structure of polynomial time reducibility, J. assoc. comput. Mach., 22, 155-171, (1975) · Zbl 0322.68028
[15] Ladner, R.; Lynch, N., Relativizations of questions about log space computability, Math. syst. theory, 10, 19-32, (1976) · Zbl 0341.68036
[16] Ladner, R.; Lynch, N.; Selman, A., A comparison of polynomial time reducibilities, Theoret. comput. sci., 1, 103-123, (1975) · Zbl 0321.68039
[17] Machtey, M., Augmented loop languages and classes of computable functions, J. comput. syst. sci., 6, 603-624, (1972) · Zbl 0312.68028
[18] Simon, I., On some subrecursive reducibilities, ()
[19] Simon, I.; Gill, J., Polynomial reducibilities and upwards diagonalizations, Proc. 9th ACM symp. theory of computing, 186-194, (1977)
[20] Stockmeyer, L., The polynomial-time hierarchy, Theoret. comput. sci., 3, 1-22, (1976) · Zbl 0353.02024
[21] H. Sudborough. The complexity of the membership problem for some extentions of context-free languages, Int. J. Comput. Math. (to appear). · Zbl 0398.68037
[22] Wrathall, C., Subrecursive predicates and automata, () · Zbl 0861.06006
[23] Wrathall, C., Complete sets and the polynomial-time hierarchy, Theoret. comput. sci., 3, 23-33, (1976) · Zbl 0366.02031
[24] Wrathall, C., Rudimentary predicates and relative computation, SIAM J. comput., 7, (1978), to appear · Zbl 0375.68030
[25] C. Wrathall, The linear and polynomial-time hierarchy (to appear).
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.