A Polynomial-Time Fragment of Dominance Constraints

Alexander Koller, Kurt Mehlhorn, and Joachim Niehren

In Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics (ACL), Hong Kong, 2000.

Dominance 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 the natural fragment of <i>normal</i> dominance constraints and show that its satisfiability problem is in deterministic polynomial time.

Download: Download

BibTeX Entry
@InProceedings{poly-dom,
	author = {Alexander Koller and Kurt Mehlhorn and Joachim Niehren},
	title = {A Polynomial-Time Fragment of Dominance Constraints},
	booktitle = {Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics (ACL)},
	year = 2000,
	address = {Hong Kong}
}

Back: Publications