Stratified Context Unification Is NP-Complete

DOI10.1007/11814771_8MaRDI QIDQ3613402zbMATH OpenOpenAlexFDO

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

Publication date 12 March 2009

Published in Automated Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11814771_8

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42)

Recommendations

• On the complexity of bounded second-order unification and stratified context unification
• A Decision Algorithm for Stratified Context Unification
• Dominance constraints in stratified context unification
• scientific article; zbMATH DE number 1841840
• Two-restricted one context unification is in polynomial time
• One-context unification with STG-compressed terms is in NP
• NP-completeness results for deductive problems on stratified terms
• Automated Deduction – CADE-20
• Deciding context unification (with regular constraints)
• One context unification problems solvable in polynomial time

Cited in

(10)

• Unification with Singleton Tree Grammars
• Simplifying the signature in second-order unification
• Dominance constraints in stratified context unification
• On rewrite constraints and context unification
• NP-completeness results for deductive problems on stratified terms
• Context unification with one context variable
• scientific article; zbMATH DE number 1841840 (Why is no real title available?)
• On the complexity of bounded second-order unification and stratified context unification
• Congruence closure of compressed terms in polynomial time
• A Decision Algorithm for Stratified Context Unification

This page was built for publication: Stratified Context Unification Is NP-Complete

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