Solving Equations in Strings: On Makanin's Algorithm

摘要

We present a further simplification of Makanin's algorithm, still the only known general proceduure for solving string equations. We also give pseudo-code, a thorough analysis of its compelxity, and complete proofs of correctness and termination.