Accession Number:

ADA162716

Title:

GPSG (Generalized Phrase Structure Grammar) Recognition Is NP Hard,

Descriptive Note:

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB

Personal Author(s):

Report Date:

1985-03-01

Pagination or Media Count:

13.0

Abstract:

Proponents of Generalized Phrase Structure Grammar GPSG often cite its weak context-free generative power as proof of the computational tractability of GPSG-Recognition. It is well known that context-free languages can be parsed in Ocu h time by a wide range of algorithms. Hence, it might be thought that GPSGs weak context-free generative power should guarantee that it too is efficiently parasible. This widely-assumed GPSG efficient parsibility result is false A reduction from 3-Satisfiability proves that GPSG-Recognition is a function of an input string and a grammar, and the GPSG metarule grammar can result in an arbitrarily large finite set of derived context-free rules. It is further demonstrated that a central object in GPSG theory, the metarule, inherently results in an intractable recognition problem, even when severely constrained. The implications for linguistics and natural parsing are discussed. Author

Subject Categories:

  • Linguistics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE