×
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
Cite Review PDF
Full Text: DOI

References:

[1] Beeri, C., Reductions in the number of heads for the nondeterminacy problem in multihead automata, (Technical Report (1973), Institute of Mathematics, The Hebrew University of Jerusalem: Institute of Mathematics, The Hebrew University of Jerusalem Israel)
[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, (IEEE Conference Record of 1969 Tenth Annual Symposium on Switching and Automata Theory. IEEE Conference Record of 1969 Tenth Annual Symposium on Switching and Automata Theory, Waterloo, Ontario (1969)), 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, (Proceedings of Symposium and Summer School on Mathematical Foundations of Computer Science. Proceedings of Symposium and Summer School on Mathematical Foundations of Computer Science, High Tatras, Czechoslovakia (1973)), 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, (Rozprawy Matematyczne IV (1953), Instytut Matematyczny Polskiej Akademie Nauk: Instytut Matematyczny Polskiej Akademie Nauk Warsaw), 1-45 · Zbl 0224.02029
[12] Hartmanis, J.; Berman, L., A note on tape bounds for sla language processing, (Proceedings of the 16th Annual Symposium on Foundations of Computer Science. Proceedings of the 16th Annual Symposium on Foundations of Computer Science, Berkeley, California (1975)), 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., (Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, Mass.) · Zbl 0196.01701
[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, (Kohavi, Z.; Paz, A., Theory of Machines and Computations (1971), Academic Press: Academic Press New York), 19-42 · Zbl 0266.94019
[20] Ritchie, R. W., Classes of predictably computable functions, Trans. Amer. Math. Soc., 106, 139-173 (1963) · Zbl 0107.01001
[21] Rogers, H., (Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York) · Zbl 0183.01401
[22] Ruby, S.; Fischer, P. C., Translational methods and computational complexity, (IEEE Conference Record on Switching Circuit Theory and Logical Design. IEEE Conference Record on Switching Circuit Theory and Logical Design, Ann Arbor, Michigan (1965)), 173-178 · Zbl 0257.68037
[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, (Project MAC Technical Report, 137 (September 1974), Massachusetts Institute of Technology: Massachusetts Institute of Technology Cambridge, Mass.) · Zbl 0274.04004
[25] Seiferas, J. I., A note on notions of tape constructability, (Report No. 187 (May 1976), Computer Science Department, The Pennsylvania State University: Computer Science Department, The Pennsylvania State University University Park, Pennsylvania)
[26] J. I. SeiferasJ. Comput. System Sci.; J. I. SeiferasJ. Comput. System Sci. · Zbl 0352.68063
[27] Seiferas, J. I.; Fischer, M. J.; Meyer, A. R., Refinements of the nondeterministic time and space hierarchies, (Proceedings of the 14th Annual Symposium on Switching and Automata Theory. Proceedings of the 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa (1973)), 130-137
[28] Seiferas, J. I.; Fischer, M. J.; Meyer, A. R., Separating nondeterministic time complexity classes, (Report No. 205 (August 1976), Computer Science Department, The Pennsylvania State University: Computer Science Department, The Pennsylvania State University University Park, Pennsylvania) · Zbl 0366.68038
[29] Stearns, R. E.; Hartmanis, J.; Lewis, P. M., Hierarchies of memory limited computations, (IEEE Conference Record on Switching Circuit Theory and Logical Design. IEEE Conference Record on Switching Circuit Theory and Logical Design, Ann Arbor, Michigan (1965)), 179-190 · Zbl 0229.02033
[30] Trahtenbrot, B. A., On autoreducibility, Soviet Math. Dokl., 11, 814-817 (1970) · Zbl 0216.28904
[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. 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.