English   español  
Por favor, use este identificador para citar o enlazar a este item: http://hdl.handle.net/10261/162487
COMPARTIR / IMPACTO:
Estadísticas
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:
Título

Simplifying the signature in second-order unification

AutorLevy, Jordi ; Villaret, Mateu
Palabras claveContext unification
Lambda calculus
Second-order unification
Fecha de publicación2009
EditorSpringer
CitaciónApplicable Algebra in Engineering, Communications and Computing 20: 427- 445 (2009)
ResumenSecond-Order Unification is undecidable even for very specialized fragments. The signature plays a crucial role in these fragments. If all symbols are monadic, then the problem is NP-complete, whereas it is enough to have just one binary constant to lose decidability. In this work we reduce Second-Order Unification to Second-Order Unification with a signature that contains just one binary function symbol and constants. The reduction is based on partially currying the equations by using the binary function symbol for explicit application. Our work simplifies the study of Second-Order Unification and some of its variants, like Context Unification and Bounded Second-Order Unification. © 2009 Springer-Verlag.
URIhttp://hdl.handle.net/10261/162487
Identificadoresdoi: 10.1007/s00200-009-0106-4
issn: 0938-1279
Aparece en las colecciones: (IIIA) Artículos
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
accesoRestringido.pdf15,38 kBAdobe PDFVista previa
Visualizar/Abrir
Mostrar el registro completo
 


NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.