Stratified Context Unification Is NP-Complete

DOI10.1007/11814771_8zbMath1196.68112OpenAlexW1506928755MaRDI 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

Mathematics Subject Classification ID

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

Related Items (5)

Congruence Closure of Compressed Terms in Polynomial Time ⋮ Simplifying the signature in second-order unification ⋮ Dominance constraints in stratified context unification ⋮ Unification with Singleton Tree Grammars ⋮ Context unification with one context variable

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