On the complexity of bounded second-order unification and stratified context unification

DOI10.1093/JIGPAL/JZQ010MaRDI QIDQ2889573zbMATH OpenOpenAlexFDO

Authors Jordi Levy, Mateu Villaret, Manfred Schmidt-Schauß

Publication date 8 June 2012

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/jigpal/jzq010

zbMATH Keywords

lambda-calculustree grammarscontext unificationbounded second-order unification

Mathematics Subject Classification ID

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

Recommendations

• Stratified Context Unification Is NP-Complete
• Decidability of bounded second order unification
• Bounded Second-Order Unification Is NP-Complete
• scientific article; zbMATH DE number 1841840
• A Decision Algorithm for Stratified Context Unification

Cited in

(10)

• The Complexity of Monadic Second-Order Unification
• Parameter reduction and automata evaluation for grammar-compressed trees
• On rewrite constraints and context unification
• Decidability of bounded second order unification
• scientific article; zbMATH DE number 1615236 (Why is no real title available?)
• scientific article; zbMATH DE number 1841840 (Why is no real title available?)
• Congruence closure of compressed terms in polynomial time
• Bounded Second-Order Unification Is NP-Complete
• Linear pattern matching of compressed terms and polynomial rewriting
• Stratified Context Unification Is NP-Complete

This page was built for publication: On the complexity of bounded second-order unification and stratified context unification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2889573)