Paper: Computational Complexity Of Current GPSG Theory

ACL ID P86-1006
Title Computational Complexity Of Current GPSG Theory
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1986
  • Eric Sven Ristad (Massachusetts Institute of Technology, Cambridge MA; Thinking Machines Corporation, Cambridge MA)

An important goal of computational linguistics has been to use linguistic theory to guide the construction of computationally efficient real-world natural language processing systems. At first glance, generalized phrase structure grammar (GPSG) appears to be a blessing on two counts. First, the precise formalisms of GPSG might be a direct and fransparent guide for parser design and implementation. Second, since GPSG has weak context-free generative power and context-free languages can be parsed in O(n ~) by a wide range of algorithms, GPSG parsers would ap- pear to run in polynomial time. This widely-assumed GPSG "efficient parsability" result is misleading: here we prove that the universal recognition problem for current GPSG theory is exponential-polynomial time hard, and assuredly intra...