The Complexity of Monadic Second-Order Unification
- 1 January 2008
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 38 (3) , 1113-1140
Abstract
Monadic second-order unification 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, where we use the technique of compressing solutions using singleton context-free grammars. We prove that monadic second-order matching is also NP-complete.Keywords
This publication has 19 references indexed in Scilit:
- Bounded Second-Order Unification Is NP-Complete2006
- Satisfiability of word equations with constants is in PSPACEJournal of the ACM, 2004
- Decidability of bounded second order unificationInformation and Computation, 2004
- On the Undecidability of Second-Order UnificationInformation and Computation, 2000
- Complexity of Makanin's algorithmJournal of the ACM, 1996
- Simple second-order languages for which unification is undecidableTheoretical Computer Science, 1991
- A unification algorithm for second-order monadic termsAnnals of Pure and Applied Logic, 1988
- The undecidability of the second-order unification problemTheoretical Computer Science, 1981
- THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUPMathematics of the USSR-Sbornik, 1977
- A unification algorithm for typed λ-calculusTheoretical Computer Science, 1975