Dominance Constraints with Set Operators
Autor: Denys Duchier and Joachim Niehren
Herausgeber:
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.
|