SFB 378 Einstiegsseite Postscript File BibTeX Entry

C
CHORUS

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.

SFB 378 Einstiegsseite Postscript File BibTeX Entry