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

DOI10.1093/JIGPAL/JZQ010zbMATH Open1252.68160OpenAlexW2168518033MaRDI QIDQ2889573FDOQ2889573

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

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

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)

Cited In (10)

• Bounded Second-Order Unification Is NP-Complete
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Stratified Context Unification Is NP-Complete
• Congruence closure of compressed terms in polynomial time
• Linear pattern matching of compressed terms and polynomial rewriting

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)