Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-23754 | Titel: | An efficient graph algorithm for dominance constraints |
| VerfasserIn: | 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 |
| Kontrollierte Schlagwörter: | Constraints |
| DDC-Sachgruppe: | 004 Informatik |
| Dokumenttyp: | Journalartikel / Zeitschriftenartikel |
| 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. |
| Link zu diesem Datensatz: | urn:nbn:de:bsz:291-scidok-2717 hdl:20.500.11880/23810 http://dx.doi.org/10.22028/D291-23754 |
| Datum des Eintrags: | 24-Jun-2004 |
| Fakultät: | SE - Sonstige Einrichtungen |
| Fachrichtung: | SE - Sonstige Einrichtungen |
| Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
| Datei | Beschreibung | Größe | Format | |
|---|---|---|---|---|
| eff-dom.pdf | 257,68 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.