On the Tape Complexity of Deterministic Context-Free Languages

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the Tape Complexity of Deterministic Context-Free Languages

Full text

Pdf (708 KB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 3 (July 1978) table of contents

Pages: 405 - 414

Year of Publication: 1978

ISSN:0004-5411

Author

I. H. Sudborough

Computer Science Department, The Technological Institute, Northwestern University, Evanston, IL

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 67, Citation Count: 14

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/322077.322083 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	A8o, A V, HOPCROFT, J E, AND ULLMAN, J D Time and tape complexity of pushdown automaton languages Inform and Control 13, 3 (1968), 186-206
	2	Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
	3	Boor., R V Translational lemmas, polynomial tune, and (log ny-space Theoret Comptr Scl I (1976), 215-226
	4	Stephen A. Cook, Path systems and language recognition, Proceedings of the second annual ACM symposium on Theory of computing, p.70-72, May 04-06, 1970, Northampton, Massachusetts, United States [doi>10.1145/800161.805151]
	5	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	6	COOK, S A Linear time stmulat~on of determmlsac two-way pushdown automata Informauon Processing 71, Vol !, North-Holland Pub Co, Amsterdam, pp 75-80
	7	Stephen A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal of the ACM (JACM), v.18 n.1, p.4-18, Jan. 1971 [doi>10.1145/321623.321625]
	8	CooK, S A An observaaon on Ume-storage trade off J Comptr Syst Sct 9 (1974), 308-316
	9	Michael J. Fischer, Some properties of precedence languages, Proceedings of the first annual ACM symposium on Theory of computing, p.181-190, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805432]
	10	Robert W. Floyd, Syntactic Analysis and Operator Precedence, Journal of the ACM (JACM), v.10 n.3, p.316-333, July 1963 [doi>10.1145/321172.321179]
	11	GALIL, Z Two-way deterministic pushdown automata and some open problems m the theory ofcomputauon Proc Fifteenth Annual IEEE Symp Switching and Automata Theory, 1974, pp 170-177
	12	GI~SBUgG, S, AND GREIBAeH, S A DetermmlsUc context-free languages Inform and Control 9, 6 (1966), 620-648
	13	GRAY, J N, HARRISON, M A, AND IBARRA, O H. Two-way pushdown automata Inform and Control 11, 1 (1967), 30--70
	14	GREmACH, S A The hardest context-free language SIAM J Comptng 2, 4 (1973), 304-310
	15	HARRISON, M A, ANO IBARRA, O H MultRape and muluhead pushdown automata Inform and Control 13, 5 (1968), 433-470
	16	HARTMANIS, J On nondetermmacy in sunple computing dewces Acta informanca 1 (1972), 336-344
	17	IBARRA, O H On two-way muluhead automata J Comptr Syst Sct 7 (1973), 28-36
	18	JONES, N D. Space-bounded reduobdlty among combinatorial problems J Comptr Syst Scl 11 (1975), 68-85.
	19	JONES, N.D, ANt> LAASER, W.T Complete problems for determimstlc polynomial time Theoret Comptr Scl. 3 (1977), 105-117.
	20	KAgP, R M Reductbdity among combinatorial problems In Complexay of Computer Computattons, R.E Mdler and J N Thatcher, Eds, Plenum Press, N Y, 1972, pp. 85-104.
	21	KNtJTH, D E On the translation of languages from left to right Inform and Control 8, 6 (1965), 607-639
	22	KORENJAK, A J, AND HOPCROFT, J E Simple determmlstm languages Conf Rec Seventh Annual IEEE Symp Switching and Automata Theory, 1966, pp 36-46
	23	LEwm, P M, STEARNS, R E, AND HARTMANtS, j Memory bounds for the recogmtion of context-free and context-sensmve languages Proc Sixth Annual IEEE Symp Switching Circuit Theory and Logical Design, 1965, pp 191-212
	24	MEYER, A R, AND STOCKME,,'ER, L J Word problems requmng exponentml rime Proc Fifth Annual ACM Syrup Theory of Comptng, 1973, pp I-9
	25	SAVITCH, W J Relationships between nondetermmtstic and deterministic tape complex~tms J Comptr and Syst Sct 4 (1970), 177-192
	26	StJDBOgOtJGH, 1 H On tape-bounded complexity classes and multlhead fimte automata J Comptr and Syst Sct 10, I (1975), 62-76
	27	I. H. Sudborough, 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, p.141-148, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803642]
	28	Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL, and its formal definition: Part II, Communications of the ACM, v.9 n.2, p.89-99, Feb. 1966 [doi>10.1145/365170.365202]

CITED BY 14

	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
	H. Venkateswaran, Properties that characterize LOGCFL, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.141-150, January 1987, New York, New York, United States
	Markus Holzer , Pierre McKenzie, Alternating and empty alternating auxiliary stack automata, Theoretical Computer Science, v.299 n.1-3, p.307-326, 18 April 2003
	Walter L. Ruzzo, Tree-size bounded alternation(Extended Abstract), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.352-359, April 30-May 02, 1979, Atlanta, Georgia, United States
	Georg Gottlob , Nicola Leone , Francesco Scarcello, The complexity of acyclic conjunctive queries, Journal of the ACM (JACM), v.48 n.3, p.431-498, May 2001
	M. Beaudry , M. Holzer , G. Niemann , F. Otto, McNaughton families of languages, Theoretical Computer Science, v.290 n.3, p.1581-1628, 3 January 2003
	B. Litow , I. H. Sudborough, On non-erasing oracle tapes in space bounded reducibility, ACM SIGACT News, v.10 n.2, Summer 1978
	Stephen A. Cook, Deterministic CFL's are accepted simultaneously in polynomial time and log squared space, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.338-345, April 30-May 02, 1979, Atlanta, Georgia, United States
	N. Markey , Ph. Schnoebelen, A PTIME-complete matching problem for SLP-compressed words, Information Processing Letters, v.90 n.1, p.3-6, 15 April 2004
	Georg Gottlob , Christoph Koch , Reinhard Pichler , Luc Segoufin, The complexity of XPath query evaluation and XML typing, Journal of the ACM (JACM), v.52 n.2, p.284-335, March 2005
	Bodo Manthey , Rüdiger Reischuk, The intractability of computing the Hamming distance, Theoretical Computer Science, v.337 n.1-3, p.331-346, 9 June 2005
	Luc Segoufin, Typing and querying XML documents: some complexity bounds, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.167-178, June 09-11, 2003, San Diego, California
	Lane A. Hemaspaandra, SIGACT news complexity theory column 35, ACM SIGACT News, v.33 n.1, March 2002
	Joost Engelfriet, The complexity of the circularity problem for attribute grammars: a note on a counterexample for a simpler construction, ACM SIGACT News, v.20 n.3, p.57-59, July 1989