×
Book, Ronald V.; Wrathall, Celia

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

Theor. Comput. Sci. 7, 185-195 (1978).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0385.68061

Cited in 7 Documents

MSC:

68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
\textit{R. V. Book} and \textit{C. Wrathall}, Theor. Comput. Sci. 7, 185--195 (1978; Zbl 0385.68061)
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
[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, (Studies in Abstract Families of Languages (1969), Amer. Math. Soc), 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
[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, (Ph.D. Dissertation (1977), Stanford University: Stanford University CA)
[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
[22] Wrathall, C., Subrecursive Predicates and Automata, (Ph.D. dissertation (1975), Harvard University) · 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
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.