Deterministic CFL's are accepted simultaneously in polynomial time and log squared space

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Deterministic CFL's are accepted simultaneously in polynomial time and log squared space

Full text

Pdf (625 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eleventh annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 338 - 345

Year of Publication: 1979

Author

Stephen A. Cook

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 31, Citation Count: 9

Additional Information:

abstract 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/800135.804426 What is a DOI?

ABSTRACT

We propose to prove the theorem in the title. Let PLOSS be the class of sets recognizable on a deterministic Turing machine simultaneously in polynomial time and log squared space. Using the notation of Bruss and Meyer [1], PLOSS &equil; &ugr;k TISP(nk,k log2n).

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	Anni R. Bruss , Albert R. Meyer, On time-space classes and their relation to the theory of real addition, Proceedings of the tenth annual ACM symposium on Theory of computing, p.233-239, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804352]
	2	I. H. Sudborough, On the Tape Complexity of Deterministic Context-Free Languages, Journal of the ACM (JACM), v.25 n.3, p.405-414, July 1978 [doi>10.1145/322077.322083]
	3	Richard E. Ladner, The circuit value problem is log space complete for P, ACM SIGACT News, v.7 n.1, p.18-20, January 1975 [doi>10.1145/990518.990519]
	4	A.B. Borodin, "On relating time and space to size and depth". SIAM J. Comput., vol.6, No.4, (December 1977), pp.733-744.
	5	W.J. Savitch, "Relationships between nondeterministic and deterministic tape complexities". JCSS 4 (1970), pp.177-192.

CITED BY 9

	Martin Tompa, Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.333-338, April 28-30, 1980, Los Angeles, California, United States
	Patrick W. Dymond , Walter L. Ruzzo, Parallel RAMs with owned global memory and deterministic context-free language recognition, Journal of the ACM (JACM), v.47 n.1, p.16-45, Jan. 2000
	S. R. Buss, The Boolean formula value problem is in ALOGTIME, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.123-131, January 1987, New York, New York, United States
	A. Borodin , S. Cook, A time-space tradeoff for sorting on a general sequential model of computation, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.294-301, April 28-30, 1980, Los Angeles, California, United States
	Burkhard Monien , Ivan Hal Sudborough, Bandwidth constrained NP-Complete problems, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.207-217, May 11-13, 1981, Milwaukee, Wisconsin, United States
	Sergio De Agostino , Riccardo Silvestri, Bounded size dictionary compression: SC^k -completeness and NC algorithms, Information and Computation, v.180 n.2, p.101-112, 29 January 2003
	Dale Myers, The random access hierarchy, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.355-364, December 1983
	S. Skyum , L. G. Valiant, A complexity theory based on Boolean algebra, Journal of the ACM (JACM), v.32 n.2, p.484-502, April 1985
	Henk Alblas , Rieks op den Akker , Paul Oude Luttighuis , Klaas Sikkel, A bibliography on parallel parsing, ACM SIGPLAN Notices, v.29 n.1, p.54-65, Jan. 1994