Publication details

Programming Systems

Gert Smolka

Publications

Teaching

Software

Formalizations

A Polynomial-Time Fragment of Dominance Constraints

Alexander Koller, Kurt Mehlhorn, Joachim Niehren

Proceedings of the 38th Annual Meeting of the Association of Computational Linguistics, pp. 368--375, 2000

Dominance constraints are a logical language for describing trees that is widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify emphnormal dominance constraints, a natural fragment whose satisfiability problem we show to be in polynomial time. We present a quadratic satisfiability algorithm and use it in another algorithm that enumerates solutions efficiently. Our result is useful for various applications of dominance constraints and related formalisms.

Download PDF        Show BibTeX               

@INPROCEEDINGS{KolMehNie00,
  title = {A Polynomial-Time Fragment of Dominance Constraints},
  author = {Alexander Koller and Kurt Mehlhorn and Joachim Niehren},
  year = {2000},
  month = {"3--6"#oct},
  booktitle = {Proceedings of the 38th Annual Meeting of the                 Association of Computational Linguistics},
  pages = {{368--375}},
  address = {{Hong Kong}},
}

Login to edit