×
Ladner, Richard E.; Lynch, Nancy A.

Relativization of questions about log space computability. (English) Zbl 0341.68036

Math. Syst. Theory 10, 19-32 (1976).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0341.68036

Cited in 2 Reviews
Cited in 62 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
03D25 Recursively (computably) enumerable sets and degrees
03D10 Turing machines and related notions
Cite Review PDF
Full Text: DOI

References:

[1] T. Baker, J. Gill, andR. Solovay, Relativizations of the question. To appear inSIAM Journal on Computing. · Zbl 0323.68033
[2] S. A. Cook, Characterizations of pushdown machines in terms of time-bounded computers,Journal of the ACM,18 (1971) 4–18. · Zbl 0222.02035 · doi:10.1145/321623.321625
[3] S. A. Cook, The complexity of theorem proving procedures,Proc. Third Annual ACM Symposium on Theory of Computing, 1971 pp. 151–158. · Zbl 0253.68020
[4] S. A. Cook, An observation on time-storage trade off,Proc. of Fifth Annual ACM Symposium on Theory of Computing, 1973 pp. 29–33. · Zbl 0305.68066
[5] J. Hartmanis, On nondeterminacy of simple computing devices,Acta Informatica,1 (1972) 336–344. · Zbl 0229.68014 · doi:10.1007/BF00289513
[6] J. E. Hopcroft andJ. D. Ullman, Nonerasing stack automata,Journal of Computer and System Sciences,1 (1967) 166–186. · Zbl 0166.00506 · doi:10.1016/S0022-0000(67)80013-8
[7] J. E. Hopcroft andJ. D. Ullman,Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, Ma. 1969. · Zbl 0196.01701
[8] P. Hsia andR. Yeh, Finite automata with marks, inAutomata, Languages and Programming, M. Nivat, editor, American Elsevier, New York 1973.
[9] N. D. Jones, Space-bounded reducibility among combinatorial problems,Journal of Computer and System Sciences,11 (1975) 68–85. · Zbl 0317.02039 · doi:10.1016/S0022-0000(75)80050-X
[10] N. D. Jones andW. T. Laaser, Complete problems for deterministic polynomial time,Proc. of Sixth Annual ACM Symposium on Theory of Computing, pp. 40–46 1974. · Zbl 0376.68040
[11] R. M. Karp, Reducibility among combinatorial problems, inComplexity of Computer Computations, R. Miller and J. Thatcher, editors, Plenum Press, New York 1972.
[12] R. E. Ladner, On the structure of polynomial time reducibility,Journal of the ACM,22 (1975) 155–171. · Zbl 0322.68028 · doi:10.1145/321864.321877
[13] R. E. Ladner, The circuit value problem is log space complete for ,SIGACT News,7 (1975) 18–20. · doi:10.1145/990518.990519
[14] R. E. Ladner, N. A. Lynch, andA. L. Selman, A comparison of polynomial time reducibilities. To appear inTheoretical Computer Science. · Zbl 0321.68039
[15] N. A. Lynch, Log space recognition and translation of parenthesis languages, manuscript. · Zbl 0401.68051
[16] N. A. Lynch, Log space machines with multiple oracle tapes, manuscript. · Zbl 0368.68058
[17] A. R. Meyer, private communication.
[18] W. J. Savitch, Relationship between nondeterministic and deterministic tape complexities,Journal of Computer and System Sciences,4 (1970) 177–192. · Zbl 0188.33502 · doi:10.1016/S0022-0000(70)80006-X
[19] Simon, Istvan. Private communication (Ph.D. Thesis in preparation, Stanford).
[20] R. E. Stearns, J. Hartmanis, andP. M. Lewis II, Hierarchies of memory limited computations,IEEE Conf. Record on Switching Circuit Theory and Logical Design, (1965) 191–202 · Zbl 0229.02033
[21] L. Stockmeyer andA. R. Meyer, Word problems requiring exponential timeProc. of Fifth Annual ACM Symposium on Theory of Computing, (1973) pp. 1–9. · Zbl 0359.68050
[22] I. H. Sudborough, On tape-bounded complexity classes and multihead automata,Journal of Computer and System Sciences, Vol,10 (1975) 62–76. · Zbl 0299.68031 · doi:10.1016/S0022-0000(75)80014-6
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.