Constraint Dependency Grammar

Natural language sentences sometimes have more than exponential syntactic ambiguities. Structural disambiguation should be done without explicitly generating individual parse trees. In this paper, we present a new grammatical formalism called Constraint Dependency Grammar (CDG) in which every grammatical rule is given as a constraint on word-to-word modifications. In CDG parsing, the intermediate parsing result is implicitly represented as a single constraint network. Every solution that satisfies the constraints corresponds to an individual parse. New constraints can be dynamically added to the network until the syntactic ambiguity becomes reasonably small. An efficient constraint-propagation algorithm is employed to keep the network locally consistent. The initial formation of the constraint network and the constraint propagation over the network have a polynomial time bound, whereas the weak generative capacity of CDG is strictly greater than that of Context Free Grammar (CFG).