Publication details

Saarland University Computer Science

Dominance Constraints with Set Operators

Denys Duchier, Joachim Niehren

Proceedings of the First International Conference on Computational Logic (CL2000), Vol. 1861 of Lecture Notes in Computer Science, pp. 326-341, Springer, July 2000

Dominance constraints are widely used in computational linguistics as a language for talking and reasoning about trees. In this paper, we extend dominance constraints by admitting set operators. Set operators contribute a controlled form of disjunction that is emminently well-suited for constraint propagation. We present a solver for dominance constraints with set operators as a system of abstract propagation and distribution rules, and prove its soundness and completeness. We then derive an efficient implementation in a constraint programming language with finite sets and prove its faithfullness to the abstract inference rules.

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009