Publication details

Programming Systems

Gert Smolka

Publications

Teaching

Software

Formalizations

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               

@INPROCEEDINGS{dombool,
  title = {Dominance Constraints with Set Operators},
  author = {Denys Duchier and Joachim Niehren},
  year = {2000},
  month = {jul},
  publisher = {{Springer}},
  booktitle = {Proceedings of the First International Conference on Computational Logic (CL2000)},
  series = {{Lecture Notes in Computer Science}},
  volume = {1861},
  pages = {{326-341}},
}

Login to edit