Eingang zum Volltext in SciDok
Hinweis zum Urheberrecht
Aufsatz zugänglich unter
An efficient graph algorithm for dominance constraints
URN: urn:nbn:de:bsz:291-scidok-2717
URL: http://scidok.sulb.uni-saarland.de/volltexte/2004/271/
Quelle:
(2003) Journal of Algorithms, Volume 48, Issue 1, August 2003, Pages 194-219
pdf-Format:
Dokument 1.pdf (258 KB)
SWD-Schlagwörter:
Constraints
Institut:
DDC-Sachgruppe:
Informatik
Dokumentart:
Aufsatz
Sprache:
Englisch
Erstellungsjahr:
2003
Publikationsdatum:
24.06.2004
Kurzfassung auf Englisch:
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.