tailieunhanh - Báo cáo khoa học: "DEFINING NATURAL LANGUAGE GRAMMARS IN GPSG"

The computational difficultyof the task can be clarified by investigating specific models of morphological processing. The use of finite-state machinery in the "twolevel" model by K i m m o Koskenniemi gives it the appearance of computational efficiency, but closer examination shows the model does not guarantee efficient processing. Reductions of the satisfiability problem show that finding the proper lexical/surface correspondence in a two-level generation or recognition problem can be computationally difficult. The difficulty increases if unrestricted deletions (null characters) are allowed | DEFINING NATURAL LANGUAGE GRAMMARS IN GPSG Eric Sven Ristad MIT Artificial Intelligence Lab 545 Technology Square Cambridge MA 02139 Thinking Machines Corporation and 245 First Street Cambridge MA 02142 1 Overview Three central goals of work in the generalized phrase structure grammar GPSG linguistic framework as stated in the leading book Generalized Phrase structure Grammar G azdar et al 1985 hereafter GKPS are 1 to characterize all and only the natural language grammars 2 to algorithmically determine membership and generative power consequences of GPSGs and 3 to embody the universalism of natural language entirely in the formal system rather than by statements made in These pages formally consider whether GPSG s weak context-free generative power wcfgp will allow it to achieve the three goals. The centerpiece of this paper is a proof that it is undecidable whether an arbitrary GPSG generates the nonnatural language S . On the basis of this result I argue that GPSG fails to define the natural language grammars and that the generative power consequences of the GPSG framework cannot be algorithmically determined contrary to goals one and In the process I examine the linguistic universalism of the GPSG formal system and argue that GPSGs can describe an infinite class of nonnatural context-free languages. The paper concludes with a brief diagnosis of the result and suggests that the problem might be met by abandoning the weak context-free generative power framework and assuming substantive constraints. The Structure of GPSG Theory A generalized phrase structure grammar contains five languageparticular components immediate dominance ID rules metarules linear precedence LP statements feature co-occurrence GKPS clearly outline their goals. One to arrive at a constrained metalanguage capable of defining the grammars of natural languages but not the grammar of say the set of prime numbers. . Two to construct an explicit linguistic theory whose formal .