| HAL-Inria | Les publications, logiciels... des scientifiques Inria |
Communication dans un congrès
A Polynomial-Time Fragment of Dominance Constraints
Abstract : Dominance constraints are a logical language for describing trees that is widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify emphnormal dominance constraints, a natural fragment whose satisfiability problem we show to be in polynomial time. We present a quadratic satisfiability algorithm and use it in another algorithm that enumerates solutions efficiently. Our result is useful for various applications of dominance constraints and related formalisms.
Littérature citée [19 références]
https://hal.inria.fr/inria-00536809
Contributeur : Joachim Niehren <>
Soumis le : mardi 16 novembre 2010 - 23:09:39
Dernière modification le : jeudi 20 septembre 2018 - 07:54:02
Document(s) archivé(s) le : jeudi 17 février 2011 - 03:14:33
Contributeur : Joachim Niehren <>
Soumis le : mardi 16 novembre 2010 - 23:09:39
Dernière modification le : jeudi 20 septembre 2018 - 07:54:02
Document(s) archivé(s) le : jeudi 17 février 2011 - 03:14:33
Fichiers
poly-dom.pdf
Fichiers produits par l'(les) auteur(s)