Abstract
If we take the class of context-free phrase structure grammars (CFPSGs) and modify it so that (i) grammars are allowed to make use of finite feature systems and (ii) rules are permitted to manipulate the features in arbitrary ways, then what we end up with is equivalent to what we started out with. Suppose, however, that we take the class of contextfree phrase structure grammars and modify it so that (i) grammars are allowed to employ a single designated feature that takes stacks of items drawn from some finite set as its values, and (ii) rules are permitted to push items onto, pop items from, and copy the stack. What we end up with now is no longer equivalent to the CF-PSGs but is significantly more powerful, namely the indexed grammars (Aho, 1968). This class of grammars has been alluded to a number of times in the recent linguistic literature: by Klein (1981) in connection with nested comparative constructions, by Dahl (1982) in connection with topicalised pronouns, by Engdahl (1982) and Gazdar (1982) in connection with Scandinavian unbounded dependencies, by Huybregts (1984) and Pulman and Ritchie (1984) in connection with Dutch, by Marsh and Partee (1984) in connection with variable binding, and doubtless elsewhere as well.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aho, Alfred V. 1968. Indexed Grammars. Journal of the Association for Computing Machinery 15:647–671.
Aho, Alfred V. 1969. Nested Stack Automata. Journal of the Association for Computing Machinery 16:383–406.
Bresnan, Joan W., Ronald M. Kaplan, P. Stanley Peters, and Annie Zaenen. 1982. Cross-serial Dependencies in Dutch. Linguistic Inquiry 13:613–635.
Bertsch, Eberhard. 1975. Two Thoughts on’ Fast Recognition of Indexed Languages. Information and Control 29:381–384.
Bowers, John S. 1975. Adjectives and Adverbs in English. Foundations of Language 13:529–662.
Culy, Christopher. 1985. The Complexity of the Vocabulary of Bambara. Linguistics and Philosophy 8:345–351.
Dahl, Osten. 1982. Bound Pronouns in Dislocated Constituents. Manuscript, University of Stockholm.
Damm, Werner. 1982. The IO-and OI-hierarchies. Theoretical Computer Science 20:95–207.
Engdahl, Elisabet. 1980. The Syntax and Semantics of Questions in Swedish. PhD dissertation, University of Massachusetts at Amherst.
Engdahl, Elisabet. 1982. Restrictions on Unbounded Dependencies in Swedish. In Elisabet Engdahl and Eva Ejerhed (Eds.), Readings on Unbounded Dependencies in Scandinavian. Stockholm: Almqvist and Wiksell, 151–174.
Engelfriet, Joost and Erik Meineche Schmidt. 1977/78. IO and OI. Journal of Computer and System Sciences 15:328–353; 16:67–99.
Gazdar, Gerald. 1982. Phrase Structure Grammar. In Pauline Jacobson and Geoffrey K. Pullum (Eds.), The Nature of Syntactic Representation. Dordrecht: Reidel, 131–186.
Gazdar, Gerald and Geoffrey K. Pullum. 1985. Computationally Relevant Properties of Natural Languages and Their Grammars. New Generation Computing 3:273–306. [Also appeared as CSLI Report CSLI-85-24, Stanford, May 1985.]
Hayashi, Takeshi. 1973. On Derivation Trees of Indexed Grammars—an Extension of the uvwxy Theorem. Publ. RIMS (Kyoto University) 9:61–92.
Hopcroft, John and Jeffrey Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. Reading, Massachusetts: Addison-Wesley.
Huybregts, Riny. 1984. The Weak Inadequacy of Context-free Phone Structure Grammars. In Ger de Haan, Mieke Trommelen and Wim Zonneveld. (Eds.), Van Periferie naar Kern. Dordrecht: Foris
Klein, Ewan. 1981. The Syntax and Semantics of Nominal Comparatives. In M. Moneglia (Ed.), Atti de Seminario su Tempo e Verbale Strutture Quantificate in Forma Logica. Florence: Presso l’Accademia della Crusca
Maibaum, T. S. E. 1974. A Generalized Approach to Formal Languages. Journal of Computer and System Sciences 8:409–439.
Maling, Joan and Annie Zaenen. 1982. A Phrase Structure Account of Scandinavian Extraction Phenomena. In Pauline Jacobson and Geoffrey K. Pullum (Eds.) The Nature of Syntactic Representation. Dordrecht: Reidel. 229–282.
Marsh, William E. 1985. Some Conjectures on Indexed Languages. Paper presented to the Association for Symbolic Logic Meeting, Stanford University, July 15–19, 1985.
Marsh, William E. and Barbara H. Partee. 1984. How Non-context-free is Variable Binding? In Mark Cobler et al. (Eds.), Proceedings of the Third West Coast Conference on Formal Linguistics. Stanford: Stanford Linguistics Association, 179–190.
Parchmann, R., J. Duske and J. Specht. 1980a. On Deterministic Indexed Languages. Information and Control 45:48–67.
Parchmann, R., J. Duske and J. Specht. 1980b. Closure Properties of Deterministic Indexed Languages. Information and Control 46:200–218.
Pollard, Carl J. 1984. Generalized Phrase Structure Grammars, Head Grammars, and Natural Languages. Phd thesis, Stanford University.
Pollard, Carl J. 1985. Some Extensions of Context-free Grammars and Their Time Complexity. Paper presented to the Santa Cruz Workshop on the Mathematics of Grammars and Languages, June 25–28, 1985.
Pulman, Stephen G. and Graeme D. Ritchie. 1984. Indexed Grammars and Intersecting Dependencies. Unpublished paper, University of Cambridge.
Pullum, Geoffrey K. 1983. Context-freeness and the Computer Processing of Human Languages. Proceedings of the 21st Annual Meeting, Association for Computational Linguistics, Menlo Park, CA, 1–6.
Pullum, Geoffrey K. and Gerald Gazdar. 1982. Natural Languages and Context-free Languages. Linguistics and Philosophy 4:471–504.
Sag, Ivan A., Gerald Gazdar, Thomas Wasow and Steven Weisler. 1985. Coordination and How to Distinguish Categories. Natural Language and Linguistic Theory 3:117–171.
Shieber, Stuart M. 1985. Evidence Against the Context-freeness of Natural Language. Linguistics and Philosophy 8:333–343.
Zaenen, Annie, Elisabet Engdahl and Joan Maling. 1981. Resumptive Pronouns can be Syntactically Bound. Linguistic Inquiry 12:679–682.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1988 D. Reidel Publishing Company
About this chapter
Cite this chapter
Gazdar, G. (1988). Applicability of Indexed Grammars to Natural Languages. In: Reyle, U., Rohrer, C. (eds) Natural Language Parsing and Linguistic Theories. Studies in Linguistics and Philosophy, vol 35. Springer, Dordrecht. https://doi.org/10.1007/978-94-009-1337-0_3
Download citation
DOI: https://doi.org/10.1007/978-94-009-1337-0_3
Publisher Name: Springer, Dordrecht
Print ISBN: 978-1-55608-056-2
Online ISBN: 978-94-009-1337-0
eBook Packages: Springer Book Archive
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.