Revised Generalized Phrase Structure Grammar

REVISED GENERALIZED PHRASE STRUCTURE GRAMMAR Eric Sven Rlstad 1 M.I.T. Artificial Intelligence Lab 545 Technology Square, 805 Cambridge, MA 02139 Thinking Machines Corporation 245 First Street Cambridge, MA 02142 ABSTRACT In this paper, I revise generalized phrase structure grammar (GPSG) linguistic theory so that it is more tractable and linguis- tically constrained. Revised GPSG is also easier to understand, use, and implement. I provide an account of topicalization, ex- plicative pronouns, and parasitic gaps in the revised system and conclude with suggestions for efficient parser design. 1 Introduction and Motivation A linguistic theory specifies a computational process that assigns structural descriptions to utterances. This process requires cer- tain computational resources, such as time or space. In a descrip- tively adequate linguistic theory, the computational resources available to the theory match those used by the ideal speaker- hearer. The goal of this paper is to revise generalized phrase structure grammar (GPSG) so that its computational power cor- responds to the ability of the speaker-hearer. The bulk of this paper is devoted to identifying what com- putational resources are used by GPSG theory, and deciding whether they are linguistically necessary. GPSG contains five formal devices, each of which provides the theory with the re- sources to model some linguistic phenomenon or ability. I iden- tify those aspects of each device that cause intractability and then restrict the computational power of each device to more closely match the (inherent) complexity of the phenomenon or ability it models. The remainder of the paper presents the new formal system and exercises it in the domain of topicalization, explica- tive pronouns, and parasitic gaps. I conclude with suggestions for efficient parser design and future research. In my opinion, the primary value of this work lies in the re- sult (revised GPSG, or RGPSG) as well as in the methodology of using complexity analysis to improve linguistic theories. The methodology explicates how a tool of modern computer science can help us understand and improve theories of linguistic compe- tence. More than that, complexity analysis forms the foundation of informed parser design. I feel RGPSG is of value both to lin- guists and computational linguists because it is more tractable and easier to understand, use, and implement. It can be effi- ciently implemented and appears to have better empirical cover- age than its GPSG ancestor. tThe author is eupported by a graduate fellowship from the IBM Corpora- tion. This research was supported in part by Thinking Machines Corporation and by NSF Grant DCR-85552543, under a Presidential Young Investigator Award to Profeuor Robert C. Berwick. I wish to thank Ed Barton for stylistic improvements and helpful discussion; Robert Berwick for support, critickm, and suggesting I pursue thk research; and Geoff Pullum for his patient help with GPSG theory. 2 Eliminating Intractability in GPSG Ristad (1986a) examines the computational complexity of two components of the GPSG formal system (metarules and the fea- ture system) and shows how each of these systems can lead to computational intractability. Rlstad also proves that …

Content truncated to 500 words