| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [31 references]
https://hal.inria.fr/inria-00536539
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
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
File
eff-dom.pdf
Files produced by the author(s)