On the relation between Context and Sequence Unification

Abstract

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.