Publication details

Saarland University Computer Science

A Polynomial-Time Fragment of Dominance Constraints

Alexander Koller, Kurt Mehlhorn, Joachim Niehren

Proceedings of the 38th Annual Meeting of the Association of Computational Linguistics, pp. 368--375, 2000

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.

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009