Makanin's algorithm is not primitive recursive

DOI10.1016/S0304-3975(96)00321-0zbMath0908.68107OpenAlexW1969654785MaRDI QIDQ1127320

Leszek Pacholski, Antoni Kościelski

Publication date: 13 August 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00321-0

zbMATH Keywords

equational satisfiability in semigroupsMakanin's decision procedure

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

POLYNOMIAL-TIME COMPLEXITY FOR INSTANCES OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS ⋮ An analysis of Makanin's algorithm deciding solvability of equations in free groups ⋮ Equations in free semigroups with involution and their relation to equations in free groups. ⋮ Solving one-variable equations in free groups ⋮ On PSPACE generation of a solution set of a word equation and its applications ⋮ The existential theory of equations with rational constraints in free groups is PSPACE-complete ⋮ SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solutions principales et rang d'un système d'équations avec constantes dans le monoide libre
• Investigations on algorithmic questions of algebra
• Word unification and transformation of generalized equations
• EQUATIONS IN A FREE GROUP
• Minimal and complete word unification
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• ON SYSTEMS OF EQUATIONS IN A FREE GROUP
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Complexity of Makanin's algorithm
• Solving word equations
• An analysis of Makanin's algorithm deciding solvability of equations in free groups

This page was built for publication: Makanin's algorithm is not primitive recursive