A New Algorithm for Normal Dominance Constraints

Manuel Bodirsky 1 Denys Duchier 2 Joachim Niehren 3, 4 Sebastian Miele 5
1 Department of Computer Science [Berlin]
2 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
4 LIFL - Laboratoire d'Informatique Fondamentale de Lille
5 Programming Systems Lab [Saarland]
Abstract : Dominance constraints are logical descriptions of trees. Efficient algorithms for the subclass of normal dominance constraints were recently proposed. We present a new and simpler graph algorithm solving these constraints more efficiently, in quadratic time per solved form. It also applies to weakly normal dominance constraints as needed for an application to computational linguistics. Subquadratic running time can be achieved employing decremental graph biconnectivity algorithms.
Mots-clés : contraintes de dominance graph algorithms dominance constraints algorithme de graphe
Type de document :
Communication dans un congrès
J. Ian Munro. ACM-SIAM Symposium on Discrete Algorithms - SODA'2003, Jan 2004, New Orleans, Louisiana, United States. ACM Press, pp.59-67, 2004, SODA '04 Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. 〈http://portal.acm.org/citation.cfm?id=982801〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00536536
Contributeur : Joachim Niehren <>
Soumis le : jeudi 18 novembre 2010 - 16:36:01
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : samedi 19 février 2011 - 02:45:17

Fichier

wndc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536536, version 1

Collections

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

Citation

Manuel Bodirsky, Denys Duchier, Joachim Niehren, Sebastian Miele. A New Algorithm for Normal Dominance Constraints. J. Ian Munro. ACM-SIAM Symposium on Discrete Algorithms - SODA'2003, Jan 2004, New Orleans, Louisiana, United States. ACM Press, pp.59-67, 2004, SODA '04 Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. 〈http://portal.acm.org/citation.cfm?id=982801〉. 〈inria-00536536〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

323

Téléchargements de fichiers

171

Contact


archive-ouverte@inria.fr