GPSG (Generalized Phrase Structure Grammar) Recognition Is NP Hard,
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 O(cu h) time by a wide range of algorithms. Hence, it might be thought that GPSG's 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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1985
- Accession Number
- ADA162716
Entities
People
- Eric Sven Ristad
Organizations
- Massachusetts Institute of Technology