An Efficient Graph Algorithm for Dominance Constraints

Ernst Althaus 1 Denys Duchier 2 Alexander Koller 3 Kurt Mehlhorn 1 Joachim Niehren 4 Sven Thiel 1
1 MPII - Max-Planck-Institut für Informatik
2 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 Allgemeine Linguistik - Allgemeine Linguistik Computational Linguistics and phonetics
4 LIFL - Laboratoire d'Informatique Fondamentale de Lille
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.
Mots-clés : contraintes de dominance graph algoritm dominance constraints algorithme de graphe
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 20 septembre 2018 - 07:54:02
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

INRIA | UNIV-LILLE3 | LIFL | LORIA | UNIV-LORRAINE

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

292

Téléchargements de fichiers

267

Contact


archive-ouverte@inria.fr