Complexity of Makanin's algorithm
From MaRDI portal
Publication:4371685
DOI10.1145/234533.234543zbMath0882.68073OpenAlexW2054924158WikidataQ128392129 ScholiaQ128392129MaRDI QIDQ4371685
Leszek Pacholski, Antoni Kościelski
Publication date: 22 January 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://www.acm.org/pubs/contents/journals/jacm/1996-43/
Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)
Related Items (25)
EXPONENT OF PERIODICITY OF WORD EQUATIONS IN FIXED DIMENSION IS POLYNOMIAL ⋮ Finding all solutions of equations in free groups and monoids with involution ⋮ The expressibility of languages and relations by word equations ⋮ Monadic simultaneous rigid E-unification and related problems ⋮ Makanin's algorithm is not primitive recursive ⋮ Unification in commutative semigroups ⋮ More Than 1700 Years of Word Equations ⋮ Efficient solving of the word equations in one variable ⋮ 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. ⋮ Monadic simultaneous rigid \(E\)-unification ⋮ Decidability of bounded higher-order unification ⋮ Two-variable word equations ⋮ Word equations in non-deterministic linear space ⋮ On word equations in one variable ⋮ Towards Decidability of Conjugacy of Pairs and Triples ⋮ Extending free pregroups with lower bounds ⋮ On equality up-to constraints over finite trees, context unification, and one-step rewriting ⋮ On the relation between context and sequence unification ⋮ The hardness of solving simple word equations ⋮ On PSPACE generation of a solution set of a word equation and its applications ⋮ On the complexity of computation maximal exponent of periodicity of word equations and expressible relations (note) ⋮ The existential theory of equations with rational constraints in free groups is PSPACE-complete ⋮ Solvability of context equations with two context variables is decidable ⋮ \(\forall \exists^{5}\)-equational theory of context unification is undecidable
This page was built for publication: Complexity of Makanin's algorithm
