Complexity of Makanin's algorithm

DOI10.1145/234533.234543zbMATH Open0882.68073OpenAlexW2054924158WikidataQ128392129 ScholiaQ128392129MaRDI QIDQ4371685FDOQ4371685

Authors: Antoni Kościelski, Leszek Pacholski 

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/

Recommendations

• EXPONENT OF PERIODICITY OF WORD EQUATIONS IN FIXED DIMENSION IS POLYNOMIAL
• On the complexity of computation maximal exponent of periodicity of word equations and expressible relations (note)
• scientific article; zbMATH DE number 1189059

zbMATH Keywords

periodicitydiophantine equationnonnumerical algorithmsword-unification algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Cited In (26)

• Efficient solving of the word equations in one variable
• Title not available (Why is that?)
• On the complexity of computation maximal exponent of periodicity of word equations and expressible relations (note)
• Unification in commutative semigroups
• EXPONENT OF PERIODICITY OF WORD EQUATIONS IN FIXED DIMENSION IS POLYNOMIAL
• \(\forall \exists^{5}\)-equational theory of context unification is undecidable
• Equations in free semigroups with involution and their relation to equations in free groups.
• The hardness of solving simple word equations
• On word equations in one variable
• Monadic simultaneous rigid \(E\)-unification and related problems
• Two-variable word equations
• An analysis of Makanin's algorithm deciding solvability of equations in free groups
• On PSPACE generation of a solution set of a word equation and its applications
• Extending free pregroups with lower bounds
• Solvability of context equations with two context variables is decidable
• Makanin's algorithm is not primitive recursive
• On the relation between context and sequence unification
• On equality up-to constraints over finite trees, context unification, and one-step rewriting
• More than 1700 years of word equations
• Decidability of bounded higher-order unification
• Finding all solutions of equations in free groups and monoids with involution
• Word equations in non-deterministic linear space
• Monadic simultaneous rigid \(E\)-unification
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• Towards Decidability of Conjugacy of Pairs and Triples
• The expressibility of languages and relations by word equations

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)