×
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 27 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 nondeterminancy 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] 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, (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
[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, (Rozprawy Matematyczme IV (1953), Instytut Matematyczny Polskiej Akademie Nauk: Instytut Matematyczny Polskiej Akademie Nauk Warsaw), 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, (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
[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., (Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, Mass.) · Zbl 0196.01701
[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, (Project MAC Technical Report, 137 (September 1974), Massachusetts Institute of Technology: Massachusetts Institute of Technology Cambridge, Mass.) · Zbl 0274.04004
[22] 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)
[23] J. I. SeiferasJ. Comput. System Sci.; J. I. SeiferasJ. Comput. System Sci. · Zbl 0352.68062
[24] Seiferas, J. I.; Fischer, M. J.; Meyer, A. R., Refinements of the nondeterministic time and space hierarchies, (Proceedings of 14th Annual Symposium on Switching and Automata Theory. Proceedings of 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa (1973)), 130-137
[25] 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
[26] I. H. Sudborough; I. H. Sudborough
[27] Sudborough, I. H., On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store, (Proceedings of the Eighth Annual ACM Symposium on Theory of Computing. Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, Hershey, Pennsylvania (1976)), 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. 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.