Title | Monadic Second-Order Unifications is NP Complete |

Publication Type | Conference Paper |

Year of Publication | 2004 |

Authors | Levy J [1], Schmidt-Schauss M [2], Villaret M [3] |

Conference Name | Lecture Notes in Computer Science |

Volume | 3091 |

Publisher | Springer-Verlag |

Pagination | 55-69 |

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