A Note Concerning Nondeterministic Tape Complexities

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Note Concerning Nondeterministic Tape Complexities

Full text

Pdf (360 KB)

Source

Journal of the ACM (JACM) archive
Volume 19 , Issue 4 (October 1972) table of contents

Pages: 608 - 612

Year of Publication: 1972

ISSN:0004-5411

Author

Oscar H. Ibarra

University of Minnesota, Department of Computer Science, Institute of Technology, Minneapolis, MN

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 31, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321724.321727 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BooK, R. V., AND WEGBREITT, B. A note on AFLs and bounded erasing. Information and Control 19 (1971), 18-29.
	2	Seymour Ginsburg , Sheila A. Greibach , Michael A. Harrison, Stack automata and compiling, Journal of the ACM (JACM), v.14 n.1, p.172-201, Jan. 1967 [doi>10.1145/321371.321385]
	3	HARTMANIS, J., LEWIS, P. M. I I , AND STEARNS, R. E. Hierarchies of memory limited computations. IEEE Conf. Rec. on Switching Circuit Theory and Logical Design, Ann Arbor, Mich., 1965, pp. 179-190.
	4	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	5	HOPCROFT, J. E., AND ULLMAN, J .D . Nonerasing stack automata. J. Computer Syst. Sci. 1 (1967), 166-186.
	6	J. E. Hopcroft , J. D. Ullman, Some Results on Tape-Bounded Turing Machines, Journal of the ACM (JACM), v.16 n.1, p.168-177, Jan. 1969 [doi>10.1145/321495.321508]
	7	IBARRA, O. H. Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata. J. Computer Syst. Sci. 5 (1971), 88-117.
	8	RUBY, S., AND FISCHER, P. C. Translational methods and computational complexity. IEEE Conf. Rec. on Switching Circuit Theory and Logical Design, Ann Arbor, Mich., 1965, pp. 173-178.
	9	SAVITCn, W. J. Relationships between nondeteiministic and deterministic tape complexities. J. Computer Syst. Sci. 4 (1970), 177-192.

CITED BY 11

	J. Hartmanis , V. Sewelson , N. Immerman, Sparse sets in NP-P: Exptime versus nexptime, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.382-391, December 1983
	Joel I. Seiferas , Michael J. Fischer , Albert R. Meyer, Separating Nondeterministic Time Complexity Classes, Journal of the ACM (JACM), v.25 n.1, p.146-167, Jan. 1978
	Dale Myers, The random access hierarchy, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.355-364, December 1983
	L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States
	Tat-hung Chan, Reversal complexity of counter machines, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.146-157, May 11-13, 1981, Milwaukee, Wisconsin, United States
	I. H. Sudborough, Separating tape bounded auxiliary pushdown automata classes, Proceedings of the ninth annual ACM symposium on Theory of computing, p.208-217, May 04-04, 1977, Boulder, Colorado, United States
	Stephen A. Cook, A hierarchy for nondeterministic time complexity, Proceedings of the fourth annual ACM symposium on Theory of computing, p.187-192, May 01-03, 1972, Denver, Colorado, United States
	Viliam Geffert, Space hierarchy theorem revised, Theoretical Computer Science, v.295 n.1-3, p.171-187, 24 February 2003
	Oscar H. Ibarra, On the computational complexity of membrane systems, Theoretical Computer Science, v.320 n.1, p.89-109, 12 June 2004
	Jik H. Chang , Oscar H. Ibarra , Anastasios Vergis, On the power of one-way communication, Journal of the ACM (JACM), v.35 n.3, p.697-726, July 1988
	Chuzo Iwamoto , Harumasa Yoneda , Kenichi Morita , Katsunobu Imai, A Recursive Padding Technique on Nondeterministic Cellular Automata, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.9, p.2335-2340, September 2008