TítuloMonadic Second-Order Unifications is NP Complete
Publication TypeConference Paper
Year of Publication2004
AuthorsLevy J, Schmidt-Schauss M, Villaret M
Conference NameLecture Notes in Computer Science
Volume3091
EditorialSpringer-Verlag
Paginación55-69
Resumen

Monadic 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.