An Efficient Graph Algorithm for Dominance Constraints

Special Issue of SODA 2001.ISSN: 0196-6774International audienceDominance 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