@Article{Althaus_et_al:2003,
AUTHOR = {Althaus, Ernst and Duchier, Denys and Koller, Alexander and Mehlhorn, Kurt and Niehren, Joachim and Thiel, Sven},
TITLE = {An Efficient Graph Algorithm for Dominance Constraints},
YEAR = {2003},
JOURNAL = {Journal of Algorithms},
VOLUME = {48},
PAGES = {194--219},
URL = {https://www.coli.uni-saarland.de/~koller/papers/eff-dom.ps.gz},
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.},
ANNOTE = {COLIURL : Althaus:19xx:EGA.pdf Althaus:19xx:EGA.ps}
}
|
