Publication details

Programming Systems

Gert Smolka

Publications

Teaching

Software

Formalizations

Dominance Constraints: Algorithms and Complexity

Alexander Koller, Joachim Niehren, Ralf Treinen

Third International Conference on Logical Aspects of Computational Linguistics (Dec. 1998, Grenoble, France), Vol. 2014 of Lecture Note in Artificial Intelligence, pp. 106-125, Springer-Verlag, 2001

Dominance constraints for finite tree structures are widely used in several areas of computational linguistics including syntax, semantics, and discourse. In this paper, we investigate algorithmic and complexity questions for dominance constraints and their first-order theory. We present two NP algorithms for solving dominance constraints, which have been implemented in the concurrent constraint programming language Oz. The main result of this paper is that the satisfiability problem of dominance constraints is NP-complete. Despite this intractability result, the more sophisticated of our algorithms performs well in an application to scope underspecification. We also show that the existential fragment of the first-order theory of dominance constraints is NP-complete and that the full first-order theory has non-elementary complexity.

Download PDF        Show BibTeX               

@INPROCEEDINGS{DominanceNP:98-2001,
  title = {Dominance Constraints: Algorithms and Complexity},
  author = {Alexander Koller and Joachim Niehren and Ralf Treinen},
  year = {2001},
  editor = {{M. Moortgat}},
  publisher = {{Springer-Verlag}},
  booktitle = {Third International Conference on Logical Aspects of                Computational Linguistics (Dec. 1998, Grenoble, France)},
  series = {{Lecture Note in Artificial Intelligence}},
  volume = {2014},
  pages = {{106-125}},
  address = {{Heidelberg}},
}

Login to edit