Well-nested Context Unification

Abstract : Context unification (CU) is the famous open problem of solving context equations for trees. We distinguish a new decidable fragment of CU - well-nested CU - and present a new unification algorithm that solves well-nested context equations in non-deterministic polynomial time. We show that minimal well-nested solutions of context equations can be composed from the material present in the equation. This surprising property is highly wishful when modeling natural language ellipsis in CU.
Type de document :
Communication dans un congrès
Robert Nieuwenhuis. 20th International Conference on Automated Deduction, 2005, Tallinn, Estonia. Springer, 3632, pp.149-163, 2005, Lecture Notes in Computer Science
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-00536525
Contributeur : Joachim Niehren <>
Soumis le : jeudi 18 novembre 2010 - 16:52:22
Dernière modification le : vendredi 2 février 2018 - 19:24:01
Document(s) archivé(s) le : samedi 19 février 2011 - 02:44:35

Fichier

wellnested-cu.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536525, version 1

Collections

Citation

Jordi Levy, Joachim Niehren, Mateu Villaret. Well-nested Context Unification. Robert Nieuwenhuis. 20th International Conference on Automated Deduction, 2005, Tallinn, Estonia. Springer, 3632, pp.149-163, 2005, Lecture Notes in Computer Science. 〈inria-00536525〉

Partager

Métriques

Consultations de la notice

255

Téléchargements de fichiers

111