Por favor, use este identificador para citar o enlazar a este item:
http://hdl.handle.net/10261/138237
COMPARTIR / EXPORTAR:
SHARE CORE BASE | |
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE | |
Título: | On the complexity of bounded second-order unification and stratified context unification |
Autor: | Levy, Jordi CSIC ORCID ; Schmidt-Schauss, Manfred; Villaret, Mateu | Palabras clave: | Bounded second-order unification Tree grammars Lambda calculus Context unification |
Fecha de publicación: | 2011 | Editor: | Oxford University Press | Citación: | Logic Journal of the IGPL 19: 763- 789 (2011) | Resumen: | Bounded 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. | URI: | http://hdl.handle.net/10261/138237 | DOI: | 10.1093/jigpal/jzq010 | Identificadores: | doi: 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.pdf | 259,35 kB | Adobe PDF | Visualizar/Abrir |
CORE Recommender
SCOPUSTM
Citations
12
checked on 18-abr-2024
WEB OF SCIENCETM
Citations
6
checked on 29-feb-2024
Page view(s)
208
checked on 22-abr-2024
Download(s)
218
checked on 22-abr-2024
Google ScholarTM
Check
Altmetric
Altmetric
NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.