×
Seiferas, Joel I.

Techniques for separating space complexity classes. (English) Zbl 0352.68062

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

Cited in 20 Documents

MSC:

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

References:

[1] Beeri, C., Reductions in the number of heads for the nondeterminacy problem in multihead automata, ()
[2] Book, R.V., On languages accepted in polynomial time, SIAM J. computing, 1, 281-287, (1972) · Zbl 0251.68042
[3] Book, R.V.; Greibach, S.A.; Ibarra, O.H.; Wegbreit, B., Tape-bounded Turing acceptors and principal afls, J. comput. system sci., 4, 622-625, (1970) · Zbl 0206.28703
[4] Borodin, A., Computational complexity and the existence of complexity gaps, J. assoc. comput. Mach., 19, 158-174, (1972) · Zbl 0261.68024
[5] Borodin, A.; Constable, R.L.; Hopcroft, J.E., Dense and non-dense families of complexity classes, (), 7-19
[6] Constable, R.L., The operator gap, J. assoc. comput. Mach., 19, 175-183, (1972) · Zbl 0229.68016
[7] Cook, S.A., A hierarchy for nondeterministic time complexity, J. comput. system sci., 7, 343-353, (1973) · Zbl 0278.68042
[8] Feldman, E.D.; Owings, J.C., A class of universal linear bounded automata, Inf. sci. (NY), 6, 187-190, (1973) · Zbl 0268.94043
[9] Flajolet, P.; Steyaert, J.-M., Decision problems for multihead finite automata, (), 225-230
[10] Freedman, A.R.; Ladner, R.E., Space bounds for processing contentless inputs, J. comput. system sci., 11, 118-128, (1975) · Zbl 0307.68036
[11] Grzegorczyk, A., Some classes of recursive functions, (), 1-45 · Zbl 0224.02029
[12] Hartmanis, J.; Berman, L., A note on tape bounds for sla language processing, (), 65-70
[13] Hopcroft, J.E.; Ullman, J.D., Some results on tape-bounded Turing machines, J. assoc. comput. Mach., 16, 168-177, (1969) · Zbl 0188.33501
[14] Hopcroft, J.E.; Ullman, J.D., ()
[15] Ibarba, 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] Meyer, A.R.; McCreight, E.M., Computationally complex and pseudo-random zero-one valued functions, (), 19-42
[20] Ritchie, R.W., Classes of predictably computable functions, Trans. amer. math. soc., 106, 139-173, (1963) · Zbl 0107.01001
[21] Rogers, H., ()
[22] Ruby, S.; Fischer, P.C., Translational methods and computational complexity, (), 173-178
[23] Savitch, W.J., Relationships between nondeterministic and deterministic tape complexities, J. comput. system sci., 4, 177-192, (1970) · Zbl 0188.33502
[24] Seiferas, J.I., Nondeterministic time and space complexity classes, () · Zbl 0274.04004
[25] Seiferas, J.I., A note on notions of tape constructability, ()
[26] {\scJ. I. Seiferas}, Relating refined space complexity classes, J. Comput. System Sci., to appear. · Zbl 0352.68063
[27] Seiferas, J.I.; Fischer, M.J.; Meyer, A.R., Refinements of the nondeterministic time and space hierarchies, (), 130-137
[28] Seiferas, J.I.; Fischer, M.J.; Meyer, A.R., Separating nondeterministic time complexity classes, () · Zbl 0366.68038
[29] Stearns, R.E.; Hartmanis, J.; Lewis, P.M., Hierarchies of memory limited computations, (), 179-190 · Zbl 0229.02033
[30] Trahtenbrot, B.A., On autoreducibility, Soviet math. dokl., 11, 814-817, (1970)
[31] Young, P., Easy constructions 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.