2019-08-25T13:07:49Z
https://digital.csic.es/dspace-oai/request
oai:digital.csic.es:10261/161155
2018-05-28T07:52:50Z
com_10261_60
com_10261_4
col_10261_313
00925njm 22002777a 4500
dc
Kutsia, Temur
author
Levy, Jordi
author
Villaret, Mateu
author
2010
Both Sequence and Context Unification generalize the same problem: Word Unification. Besides that, Sequence Unification solves equations between unranked terms involving sequence variables, and seems to be appealing for information extraction in XML documents, program transformation, knowledge representation, and rule-based programming. It is decidable. Context Unification deals with the same problem for ranked terms involving context variables, and has applications in computational linguistics and program transformation. Its decidability is a long-standing open question. In this work we study a relation between these two problems. We introduce a variant (restriction) of Context Unification, called Left-Hole Context Unification (LHCU), to which Sequence Unification is P-reduced: We define a partial currying procedure to translate Sequence Unification problems into Left-Hole Context Unification problems, and prove the soundness of the translation. Furthermore, a precise characterization of the shape of the unifiers allows us to easily reduce Left-Hole Context Unification to (the decidable problem of) Word Unification with Regular Constraints, obtaining then a new decidability proof for Sequence Unification. Finally, we define an extension of Sequence Unification (ESU) and, closing the circle, prove the inter-P-reducibility of LHCU and ESU. © 2009 Elsevier Ltd. All rights reserved.
Journal of Symbolic Computation 45: 74- 95 (2010)
http://hdl.handle.net/10261/161155
http://dx.doi.org/10.13039/501100000780
http://dx.doi.org/10.13039/501100007273
Word unification
Sequence unification
Context unification
On the relation between Context and Sequence Unification