Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

A Polynomial-Time Fragment of Dominance Constraints


Koller,  Alexander
Max Planck Society;


Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Koller, A., Mehlhorn, K., & Niehren, J. (2000). A Polynomial-Time Fragment of Dominance Constraints. In Proceedings of the 38th Annual Meeting of the Association of Computational Linguistics (ACL-00) (pp. 368-375). San Francisco, USA: Morgan Kaufmann.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-3355-D
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.