A Polynomial-Time Fragment of Dominance Constraints
Author: Alexander Koller and Kurt Mehlhorn and Joachim Niehren
Editor:
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
\emphnormal 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.
|