Títol | Well-Nested Context Unification |

Publication Type | Conference Paper |

Year of Publication | 2005 |

Authors | Levy J [1], Niehren J [2], Villaret M [3] |

Conference Name | Lecture Notes in Artificial Intelligence |

Volume | 3632 |

Editor | Springer-Verlag |

Paginació | 149-163 |

Resum | Context unification (CU) is the open problem of solving context equations for trees. We distinguish a new decidable variant 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 (see Theorem 1). This property is wishful when modeling natural language ellipsis in CU. |