An Efficient Graph Algorithm for Dominance Constraints - Archive ouverte HAL Access content directly
Journal Articles Journal of Algorithms in Cognition, Informatics and Logic Year : 2003

An Efficient Graph Algorithm for Dominance Constraints

(1) , (2) , (3) , (1) , (4) , (1)
1
2
3
4

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.
Fichier principal
Vignette du fichier
eff-dom.pdf (257.68 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00536539 , version 1 (16-11-2010)

Identifiers

Cite

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, 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⟩
183 View
296 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More