×
Seiferas, Joel I.

Relating refined space complexity classes. (English) Zbl 0352.68063

J. Comput. Syst. Sci. 14, 100-129 (1977).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0352.68063

Cited in 26 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
\textit{J. I. Seiferas}, J. Comput. Syst. Sci. 14, 100--129 (1977; Zbl 0352.68063)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Beeri, C., Reductions in the number of heads for the nondeterminancy problem in multihead automata, ()
[2] Borodin, A., Computational complexity and the existence of complexity gaps, J. assoc. comput. Mach., 19, 158-174, (1972) · Zbl 0261.68024
[3] Constable, R.L., The operator gap, J. assoc. comput. Mach., 19, 175-183, (1972) · Zbl 0229.68016
[4] Feldman, E.D.; Owings, J.C., A class of universal linear bounded automata, Inf. sci. (NY), 6, 187-190, (1973) · Zbl 0268.94043
[5] Flajolet, P.; Steyaert, J.-M., Decision problems for multihead finite automata, (), 225-230
[6] Freedman, A.R.; Ladner, R.E., Space bounds for processing contentless inputs, J. comput. system sci., 11, 118-128, (1975) · Zbl 0307.68036
[7] Ginsburg, S.; Greibach, S.A.; Harrison, M.A., Stack automata and compiling, J. assoc. comput. math., 14, 172-201, (1967) · Zbl 0153.01101
[8] Grzegorczyk, A., Some classes of recursive functions, (), 1-45 · Zbl 0224.02029
[9] Hartmanis, J., On nondeterminancy in simple computing devices, Acta inf., 1, 336-344, (1972) · Zbl 0229.68014
[10] Hartmanis, J.; Berman, L., A note on tape bounds for sla language processing, (), 65-70
[11] Hopcroft, J.E.; Ullman, J.D., Nonerasing stack automata, J. comput. system sci., 1, 166-186, (1967) · Zbl 0166.00506
[12] Hopcroft, J.E.; Ullman, J.D., Some results on tape-bounded Turing machines, J. assoc. comput. Mach., 16, 168-177, (1969) · Zbl 0188.33501
[13] Hopcroft, J.E.; Ullman, J.D., ()
[14] Ibarra, O.H., Characterization of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata, J. comput. system sci., 5, 88-117, (1971) · Zbl 0255.68012
[15] Ibarra, O.H., A note concerning nondeterministic tape complexities, J. assoc. comput. Mach., 19, 608-612, (1972) · Zbl 0245.94044
[16] Ibarra, O.H., On two-way multihead automata, J. comput. system sci., 7, 28-36, (1973) · Zbl 0256.68028
[17] Ibarra, O.H., A hierarchy theorem for polynomial-space recognition, SIAM J. computing, 3, 184-187, (1974) · Zbl 0294.02013
[18] Ibarra, O.H.; Sahni, S.K., Hierarchies of Turing machines with restricted tape alphabet size, J. comput. system sci., 11, 56-67, (1975) · Zbl 0307.68037
[19] Ritchie, R.W., Classes of predictably computable functions, Trans. amer. math. soc., 106, 139-173, (1963) · Zbl 0107.01001
[20] Savitch, W.J., Relationships between nondeterministic and deterministic tape complexities, J. comput. system sci., 4, 177-192, (1970) · Zbl 0188.33502
[21] Seiferas, J.I., Nondeterministic time and space complexity classes, () · Zbl 0274.04004
[22] Seiferas, J.I., A note on notions of tape constructability, ()
[23] {\scJ. I. Seiferas}, Techniques for separating space complexity classes, J. Comput. System Sci., to appear. · Zbl 0352.68062
[24] Seiferas, J.I.; Fischer, M.J.; Meyer, A.R., Refinements of the nondeterministic time and space hierarchies, (), 130-137
[25] Stearns, R.E.; Hartmanis, J.; Lewis, P.M., Hierarchies of memory limited computations, (), 179-190 · Zbl 0229.02033
[26] {\scI. H. Sudborough}, Personal communication, October 1975.
[27] Sudborough, I.H., On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store, (), 141-148 · Zbl 0365.68077
[28] Young, P., Easy contructions in complexity theory: gap and speed-up theorems, Proc. amer. math. soc., 37, 555-563, (1973) · Zbl 0328.68044
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.