Makanin's algorithm is not primitive recursive
From MaRDI portal
Publication:1127320
Cites work
- An analysis of Makanin's algorithm deciding solvability of equations in free groups
- Complexity of Makanin's algorithm
- DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
- EQUATIONS IN A FREE GROUP
- scientific article; zbMATH DE number 3329006 (Why is no real title available?)
- scientific article; zbMATH DE number 3413831 (Why is no real title available?)
- scientific article; zbMATH DE number 3424272 (Why is no real title available?)
- Investigations on algorithmic questions of algebra
- Minimal and complete word unification
- ON SYSTEMS OF EQUATIONS IN A FREE GROUP
- Solutions principales et rang d'un système d'équations avec constantes dans le monoide libre
- Solving word equations
- THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
- Word unification and transformation of generalized equations
Cited in
(8)- Equations in free semigroups with involution and their relation to 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
- Solving one-variable equations in free groups
- 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
- Solving one variable word equations in the free group in cubic time
This page was built for publication: Makanin's algorithm is not primitive recursive
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1127320)
