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.
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00536525
Contributor : Joachim Niehren <>
Submitted on : Thursday, November 18, 2010 - 4:52:22 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Saturday, February 19, 2011 - 2:44:35 AM

File

wellnested-cu.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00536525, version 1

Collections

Citation

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

Share

Metrics

Record views

333

Files downloads

262