    |
An Efficient Graph Algorithm for Dominance Constraints
Autor: Ernst Althaus and Denys Duchier and Alexander Koller and Kurt Mehlhorn and Joachim Niehren and Sven ThielHerausgeber:
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.
|