Computational Complexity of Current GPSG Theory

COMPUTATIONAL COMPLEXITY OF CURRENT GPSG THEORY Eric Sven Ristad MIT Artificial Intelligence Lab Thinking Machines Corporation 545 Technology Square and 245 First Street Cambridge, MA 02139 Cambridge, MA 02142 ABSTRACT 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 intractable. The paper pinpoints sources of complexity (e.g. metarules and the theory of syntactic features) in the current GPSG theory and concludes with some linguistically and computationally mo- tivated restrictions on GPSG. 1 Introduction 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. Gen- eralized Phrase Structure Grammar (GPSG) linguistic theory holds out considerable promise as an aid in this task. The pre- cise formalisms of GPSG offer the prospect of a direct and trans- parent guide for parser design and implementation. Further- more, and more importantly, GPSG's weak context-free gener- ative power suggests an efficiency advantage for GPSG-based parsers. Since context-free languages can be parsed in polyno- mial time, it seems plausible that GPSGs can also be parsed in polynomial time. This would in turn seem to provide "the be- ginnings of an explanation for the obvious, but largely ignored, fact thatlhumans process the utterances they hear very rapidly (Gazdar,198] :155)." 1 In this paper I argue that the expectations of the informal complexity argument from weak context-free generative power are not in fact met. I begin by examining the computational complexity of metarules and the feature system of GPSG and show that these systems can lead to computational intractabil- ~See also Joshi, "Tree Adjoining Grammars ~ p.226, in Natural Language Parsing (1985) ed. by D. Dowty, L. Karttunen, and A. Zwicky, Cambridge University Press: Cambridge, and aExceptlons to the Rule, ~ Science News 128: 314-315. ity. Next I prove that the universal recognition problem for cur- rent GPSG theory is Exp-Poly hard, and assuredly intractable. 2 That is, the problem of determining for an arbitrary GPSG G and input string z whether x is in the language L(G) gener- ated by G, is exponential polynomial time hard. This result puts GPSG-Recognition in a complexity class occupied by few natural problems: GPSG-Recognition is harder than the trav- eling salesman problem, context-sensitive language recognition, or winning the game of Chess on an n x n board. The complex- ity classification shows that the fastest recognition algorithm for GPSGs …

Content truncated to 500 words