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