The computational difficulty of ID/LP parsing

Abstract

Modern linguistic theory attributes surface complexity to interacting subsystems of constraints. For instance, the ID/LP grammar formalism separates constraints on immediate dominance from those on linear order. Shieber's (1983) ID/LP parsing algorithm shows how to use ID and LP constraints directly in language processing, without expanding them into an intermediate "object grammar." However, Shieber's purported O(|G|2 n3) runtime bound underestimates the dificulty of ID/LP parsing. ID/LP parsing is actually NP-complete, and the worst-case runtime of Shieber's algorithm is actually exponential in grammar size. The growth of parser data structures causes the difficulty. Some computational and linguistic implications follow: in particular, it is important to note that despite its potential for combinatorial explosion, Shieber's algorithm remains better than the alternative of parsing an expanded object grammar.