Paper: A Polynomial-Time Fragment Of Dominance Constraints

ACL ID P00-1047
Title A Polynomial-Time Fragment Of Dominance Constraints
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2000
Authors

Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satis ability problem is known to be NP-complete. Here we identify the natural fragment of normal dominance constraints and show that its satis ability problem is in deterministic polynomial time.