A New Normal-Form Theorem for Context-Free Phrase Structure Grammars

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A New Normal-Form Theorem for Context-Free Phrase Structure Grammars

Full text

Pdf (569 KB)

Source

Journal of the ACM (JACM) archive
Volume 12 , Issue 1 (January 1965) table of contents

Pages: 42 - 52

Year of Publication: 1965

ISSN:0004-5411

Author

Sheila A. Greibach

Harvard University, Cambridge, Massachusetts

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 46, Citation Count: 36

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/321250.321254 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	CHOSXY, N. Formal properties of grammars. In Hardboo qf fathe;naica{ PqcJmL ogy, voL II. Lute, R. D., Bush, R. R., and Galanter, E. (Eds.), Wiley New York, 1963.
	2	EVEY, J. The Theory and Applications of Pushdown Store Mtchines. Doct.. Thesis, Harvard U., Cambridge, Mass., 1963.
	3	Melvin E. Conway, Design of a separable transition-diagram compiler, Communications of the ACM, v.6 n.7, p.396-408, July 1963 [doi>10.1145/366663.366704]
	4	E. T. Irons, An error-correcting parse algorithm, Communications of the ACM, v.6 n.11, p.669-673, Nov. 1963 [doi>10.1145/368310.368385]
	5	KUNO, S, axu 0TTINOER, A. G. Multiple-path syntactic analyzer. In informaffon Processing 62, C. M. Popplewell (Ed.), North Holland, Amsterdam, 1962-1963.
	6	YNQv, V. A model and hypothesis for language structure. Proc. Miner. Ptil. Soc. i07, 5 (Oct. 1960).
	7	CHOMSKY, N, _NrD SCHUrZEXBERGER, M. P. The algebraic theory of context-free languages. In Computer Programming and Formal Sytems, Braffort, P., and Hirschberg, I9. (Eds.), North Holland, Amsterdam, 1963.
	8	BHILLEL, Y., PEaLES, M., YD SItxe, E. On formal properties of simple phrase structure grammars. Zeit. Phonet. Sprachwis. Komm,wnih. Forsch. 1, 2 (1961).
	9	Kuo, S. Automatic transformation of au admissible PSG into a standard form PSG. Unpublished paper.
	10	FENICHL, R. Private communication.
	11	RaBIN, M. O. anD SCOTT, D. Finite automata and their decision problems. IBM Y. ReS, Develop. 8 (1959), 114-125.
	12	HAYs, D. G. Grouping and dependercy theories. Paper P-l010, RAND Corp., SANta Moniea Calif,, 1960.
	13	GAIFMAN, M. Dependency systems and phrase structure systems. Paper P-2315, RAND Corp., Santa Monica, Calif., 1961.
	14	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]
	15	SPIELMAN, J Operator and precedence frammars. Unpublished paper.
	16	ZIELLER, C. A theorem of N. Chomsky and M. P. Schiitzenberger. Unpublished paper.
	17	GIEIAc S. Inverses of phrase strueture generators. Doct. Thesis, Harvard U. Cambridge, Mass., 1963.
	18	Seymour Ginsburg , H. Gordon Rice, Two Families of Languages Related to ALGOL, Journal of the ACM (JACM), v.9 n.3, p.350-371, July 1962 [doi>10.1145/321127.321132]
	19	COMSY, N. Context-free grammars and pushdown storage. RLE Quart. Prog. Rep. No. 65, M.t.T., Cambridge, Mass., Mar. 1962.
	20	McNAuGITON, It., NU YAMADA, H. Regular expressions and state graphs for auto mata, fief Trans. C-9, (1960), 39-47.

CITED BY 36

	Susumu Kuno , Anthony G. Oettinger, Computational linguistics in a Ph.D. computer science program, Communications of the ACM, v.11 n.12, p.831-836, Dec. 1968
	Susumu Kuno, The augmented predictive analyzer for context-free languages—its relative efficiency, Communications of the ACM, v.9 n.11, p.810-823, Nov. 1966
	Daniel J. Rosenkrantz, Matrix Equations and Normal Forms for Context-Free Grammars, Journal of the ACM (JACM), v.14 n.3, p.501-507, July 1967
	A. E. Roberts, Jr., The construction of recognizers, Proceedings of the 1966 21st national conference, p.383-389, January 1966
	William F. Atchison , Samuel D. Conte , John W. Hamblen , Thomas E. Hull , Thomas A. Keenan , William B. Kehl , Edward J. McCluskey , Silvio O. Navarro , Werner C. Rheinboldt , Earl J. Schweppe , William Viavant , David M. Young, Jr., Curriculum 68: Recommendations for academic programs in computer science: a report of the ACM curriculum committee on computer science, Communications of the ACM, v.11 n.3, p.151-197, March 1968
	Werner Kuich, Forty years of formal power series in automata theory, A half-century of automata theory: celebration and inspiration, World Scientific Publishing Co., Inc., River Edge, NJ, 2001
	Stephen N. Cole, Deterministic Pushdown Store Machines and Real-Time Computation, Journal of the ACM (JACM), v.18 n.2, p.306-328, April 1971
	Alfred V. Aho, Indexed Grammars—An Extension of Context-Free Grammars, Journal of the ACM (JACM), v.15 n.4, p.647-671, Oct. 1968
	H. A. Maurer , A. Salomaa , D. Wood, A Supernormal-Form Theorem for Context-Free Grammars, Journal of the ACM (JACM), v.30 n.1, p.95-102, Jan. 1983
	Robert C. Moore, Removing left recursion from context-free grammars, Proceedings of the first conference on North American chapter of the Association for Computational Linguistics, p.249-255, April 29-May 04, 2000, Seattle, Washington
	Seymour Ginsburg , Michael A. Harrison, One-way nondeterministic real-time list-storage languages, Journal of the ACM (JACM), v.15 n.3, p.428-446, July 1968
	Thomas N. Hibbard, Context-Limited Grammars, Journal of the ACM (JACM), v.21 n.3, p.446-453, July 1974
	Y. R. Wang, On the formulation of normal pushdown acceptors, Proceedings of the 1968 23rd ACM national conference, p.605-612, August 27-29, 1968
	Susumu Kuno, The predictive analyzer and a path elimination technique, Communications of the ACM, v.8 n.7, p.453-462, July 1965
	Clarence A. Ellis, Probabilistic Tree Automata, Proceedings of the second annual ACM symposium on Theory of computing, p.198-205, May 04-06, 1970, Northampton, Massachusetts, United States
	Bruce W. Arden, The role of programming in a Ph.D. computer science program, Communications of the ACM, v.12 n.1, p.31-37, Jan. 1969
	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
	Clarence A. Ellis, The Halting Problem for Probabilistic Context-Free Generators, Journal of the ACM (JACM), v.19 n.3, p.396-399, July 1972
	Sheila A. Greibach, Jump PDA's, deterministic context-free languages principal AFDLs and polynomial time recognition—(Extended Abstract), Proceedings of the fifth annual ACM symposium on Theory of computing, p.20-28, April 30-May 02, 1973, Austin, Texas, United States
	James N. Gray , Michael A. Harrison, Canonical Precedence Schemes, Journal of the ACM (JACM), v.20 n.2, p.214-234, April 1973
	D. J. Rosenkrantz , R. E. Stearns, Properties of deterministic top down grammars, Proceedings of the first annual ACM symposium on Theory of computing, p.165-180, May 05-07, 1969, Marina del Rey, California, United States
	Sheila A. Greibach, An Infinite Hierarchy of Context-Free Languages, Journal of the ACM (JACM), v.16 n.1, p.91-106, Jan. 1969
	Seymour Ginsburg , Sheila Greibach, Multitape AFA, Journal of the ACM (JACM), v.19 n.2, p.193-221, April 1972
	G. Salton, Information science in a Ph.D. computer science program, Communications of the ACM, v.12 n.2, p.111-117, Feb. 1969
	Bruce S. N. Cheung, Ambiguity in context-free grammars, Proceedings of the 1995 ACM symposium on Applied computing, p.272-276, February 26-28, 1995, Nashville, Tennessee, United States
	Stephen N. Cole, Pushdown store machines and real-time computation, Proceedings of the first annual ACM symposium on Theory of computing, p.233-245, May 05-07, 1969, Marina del Rey, California, United States
	David Bruce Lomet, A Formalization of Transition Diagram Systems, Journal of the ACM (JACM), v.20 n.2, p.235-257, April 1973
	S. A. Greibach , E. P. Friedman, Superdeterministic PDAs: A Subcase with a Decidable Inclusion problem, Journal of the ACM (JACM), v.27 n.4, p.675-700, Oct. 1980
	Jürgen Albert , Dora Giammarresi , Derick Wood, Normal form algorithms for extended context-free grammars, Theoretical Computer Science, v.267 n.1-2, p.35-47, 09/26/2001
	H. Gaifman , E. Shamir, Roots of the hardest context free language and other constructs, ACM SIGACT News, v.12 n.3, Fall 1980
	Yves Schabes , Richard C. Waters, Tree insertion grammar: a cubic-time, parsable formalism that lexicalizes context-free grammar without changing the trees produced, Fuzzy Sets and Systems, v.76 n.3, p.309-317, Dec. 22, 1995
	S. A. Greibach, Comments on the roots of theorems and languages both easy and hard, ACM SIGACT News, v.13 n.1, p.26-29, Winter 1981
	T. Tanaka, Parsing Electronic Circuits in a Logic Grammar, IEEE Transactions on Knowledge and Data Engineering, v.5 n.2, p.225-239, April 1993
	Joyce Friedman , Dawei Dai , Weiguo Wang, The weak generative capacity of parenthesis-free categorial grammars, Proceedings of the 11th coference on Computational linguistics, August 25-29, 1986, Bonn, Germany
	Bernd Kühl , Axel-Toblas Schreiner, An object-oriented LL(1) parser generator, ACM SIGPLAN Notices, v.35 n.12, p.33-40, Dec. 2000
	Ryo Yoshinaka, An elementary proof of a generalization of double Greibach normal form, Information Processing Letters, v.109 n.10, p.490-492, April, 2009