English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/161155
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:

On the relation between Context and Sequence Unification

AuthorsKutsia, Temur; Levy, Jordi ; Villaret, Mateu
KeywordsWord unification
Sequence unification
Context unification
Issue Date2010
CitationJournal of Symbolic Computation 45: 74- 95 (2010)
AbstractBoth 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.
Identifiersdoi: 10.1016/j.jsc.2009.07.001
issn: 0747-7171
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
accesoRestringido.pdf15,38 kBAdobe PDFThumbnail
Show full item record
Review this work

Related articles:

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.