|Title||Monadic Second-Order Unifications is NP Complete|
|Publication Type||Conference Paper|
|Year of Publication||2004|
|Authors||Levy J, Schmidt-Schauss M, Villaret M|
|Conference Name||Lecture Notes in Computer Science|
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.
- About IIIA
- Current news