Solvability of context equations with two context variables is decidable

DOI10.1006/jsco.2001.0438zbMath1017.68165OpenAlexW2065197261MaRDI QIDQ1599536

Klaus U. Schulz, Manfred Schmidt-Schauss

Publication date: 11 June 2002

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jsco.2001.0438

zbMATH Keywords

context unification

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Decidability of theories and sets of sentences (03B25) Mechanization of proofs and logical operations (03B35)

Related Items (7)

Decidability of bounded second order unification ⋮ Simplifying the signature in second-order unification ⋮ Dominance constraints in stratified context unification ⋮ Decidability of bounded higher-order unification ⋮ Flat matching ⋮ Context unification with one context variable ⋮ On rewrite constraints and context unification

Cites Work

• The undecidability of the second-order unification problem
• Equations in free semigroups
• Completion of rewrite systems with membership constraints. I: Deduction rules
• Completion of rewrite systems with membership constraints. II: Constraint solving
• A decision algorithm for distributive unification
• Word unification and transformation of generalized equations
• On the undecidability of second-order unification
• Unification in the union of disjoint equational theories: Combining decision procedures
• Minimal and complete word unification
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Complexity of Makanin's algorithm
• Undecidability of the first order theory of one-step right ground rewriting
• Linear second-order unification
• Solving word equations
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Solvability of context equations with two context variables is decidable