Indexed Grammars—An Extension of Context-Free Grammars

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Indexed Grammars—An Extension of Context-Free Grammars

Full text

Pdf (1.60 MB)

Source

Journal of the ACM (JACM) archive
Volume 15 , Issue 4 (October 1968) table of contents

Pages: 647 - 671

Year of Publication: 1968

ISSN:0004-5411

Author

Alfred V. Aho

Bell Telephone Laboratories, Inc., Murray Hill, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 22, Downloads (12 Months): 126, Citation Count: 53

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

ABSTRACT

A new type of grammar for generating formal languages, called an indexed grammar, is presented. An indexed grammar is an extension of a context-free grammar, and the class of languages generated by indexed grammars has closure properties and decidability results similar to those for context-free languages. The class of languages generated by indexed grammars properly includes all context-free languages and is a proper subset of the class of context-sensitive languages. Several subclasses of indexed grammars generate interesting classes of languages.

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	AHO, A.V. Nested stack automata. (Submitted to a technical journal.)
	2	BAR-HLEL, Y., PIiRLES, M., AND SHAMIR, E. On formal properties of simple phrase structure grammars. Z. Phonetik, Sprachwiss. Kommunikatiotsforsch. 14 (1961), 143-172; in Bar-Hillel, Y,, Language and Information, Addisol-Wesley, Reading, Mass., 1965, pp. 116-150.
	3	CHOMKY, N. Formal properties of grammars. In Lace, R., Bush, R., and Galauter, E. (Eds.), Handbook of Mathematical Psychology, Vol. II, Wiley, New York, 1963.
	4	DAvis, M. Computability and Unsolvability. McGraw-Hill, New York, 1958.
	5	Robert W. Floyd, On the nonexistence of a phrase structure grammar for ALGOL 60, Communications of the ACM, v.5 n.9, p.483-484, Sept. 1962 [doi>10.1145/368834.368898]
	6	Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, Inc., New York, NY, 1966
	7	GINSBURG, S., AND GIEIBACII, S.A. Abstract families of languages. IEEE Conference Record of Eighth Annual Symposium on Switching and Automata Theory, IEEE pub. no. 16-C-56, Oct. 1967, pp. 128-139.
	8	Seymour Ginsburg , Sheila A. Greibach , Michael A. Harrison, Stack automata and compiling, Journal of the ACM (JACM), v.14 n.1, p.172-201, Jan. 1967 [doi>10.1145/321371.321385]
	9	Seymour Ginsburg , Sheila A. Greibach , Michael A. Harrison, One-way stack automata, Journal of the ACM (JACM), v.14 n.2, p.389-418, April 1967 [doi>10.1145/321386.321403]
	10	Sheila A. Greibach, A New Normal-Form Theorem for Context-Free Phrase Structure Grammars, Journal of the ACM (JACM), v.12 n.1, p.42-52, Jan. 1965 [doi>10.1145/321250.321254]
	11	GRIBACH, S. A. A note on undecidable properties of formal languages. Tech. Rep. TM-738/038/00, System Development Corp., Santa Monica, Calif., Aug. i967.
	12	GREIRACH, S. A., AND HOPCaOFT, J. E. Independence of AFL operations. Tech. Rep. TM-738/034/00, System Development Corp., Santa Monica, Calif., July 1967.
	13	HARTMANIS, J., AND STEARNS, R.E. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117 (May 1965), 285-306.
	14	HOPCROFT, J. E., AND ULLMAN, J.D. Nonerasing stack automata. J. Camp. Syst. Sci. I, 2 (Ag. 1967), 166-186.
	15	KURODA, S. Y. Classes of languages and linear bounded automata. Inform. Contr. 7 (June 1964), 207-223.
	16	ROSENKRANTZ, D. J. Programmed grammars--a new device for generating formal languages. IEEE Conference Record of Eighth Annual Symposium on Switching and Automata Theory, IEEE pub. no. 16-C-56, Oct, 1967, pp. 14-20.

CITED BY 53

	Alfred V. Aho, Nested Stack Automata, Journal of the ACM (JACM), v.16 n.3, p.383-406, July 1969
	J. Engelfriet , G. Rozenberg, Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages, Journal of the ACM (JACM), v.27 n.3, p.499-518, July 1980
	Michael A. Harrison , Mario Schkolnick, A Grammatical Characterization of One-Way Nondeterministic Stack Languages, Journal of the ACM (JACM), v.18 n.2, p.148-172, April 1971
	K. Vijay-Shanker , David J. Weir, The use of shared forests in tree adjoining grammar parsing, Proceedings of the sixth conference on European chapter of the Association for Computational Linguistics, April 21-23, 1993, Utrecht, The Netherlands
	James W. Thatcher, Transformations and translations from the point of view of generalized finite automata theory, Proceedings of the first annual ACM symposium on Theory of computing, p.129-142, May 05-07, 1969, Marina del Rey, California, United States
	P. Boullier, Counting with range concatenation grammars, Theoretical Computer Science, v.293 n.2, p.391-416, 6 February 2003
	Joost Engelfriet , Erik Meineche Schmidt , Jan van Leeuwen, Stack Machines and Classes of Nonnested Macro Languages, Journal of the ACM (JACM), v.27 n.1, p.96-117, Jan. 1980
	Naoya Nitta , Hiroyuki Seki , Yashiaki Takata, Security verification of programs with stack inspection, Proceedings of the sixth ACM symposium on Access control models and technologies, p.31-40, May 2001, Chantilly, Virginia, United States
	William C. Rounds, Tree-oriented proofs of some theorems on context-free and indexed languages, Proceedings of the second annual ACM symposium on Theory of computing, p.109-116, May 04-06, 1970, Northampton, Massachusetts, United States
	A. V. Aho , J. D. Ullman, Translations on a context free grammar, Proceedings of the first annual ACM symposium on Theory of computing, p.93-112, May 05-07, 1969, Marina del Rey, California, United States
	Guozhu Dong, Datalog expressiveness of chain queries: grammar tools and characterizations, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.81-90, June 02-05, 1992, San Diego, California, United States
	Naoya Nitta , Yoshiaki Takata , Hiroyuki Seki, An efficient security verification method for programs with stack inspection, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA
	Sheila A. Greibach, Some restrictions on W-grammars, Proceedings of the sixth annual ACM symposium on Theory of computing, p.256-265, April 30-May 02, 1974, Seattle, Washington, United States
	H. J. Bürkle , A. Frick , Ch. Schlier, High level language oriented hardware and the post-von Neumann era, Proceedings of the 5th annual symposium on Computer architecture, p.60-65, April 03-05, 1978
	Alexander Okhotin, Boolean grammars, Information and Computation, v.194 n.1, p.19-48, 10 October 2004
	Paul M. Postal , D. Terence Langendoen, English and the class of context-free languages, Computational Linguistics, v.10 n.3-4, p.177-181, July-December 1984
	Pierre Boullier, Chinese numbers, MIX, scrambling, and range concatenation grammars, Proceedings of the ninth conference on European chapter of the Association for Computational Linguistics, June 08-12, 1999, Bergen, Norway
	Peter Staudacher, New frontiers beyond context-freeness: DI-grammars and DI-automata, Proceedings of the sixth conference on European chapter of the Association for Computational Linguistics, April 21-23, 1993, Utrecht, The Netherlands
	C. Raymond Perrault, On the mathematical properties of linguistic theories, Computational Linguistics, v.10 n.3-4, p.165-176, July-December 1984
	Bryan Ford, Parsing expression grammars: a recognition-based syntactic foundation, ACM SIGPLAN Notices, v.39 n.1, p.111-122, January 2004
	C. Raymond Perrault, On the mathematical properties of linguistic theories, Proceedings of the 21st annual meeting on Association for Computational Linguistics, June 15-17, 1983, Cambridge, Massachusetts
	Annius V. Groenink, Literal movement grammars, Proceedings of the seventh conference on European chapter of the Association for Computational Linguistics, March 27-31, 1995, Dublin, Ireland
	Yves Schabes, Stochastic lexicalized tree-adjoining grammars, Proceedings of the 14th conference on Computational linguistics, August 23-28, 1992, Nantes, France
	K. Vijay-Shanker , David J. Weir, Parsing some constrained grammar formalisms, Computational Linguistics, v.19 n.4, p.591-636, December 1993
	David Tugwell, A state-transition grammar for data-oriented parsing, Proceedings of the seventh conference on European chapter of the Association for Computational Linguistics, March 27-31, 1995, Dublin, Ireland
	Eric Villemonte de la Clergerie , Miguel Alonso Pardo, A tabular interpretation of a class of 2-Stack Automata, Proceedings of the 17th international conference on Computational linguistics, p.1333-1339, August 10-14, 1998, Montreal, Quebec, Canada
	Daniel Radzinski, Chinese number-names, tree adjoining languages, and mild context-sensitivity, Computational Linguistics, v.17 n.3, p.277-299, September 1991
	Detlef Wotschke, Degree-languages, polynomial time recognition, and the LBA problem, Proceedings of seventh annual ACM symposium on Theory of computing, p.145-152, May 05-07, 1975, Albuquerque, New Mexico, United States
	Joost Engelfriet, The delta operation: from strings to trees to strings, Formal and natural computing, Springer-Verlag New York, Inc., New York, NY, 2002
	Gerald Gazda , Geoffrey K. Pullum , Robert Carpenter , Ewan Klein , Thomas E. Hukari , Robert D. Levine, Category structures, Computational Linguistics, v.14 n.1, p.1-19, Winter 1988
	Janusz Jurek, On the construction of transition functions for DPLL(k) automata for syntactic pattern recognition, Machine Graphics & Vision International Journal, v.12 n.4, p.489-513, April 2003
	Carl Vogel , Ulrike Hahn , Holly Branigan, Cross-serial dependencies are not hard to process, Proceedings of the 16th conference on Computational linguistics, August 05-09, 1996, Copenhagen, Denmark
	Owen Rambow, Multiset-valued linear index grammars: imposing dominance constraints on derivations, Proceedings of the 32nd annual meeting on Association for Computational Linguistics, p.263-270, June 27-30, 1994, Las Cruces, New Mexico
	Vaughan R. Pratt, Top down operator precedence, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.41-51, October 01-03, 1973, Boston, Massachusetts
	David J. Weir , Arvind K. Joshi, Combinatory Categorial Grammars: generative power and relationship to Linear Context-Free Rewriting Systems, Proceedings of the 26th annual meeting on Association for Computational Linguistics, p.278-285, June 07-10, 1988, Buffalo, New York
	Walter J. Savitch, A formal model for context-free languages augmented with reduplication, Computational Linguistics, v.15 n.4, p.250-261, December 1989
	Robert C. Berwick, Computational complexity and lexical-functional grammar, Computational Linguistics, v.8 n.3-4, p.97-109, July-December 1982
	José M. Castaño, On the applicability of Global Index Grammars, Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, p.15-22, July 07-12, 2003, Sapporo, Japan
	Yves Schabes, Stochastic tree-adjoining grammars, Proceedings of the workshop on Speech and Natural Language, February 23-26, 1992, Harriman, New York
	I. McQuillan, The generative capacity of block-synchronized context-free grammars, Theoretical Computer Science, v.337 n.1-3, p.119-133, 9 June 2005
	Ian McQuillan, Descriptional complexity of block-synchronization context-free grammars, Journal of Automata, Languages and Combinatorics, v.9 n.2-3, p.317-332, September 2004
	Solomon Marcus , Gheorghe Păun , Carlos Martín-Vide, Contextual grammars as generative models of natural languages, Computational Linguistics, v.24 n.2, p.245-274, June 1998
	Zoltán Ésik , Werner Kuich, Formal tree series, Journal of Automata, Languages and Combinatorics, v.8 n.2, p.219-285, April 2003
	Colin Stirling, Model-Checking Games for Typed λ-Calculi, Electronic Notes in Theoretical Computer Science (ENTCS), 172, p.589-609, April, 2007
	Makoto Kanazawa, Abstract Families of Abstract Categorial Languages, Electronic Notes in Theoretical Computer Science (ENTCS), 165, p.65-80, November, 2006
	José M. Castaño, Global Index Grammars and Descriptive Power, Journal of Logic, Language and Information, v.13 n.4, p.403-419, March 2004
	Franziska Biegler , Ian McQuillan , Kai Salomaa, An infinite hierarchy induced by depth synchronization, Theoretical Computer Science, v.387 n.2, p.113-124, November, 2007
	Franziska Biegler, Synchronization functions of synchronized context-free grammars and languages, Journal of Automata, Languages and Combinatorics, v.12 n.1, p.7-24, January 2007
	Hiroyuki Seki , Yuki Kato, On the Generative Power of Multiple Context-Free Grammars and Macro Grammars, IEICE - Transactions on Information and Systems, v.E91-D n.2, p.209-221, February 2008
	Florin Manea , Victor Mitrana , Takashi Yokomori, Two complementary operations inspired by the DNA hairpin formation: Completion and reduction, Theoretical Computer Science, v.410 n.4-5, p.417-425, February, 2009
	Franziska Biegler , Kai Salomaa, On the synchronized derivation depth of context-free grammars, Theoretical Computer Science, v.410 n.35, p.3198-3208, August, 2009
	Gerald Gazdar, Phrase structure grammars and natural languages, Proceedings of the Eighth international joint conference on Artificial intelligence, p.556-565, August 08-12, 1983, Karlsruhe, West Germany
	Flavio D'Alessandro , Stefano Varricchio, On the growth of context-free languages, Journal of Automata, Languages and Combinatorics, v.13 n.2, p.95-104, April 2008