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.
Type de document :
Communication dans un congrès
38th Annual Meeting of the Association of Computational Linguistics, 2000, Hong Kong, China. pp.368--375, 2000
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00536809
Contributeur : Joachim Niehren <>
Soumis le : mardi 16 novembre 2010 - 23:09:39
Dernière modification le : lundi 20 novembre 2017 - 15:14:01
Document(s) archivé(s) le : jeudi 17 février 2011 - 03:14:33

Fichiers

poly-dom.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536809, version 1

Citation

Alexander Koller, Kurt Mehlhorn, Joachim Niehren. A Polynomial-Time Fragment of Dominance Constraints. 38th Annual Meeting of the Association of Computational Linguistics, 2000, Hong Kong, China. pp.368--375, 2000. 〈inria-00536809〉

Partager

Métriques

Consultations de la notice

61

Téléchargements de fichiers

122