A Polynomial-Time Fragment of Dominance Constraints

Dominance constraints are a logical language for describing trees that is widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify \emph{normal} dominance constraints, a natural fragment whose satisfiability problem we show to be in polynomial time. We present a quadratic satisfiability algorithm and use it in another algorithm that enumerates solutions efficiently. Our result is useful for various applications of dominance constraints and related formalisms