Stratified Context Unification Is NP-Complete
From MaRDI portal
Publication:3613402
DOI10.1007/11814771_8zbMath1196.68112MaRDI QIDQ3613402
Jordi Levy, Mateu Villaret, Manfred Schmidt-Schauss
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
68Q42: Grammars and rewriting systems
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Simplifying the signature in second-order unification, Dominance constraints in stratified context unification, Context unification with one context variable, Congruence Closure of Compressed Terms in Polynomial Time, Unification with Singleton Tree Grammars