Complexity of Makanin's algorithm
From MaRDI portal
Publication:4371685
Recommendations
Cited in
(26)- Two-variable word equations
- On word equations in one variable
- Equations in free semigroups with involution and their relation to equations in free groups.
- Efficient solving of the word equations in one variable
- scientific article; zbMATH DE number 1189059 (Why is no real title available?)
- Extending free pregroups with lower bounds
- Finding all solutions of equations in free groups and monoids with involution
- On the complexity of computation maximal exponent of periodicity of word equations and expressible relations (note)
- An analysis of Makanin's algorithm deciding solvability of equations in free groups
- The hardness of solving simple word equations
- Towards Decidability of Conjugacy of Pairs and Triples
- Unification in commutative semigroups
- Solvability of context equations with two context variables is decidable
- On the relation between context and sequence unification
- On PSPACE generation of a solution set of a word equation and its applications
- Makanin's algorithm is not primitive recursive
- Monadic simultaneous rigid \(E\)-unification and related problems
- Decidability of bounded higher-order unification
- The existential theory of equations with rational constraints in free groups is PSPACE-complete
- On equality up-to constraints over finite trees, context unification, and one-step rewriting
- The expressibility of languages and relations by word equations
- EXPONENT OF PERIODICITY OF WORD EQUATIONS IN FIXED DIMENSION IS POLYNOMIAL
- More than 1700 years of word equations
- Word equations in non-deterministic linear space
- \(\forall \exists^{5}\)-equational theory of context unification is undecidable
- Monadic simultaneous rigid \(E\)-unification
This page was built for publication: Complexity of Makanin's algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4371685)
