On the Decidability of Grammar Problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the Decidability of Grammar Problems

Full text

Pdf (975 KB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 2 (April 1982) table of contents

Pages: 429 - 447

Year of Publication: 1982

ISSN:0004-5411

Author

H. B. Hunt, III

Department of Computer Science, State University of New York at Albany, 1400 Washington Avenue, Albany, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 56, Citation Count: 3

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/322307.322317 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 , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
	2	CULIK, K. II, m,lo ConE~, R LR-regular grammars--An extension of LR(k) grammars. J. Comput. Syst. ScL 7 (1973), 66-96.
	3	GELL~R, M M., AlCD HAg~soi% M.A. Characterizauons of LR(0) languages. Conf. Rec 14th Ann. Symp. on Switching and Automata Theory, Ames, Iowa, Oct. 1973, pp. 103-108
	4	James N. Gray , Michael A. Harrison, On the Covering and Reduction Problems for Context-Free Grammars, Journal of the ACM (JACM), v.19 n.4, p.675-698, Oct. 1972 [doi>10.1145/321724.321732]
	5	Ivan M. Havel , Michael A. Harrison, On the Parsing of Deterministic Languages, Journal of the ACM (JACM), v.21 n.4, p.525-548, Oct. 1974 [doi>10.1145/321850.321851]
	6	HARTMANIS, J. Context-free languages and Turmg machine computations. In Proceedings of a Symposium on Applied Mathematics, Mathematical Aspects of Computer Science 19, American Mathemattcal Society, Prowdence, R.I., 1967, pp. 42-51.
	7	J. Hartmanis , J. E. Hopcroft, An Overview of the Theory of Computational Complexity, Journal of the ACM (JACM), v.18 n.3, p.444-475, July 1971 [doi>10.1145/321650.321661]
	8	HAVEL, I.M., AND HARRISON, M.A.Real-time strict determimstie languages, SlAM J. Comput. 1 (1972), 333-349
	9	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	10	HUNT, H.B. III.Partial sot recognition problems, texmmating Turing machine computations, and the complexity of correspondence problems, grammars, and program schemes. Unpubhshed manuscript, 1980.
	11	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]
	12	HUNT, H,B. III, AND SZYMANSKI, T.G.Complexity metatheorems for context-free grammar problems. ~ Comput. Syst. Sci. 13 (1976), 318-334.
	13	Harry B. Hunt, III , Thomas G. Szymanski, Lower Bounds and Reductions Between Grammar Problems, Journal of the ACM (JACM), v.25 n.1, p.32-51, Jan. 1978 [doi>10.1145/322047.322051]
	14	JARZABEK, S., AND KILAWCZYK, T.LL-regular grammars Inf Proc. Lett. 4 (1975), 31-37.
	15	Philip M. Lewis, 2nd , Daniel J. Rosenkrantz , Richard E. Stearns, Compiler Design Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1976
	16	M. Dennis Mickunas, On the Complete Covering Problem for LR(k)Grammars, Journal of the ACM (JACM), v.23 n.1, p.17-30, Jan. 1976 [doi>10.1145/321921.321924]
	17	OGDEN W.F. Unpublished memorandum, December 1971.
	18	PAULL, M.C., AND UNGER, S.H. Structural equivalence of context=free grammars. ~ Comput. Syst. Sci. 2 (1968), 427--463
	19	REYNOLDS, J.C, AND HASK~LL, R. Grammatical coverings. Unpublished manuscript, 1970.
	20	Thomas Gregory Szymanski, Generalized bottom-up parsing., 1973
	21	SZYMANSra, T.G., AND Wmu~s, LH.Noncanonical extensions of bottom=up parsing techniques. SIAM J. Comput. 5 (1976), 231-250.
	22	THATCHER, J W.Tree automata: An mformal survey. La Currents in the Theory of Computing, A V. Allo, Ed., Prenuce-Hall, Englewood Cliffs, N.J., 1973, pp. 143--172.
	23	VALIANT, L.G.A note on the succinctness of descnptlons of determimsUc languages. Inf. Control 32 (1976), 139-145.

CITED BY 3

	H. B. Hunt, III, Terminating Turing Machine Computations and the Complexity and/or decidability of Correspondence Problems, Grammars, and Program Schemes, Journal of the ACM (JACM), v.31 n.2, p.299-318, April 1984
	D. J. Rosenkrantz , H. B. Hunt, Efficient algorithms for automatic construction and compactification of parsing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.543-566, Oct. 1987
	Mark-Jan Nederhof , Giorgio Satta, The language intersection problem for non-recursive context-free grammars, Information and Computation, v.192 n.2, p.172-184, August 1, 2004