An Efficient Graph Algorithm for Dominance Constraints

Author: Ernst Althaus and Denys Duchier and Alexander Koller and Kurt Mehlhorn and Joachim Niehren and Sven Thiel

Editor:

Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify normal dominance constraints and present an efficient graph algorithm for testing their satisfiablity in deterministic polynomial time. Previously, no polynomial time algorithm was known.