Well-nested Context Unification - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2005

Well-nested Context Unification

Résumé

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.
Fichier principal
Vignette du fichier
wellnested-cu.pdf (400.25 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00536525 , version 1 (18-11-2010)

Identifiants

  • HAL Id : inria-00536525 , version 1

Citer

Jordi Levy, Joachim Niehren, Mateu Villaret. Well-nested Context Unification. 20th International Conference on Automated Deduction, 2005, Tallinn, Estonia. pp.149-163. ⟨inria-00536525⟩
123 Consultations
108 Téléchargements

Partager

Gmail Facebook X LinkedIn More