@InProceedings{Koller_et_al:2000,
AUTHOR = {Koller, Alexander and Mehlhorn, Kurt and Niehren, Joachim},
TITLE = {A Polynomial-Time Fragment of Dominance Constraints},
YEAR = {2000},
BOOKTITLE = {38th Annual Meeting of the Association of Computational Linguistics (ACL '00), October 1-8},
ADDRESS = {Hong Kong},
URL = {ftp://ftp.ps.uni-sb.de/pub/papers/ProgrammingSysLab/poly-dom.ps.gz},
ABSTRACT = {Dominance constraints are a logical language for describing trees that is widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify emphnormal dominance constraints, a natural fragment whose satisfiability problem we show to be in polynomial time. We present a quadratic satisfiability algorithm and use it in another algorithm that enumerates solutions efficiently. Our result is useful for various applications of dominance constraints and related formalisms.},
ANNOTE = {COLIURL : Koller:2000:PTF.pdf Koller:2000:PTF.ps}
}
|
