@inbook{243381b7e310440286be024436fa56b2,
title = "Monadic second-order unification Is NP-complete",
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.",
author = "Jordi Levy and Manfred Schmidt-Schau{\ss} and Mateu Villaret",
year = "2004",
doi = "10.1007/978-3-540-25979-4\_4",
language = "English",
isbn = "3540221530",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "55--69",
editor = "\{van Oostrom\}, Vincent",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",
}