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

Monadic second-order unification Is NP-complete

AutorLevy, Jordi ; Schmidt-Schauss, Manfred; Villaret, Mateu
Palabras claveSecond-order matching
NP complete
Second orders
Fecha de publicación2004
EditorSpringer
CitaciónRewriting Techniques and Applications: 15th International Conference, RTA 2004. Proceedings. LNCS 3091: 55- 69 (2004)
ResumenMonadic Second-Order Unification (MSOU) 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. We also prove that Monadic Second-Order Matching is also NP-complete. © Springer-Verlag 2004.
URIhttp://hdl.handle.net/10261/160942
Identificadoresdoi: 10.1007/978-3-540-25979-4_4
issn: 0302-9743
isbn: 978-3-540-22153-1
Aparece en las colecciones: (IIIA) Comunicaciones congresos
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
RTA2004_LNCS3091_55-69.pdf148,95 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.