On the Complexity of ID/LP Parsing,
MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB
Pagination or Media Count:
Recent linguistic theories cast surface complexity as the result of interacting subsystems of constraints. For instance, the IDLP grammar formalism separates constraints on immediate dominance from those on linear order, Shieber 1983 has shown how to carry our direct parsing of IDLP grammars. His algorithm uses ID and LP constraints directly in language processing, without expanding them into a context-free object grammar. This report examines the computational difficulty of IDLP parsing the worst-case runtime of his algorithm is exponential in grammar size. A reduction of the vortex-cover problem proves that IDLP parsing is NP-complete. The growth of internal data structures is the source of difficulty in Shiebers algorithm. The computational and linguistic implications of these results are discussed. Despite the potential for combinatorial explosion, Shiebers algorithm remains better than the alternative of parsing an expanded object grammar.