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
3 Allgemeine Linguistik - Allgemeine Linguistik Computational Linguistics and phonetics
4 LIFL - Laboratoire d'Informatique Fondamentale de Lille

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

Domaines: Informatique et langage [cs.CL]; Théorie et langage formel [cs.FL]; Algorithme et structure de données [cs.DS]

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, 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⟩