The Complexity of Monadic Second-Order Unification | Zendy

Jordi Levy | Zendy; Manfred Schmidt-Schauß | Zendy; Mateu Villaret | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The Complexity of Monadic Second-Order Unification

Author(s) -

Jordi Levy,

Manfred Schmidt-Schauß,

Mateu Villaret

Publication year - 2008

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/050645403

Subject(s) - unification , order (exchange) , monadic predicate calculus , mathematics , computational complexity theory , computer science , combinatorics , discrete mathematics , theoretical computer science , algorithm , programming language , finance , higher order logic , economics , description logic

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research