Paper: Structural Disambiguation With Constraint Propagation

ACL ID P90-1005
Title Structural Disambiguation With Constraint Propagation
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1990
Authors

We present a new grammatical formalism called Con- straint Dependency Grammar (CDG) in which every grammatical rule is given as a constraint on word- to-word modifications. CDG parsing is formalized as a constraint satisfaction problem over a finite do- main so that efficient constraint-propagation algo- rithms can be employed to reduce structural am- biguity without generating individual parse trees. The weak generative capacity and the computational complexity of CDG parsing are also discussed.