Equations in free semigroups with involution and their relation to equations in free groups.

DOI10.1016/S0304-3975(02)00642-4zbMath1044.68067OpenAlexW2179946231MaRDI QIDQ1401304

Claudio Gutierrez

Publication date: 17 August 2003

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00642-4

zbMATH Keywords

Free group equationFree semigroup equationWord equation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Makanin's algorithm is not primitive recursive
• Equations in free semigroups
• Word unification and transformation of generalized equations
• Satisfiability of word equations with constants is in NEXPTIME
• Satisfiability of equations in free groups is in PSPACE
• Minimal and complete word unification
• ON SYSTEMS OF EQUATIONS IN A FREE GROUP
• Complexity of Makanin's algorithm

This page was built for publication: Equations in free semigroups with involution and their relation to equations in free groups.