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.
Liste complète des métadonnées

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/inria-00536539
Contributor : Joachim Niehren <>
Submitted on : Tuesday, November 16, 2010 - 1:50:27 PM
Last modification on : Thursday, February 21, 2019 - 10:52:45 AM
Document(s) archivé(s) le : Thursday, February 17, 2011 - 2:59:50 AM

File

eff-dom.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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. ⟨http://portal.acm.org/citation.cfm?id=989537⟩. ⟨10.1016/S0196-6774(03)00050-6⟩. ⟨inria-00536539⟩

Share

Metrics

Record views

352

Files downloads

311