Stratified Context Unification Is NP-Complete
From MaRDI portal
Publication:3613402
DOI10.1007/11814771_8zbMATH Open1196.68112OpenAlexW1506928755MaRDI QIDQ3613402FDOQ3613402
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
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42)
Cited In (8)
- Unification with Singleton Tree Grammars
- Simplifying the signature in second-order unification
- Dominance constraints in stratified context unification
- Congruence Closure of Compressed Terms in Polynomial Time
- On rewrite constraints and context unification
- Context unification with one context variable
- Title not available (Why is that?)
- 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)
