Computational Structure of GPSG Models: Revised Generalized Phrase Structure Grammar

Title: en_US Computational Structure of GPSG Models: Revised Generalized Phrase Structure Grammar
Creator: en_US Ristad, Eric Sven
Date: 2004-10-20T19:58:16Z
Date Available: 2004-10-20T19:58:16Z
Date Issued: en_US 1989-09-01
Identifier: en_US AITR-1170
uri: http://hdl.handle.net/1721.1/6821
Abstract: en_US The primary goal of this report is to demonstrate how considerations from computational complexity theory can inform grammatical theorizing. To this end, generalized phrase structure grammar (GPSG) linguistic theory is revised so that its power more closely matches the limited ability of an ideal speaker--hearer: GPSG Recognition is EXP-POLY time hard, while Revised GPSG Recognition is NP-complete. A second goal is to provide a theoretical framework within which to better understand the wide range of existing GPSG models, embodied in formal definitions as well as in implemented computer programs. A grammar for English and an informal explanation of the GPSG/RGPSG syntactic features are included in appendices.
Extent: en_US 93 p.; 10445845 bytes; 3991998 bytes
Format: application/postscript; application/pdf
Language: en_US
Relation: en_US AITR-1170
Subject: en_US linguistics; en_US complexity; en_US GPSG; en_US natural language; en_US scomputational structure; en_US computational complexity