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
Document type :
Journal articles
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download
https://hal.inria.fr/inria-00536539
Contributor : Joachim Niehren <>
Submitted on : Tuesday, November 16, 2010 - 1:50:27 PM
Last modification on : Thursday, February 21, 2019 - 10:52:45 AM
Long-term archiving on : Thursday, February 17, 2011 - 2:59:50 AM

File

eff-dom.pdf
Files produced by the author(s)

Identifiers

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. ⟨10.1016/S0196-6774(03)00050-6⟩. ⟨inria-00536539⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

411

Files downloads

432

Contact


archive-ouverte@inria.fr