English   español  
Por favor, use este identificador para citar o enlazar a este item: http://hdl.handle.net/10261/138237
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

On the complexity of bounded second-order unification and stratified context unification

AutorLevy, Jordi ; Schmidt-Schauss, Manfred; Villaret, Mateu
Palabras claveBounded Second-Order Unification
Tree Grammars
Lambda-Calculus
Context Unification
Fecha de publicación2011
EditorOxford University Press
CitaciónLogic Journal of the IGPL 19: 763- 789 (2011)
ResumenBounded Second-Order Unification is a decidable variant of undecidable Second-Order Unification. Stratified Context Unification is a decidable restriction of Context Unification, whose decidability is a long-standing open problem. This paper is a join of two separate previous, preliminary papers on NP-completeness of Bounded Second-Order Unification and Stratified Context Unification. It clarifies some omissions in these papers, joins the algorithmic parts that construct a minimal solution, and gives a clear account of a method of using singleton tree grammars for compression that may have potential usage for other algorithmic questions in related areas. © The Author 2010. Published by Oxford University Press. All rights reserved.
URIhttp://hdl.handle.net/10261/138237
DOI10.1093/jigpal/jzq010
Identificadoresdoi: 10.1093/jigpal/jzq010
issn: 1367-0751
Aparece en las colecciones: (IIIA) Artículos
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
LJIGPL_19(6)2011_763-89.pdf259,35 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.