Skip to Main content Skip to Navigation
Conference papers

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
Document type :
Conference papers
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download
https://hal.inria.fr/inria-00536536
Contributor : Joachim Niehren <>
Submitted on : Thursday, November 18, 2010 - 4:36:01 PM
Last modification on : Monday, June 15, 2020 - 12:00:33 PM
Long-term archiving on: : Saturday, February 19, 2011 - 2:45:17 AM

File

Vignette du document
wndc.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00536536, version 1

Collections

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

Citation

Manuel Bodirsky, Denys Duchier, Joachim Niehren, Sebastian Miele. A New Algorithm for Normal Dominance Constraints. ACM-SIAM Symposium on Discrete Algorithms - SODA'2003, Jan 2004, New Orleans, Louisiana, United States. pp.59-67. ⟨inria-00536536⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

537

Files downloads

219

 

Contact                    Legal Notice                    Personal Data