The Complexity of Monadic Second-Order Unification

DOI10.1137/050645403zbMath1166.03004OpenAlexW2035973850MaRDI QIDQ3631904

Mateu Villaret, Jordi Levy, Manfred Schmidt-Schauss

Publication date: 22 June 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/050645403

zbMATH Keywords

theorem provingcontext-free grammarsrewriting systemslambda calculussecond-order unification

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatory logic and lambda calculus (03B40)

Related Items (3)

Grammar-Based Tree Compression ⋮ Linear pattern matching of compressed terms and polynomial rewriting ⋮ Parameter reduction and automata evaluation for grammar-compressed trees

This page was built for publication: The Complexity of Monadic Second-Order Unification