Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-23754
Titel: An efficient graph algorithm for dominance constraints
Verfasser: Althaus, Ernst
Duchier, Denys
Koller, Alexander
Mehlhorn, Kurt
Niehren, Joachim
Thiel, Sven
Sprache: Englisch
Erscheinungsjahr: 2003
Quelle: Journal of Algorithms, Volume 48, Issue 1, August 2003, Pages 194-219
SWD-Schlagwörter: Constraints
DDC-Sachgruppe: 004 Informatik
Dokumentart : Journalartikel
Kurzfassung: 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.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-2717
hdl:20.500.11880/23810
http://dx.doi.org/10.22028/D291-23754
SciDok-Publikation: 24-Jun-2004
Fakultät: Sonstige Einrichtungen
Fachrichtung: SE - Sonstige Einrichtungen
Fakultät / Institution:SE - Sonstige Einrichtungen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
eff-dom.pdf257,68 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.