English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/138237
Share/Impact:
Statistics
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:
Title

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

AuthorsLevy, Jordi ; Schmidt-Schauss, Manfred; Villaret, Mateu
KeywordsBounded Second-Order Unification
Tree Grammars
Lambda-Calculus
Context Unification
Issue Date2011
PublisherOxford University Press
CitationLogic Journal of the IGPL 19: 763- 789 (2011)
AbstractBounded 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
Identifiersdoi: 10.1093/jigpal/jzq010
issn: 1367-0751
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
LJIGPL_19(6)2011_763-89.pdf259,35 kBAdobe PDFThumbnail
View/Open
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.