Lower Bounds and Reductions Between Grammar Problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower Bounds and Reductions Between Grammar Problems

Full text

Pdf (1.21 MB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 1 (January 1978) table of contents

Pages: 32 - 51

Year of Publication: 1978

ISSN:0004-5411

Authors

Harry B. Hunt, III	Harvard University, Cambridge, Massachusetts and Department of Electrical Engineering and Computer Science, Columbia University, New York, NY
Thomas G. Szymanski	Department of Electrical Engineering and Computer Science, Princeton University, Princeton, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/322047.322051 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
	3	BROSGOL, B M Deterministic translation grammars Proc 8th Annual Princeton Conf on Inform Scl and Syst, March 1974, pp 300-306
	4	GELL~.R, M M , AND HARRISON, M A On LR(k) grammars and languages Manuscript, Comptr Scl Dlv , U of California, Berkeley, 1976
	5	Michael Hammer, A new grammatical transformation into LL(k) form (Extended Abstract), Proceedings of the sixth annual ACM symposium on Theory of computing, p.266-275, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803904]
	6	H. B. Hunt, III , T. G. Szymanski, Dichotomization, reachability, and the forbidden subgraph problem(Extended Abstract), Proceedings of the eighth annual ACM symposium on Theory of computing, p.126-134, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803640]
	7	HUNT, H.B III, SZYMANSKI, T G, AND ULLMAN, J.D Operations on sparse relations with apphcatlons to grammar problems Conf Rec IEEE 15th Annual Symp on Switching and Automata Theory, Oct 1974, pp 127-132
	8	Harry B. Hunt, III , Thomas G. Szymanski , Jeffrey D. Ullman, On the complexity of LR(k) testing, Communications of the ACM, v.18 n.12, p.707-716, Dec. 1975 [doi>10.1145/361227.361232]
	9	H. B. Hunt, III , J. D. Ullman , T. G. Szymanski, Operations on sparse relations, Communications of the ACM, v.20 n.3, p.171-176, March 1977 [doi>10.1145/359436.359446]
	10	KNUTH, D E On the translation of languages from left to right Inform and Control 8 (1965), 607- 639.
	11	JOHNSON, D B , AND SETm, R Efficient construction of LL(1) parsers Tech Rep #164, Comptr Scl Dept, Pennsylvania State U , University Park, Pa, March 1975
	12	P. M. Lewis, II , R. E. Stearns, Syntax-Directed Transduction, Journal of the ACM (JACM), v.15 n.3, p.465-488, July 1968 [doi>10.1145/321466.321477]
	13	ROSENKRANTZ, D J , ANt) LEWIS, P M II Deterministic left corner parsing Conf Rec IEEE 11 th Annual Symp on Switching and Automata Theory Oct 1970, pp 139-152
	14	ROSENKRANTZ, D.J , ANO STEARNS, R E. Properties of deterministic top-down grammars. Inform. and Control 17 (Oct 1970), 226-256
	15	SOISALON-SoININEr, E, ANO UKKO~EN, E A characterization of LL(k) languages. Third Int. Colloq on Automata, Languages and Programming, Edinburgh, Scotland, july 1976, pp 20-30
	16	SZVMANSKI, T G Concerning bounded-right-context grammars Theoret Comptr. Scz. 3, 3 (Dec 1976), 273-282.