Computational Structure of GPSG (Generalized Phrase Structure Grammar) Models: Revised Generalized Phrase Structure Grammar.

摘要

A central goal of mathematical linguistics is to precisely determine the power of a linguistic theory. Traditionally, formal language theory (the Chomsky hierarchy) and its generative power analyses have translated this question into the narrower question of how unrestricted the rule format of a theory is. Modern computational complexity theory offers another, more useful, translation: how much of what computational resources does a theory consume. Complexity theory also offers a new perspective on descriptive adequacy. In a descriptively adequate linguistic theory, the structural descriptions and computational power of the theory match those of an ideal speaker-hearer. The primary goal of this paper is to demonstrate how considerations from computational complexity theory can inform grammatical theorizing. To this end, the paper revises generalized phrase structure grammar (GPSG) linguistic theory so that its computational power more closely matches the limited computational ability of an ideal speaker-hearer. A second goal is to provide a theoretical framework within which to better understand the wide range of GPSG models that have appeared in the theoretical and computational linguistics literature, embodied in formal definitions as well as in implemented computer programs. (KR)