Bounded Second-Order Unification Is NP-Complete

DOI10.1007/11805618_30MaRDI QIDQ3527311zbMATH OpenOpenAlexFDO

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

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

Mathematics Subject Classification ID

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

Recommendations

• Decidability of bounded second order unification
• Rewriting Techniques and Applications
• On the complexity of bounded second-order unification and stratified context unification
• scientific article; zbMATH DE number 1189058
• The undecidability of the second order predicate unification problem
• On the undecidability of second-order unification
• Decidability of bounded higher-order unification
• scientific article; zbMATH DE number 1948184
• The Complexity of Monadic Second-Order Unification
• Monadic second order finite satisfiability and unbounded tree-width

Cited in

(11)

• Decidability of bounded second order unification
• The STO-problem is NP-hard
• On the complexity of bounded second-order unification and stratified context unification
• Congruence closure of compressed terms in polynomial time
• On the building of affine retractions
• Parameter Reduction in Grammar-Compressed Trees
• The Complexity of Monadic Second-Order Unification
• Unification with Singleton Tree Grammars
• Parameter reduction and automata evaluation for grammar-compressed trees
• Rewriting Techniques and Applications
• Simplifying the signature in second-order unification

This page was built for publication: Bounded Second-Order Unification Is NP-Complete

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