Skip to Main content Skip to Navigation
Conference papers

A Polynomial-Time Fragment of Dominance Constraints

Abstract : 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.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Joachim Niehren Connect in order to contact the contributor
Submitted on : Tuesday, November 16, 2010 - 11:09:39 PM
Last modification on : Thursday, September 20, 2018 - 7:54:02 AM
Long-term archiving on: : Thursday, February 17, 2011 - 3:14:33 AM


Files produced by the author(s)


  • HAL Id : inria-00536809, version 1


Alexander Koller, Kurt Mehlhorn, Joachim Niehren. A Polynomial-Time Fragment of Dominance Constraints. 38th Annual Meeting of the Association of Computational Linguistics, 2000, Hong Kong, China. pp.368--375. ⟨inria-00536809⟩



Record views


Files downloads