Bounded Second-Order Unification Is NP-Complete
From MaRDI portal
Publication:3527311
DOI10.1007/11805618_30zbMath1151.68450OpenAlexW1521552748MaRDI QIDQ3527311
Mateu Villaret, Jordi Levy, Manfred Schmidt-Schauss
Publication date: 25 September 2008
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11805618_30
Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (6)
Congruence Closure of Compressed Terms in Polynomial Time ⋮ Simplifying the signature in second-order unification ⋮ On the building of affine retractions ⋮ Parameter reduction and automata evaluation for grammar-compressed trees ⋮ Parameter Reduction in Grammar-Compressed Trees ⋮ Unification with Singleton Tree Grammars
This page was built for publication: Bounded Second-Order Unification Is NP-Complete
