An Efficient Graph Algorithm for Dominance Constraints

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.
Type de document :
Article dans une revue
Journal of Algorithms in Cognition, Informatics and Logic, Elsevier, 2003, Special issue: Twelfth annual ACM-SIAM symposium on discrete algorithms, 48 (1), pp.194-219. 〈http://portal.acm.org/citation.cfm?id=989537〉. 〈10.1016/S0196-6774(03)00050-6〉
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00536539
Contributeur : Joachim Niehren <>
Soumis le : mardi 16 novembre 2010 - 13:50:27
Dernière modification le : jeudi 11 janvier 2018 - 06:20:12
Document(s) archivé(s) le : jeudi 17 février 2011 - 02:59:50

Fichier

eff-dom.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, et al.. An Efficient Graph Algorithm for Dominance Constraints. Journal of Algorithms in Cognition, Informatics and Logic, Elsevier, 2003, Special issue: Twelfth annual ACM-SIAM symposium on discrete algorithms, 48 (1), pp.194-219. 〈http://portal.acm.org/citation.cfm?id=989537〉. 〈10.1016/S0196-6774(03)00050-6〉. 〈inria-00536539〉

Partager

Métriques

Consultations de la notice

280

Téléchargements de fichiers

258