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


The complexity of monadic second-order unification

AuthorsLevy, Jordi ; Schmidt-Schauss, Manfred ; Villaret, Mateu
KeywordsTheorem proving
Rewriting systems
Second-order unification
Lambda calculus
Context-free grammars
Issue Date2008
PublisherSociety for Industrial and Applied Mathematics
CitationSIAM Journal on Computing 38: 1113- 1140 (2008)
AbstractMonadic second-order unification is second-order unification where all function constants occurring in the equations are unary. Here we prove that the problem of deciding whether a set of monadic equations has a unifier is NP-complete, where we use the technique of compressing solutions using singleton context-free grammars. We prove that monadic second-order matching is also NP-complete. © 2008 Society for Industrial and Applied Mathematics.
Identifiersdoi: 10.1137/050645403
issn: 0097-5397
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.