Skip to Main content Skip to Navigation
Journal articles

An Efficient Graph Algorithm for Dominance Constraints

Abstract : Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify normal dominance constraints and present an efficient graph algorithm for testing their satisfiablity in deterministic polynomial time. Previously, no polynomial time algorithm was known.
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : Joachim Niehren Connect in order to contact the contributor
Submitted on : Tuesday, November 16, 2010 - 1:50:27 PM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM
Long-term archiving on: : Thursday, February 17, 2011 - 2:59:50 AM


Files produced by the author(s)




Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, et al.. An Efficient Graph Algorithm for Dominance Constraints. Journal of Algorithms in Cognition, Informatics and Logic, Elsevier, 2003, Special issue: Twelfth annual ACM-SIAM symposium on discrete algorithms, 48 (1), pp.194-219. ⟨10.1016/S0196-6774(03)00050-6⟩. ⟨inria-00536539⟩



Les métriques sont temporairement indisponibles