Publications

Monadic Second-Order Unifications is NP Complete

Publication Type:

Conference Paper

Authors:

Jordi Levy; Manfred Schmidt-Schauss; Mateu Villaret

Source:

Lecture Notes in Computer Science, Springer-Verlag, Volume 3091, p.55-69 (2004)

Abstract:

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.

»