Dominance Constraints: Algorithms and Complexity

Abstract : Dominance constraints for finite tree structures are widely used in several areas of computational linguistics including syntax, semantics, and discourse. In this paper, we investigate algorithmic and complexity questions for dominance constraints and their first-order theory. We present two NP algorithms for solving dominance constraints, which have been implemented in the concurrent constraint programming language Oz. The main result of this paper is that the satisfiability problem of dominance constraints is NP-complete. Despite this intractability result, the more sophisticated of our algorithms performs well in an application to scope underspecification. We also show that the existential fragment of the first-order theory of dominance constraints is NP-complete and that the full first-order theory has non-elementary complexity.
Type de document :
Communication dans un congrès
M. Moortgat. Third International Conference on Logical Aspects of Computational Linguistics 1998 (Postproceedings 2001), 1998, Grenoble, France. Springer, 2014, pp.106-125, 2001, Lecture Notes on Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00536812
Contributeur : Joachim Niehren <>
Soumis le : mardi 16 novembre 2010 - 23:09:49
Dernière modification le : mardi 24 avril 2018 - 13:51:42
Document(s) archivé(s) le : jeudi 17 février 2011 - 03:15:45

Fichiers

DominanceNP98.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536812, version 1

Collections

Citation

Alexander Koller, Joachim Niehren, Ralf Treinen. Dominance Constraints: Algorithms and Complexity. M. Moortgat. Third International Conference on Logical Aspects of Computational Linguistics 1998 (Postproceedings 2001), 1998, Grenoble, France. Springer, 2014, pp.106-125, 2001, Lecture Notes on Computer Science. 〈inria-00536812〉

Partager

Métriques

Consultations de la notice

134

Téléchargements de fichiers

63