Article ID Journal Published Year Pages File Type
9657748 Theoretical Computer Science 2005 8 Pages PDF
Abstract
Although Makanin proved the problem of satisfiability of word equations to be decidable, the general structure of solutions is difficult to describe. In particular, Hmelevskii proved that the set of solutions of xyz=zvx cannot be described using only finitely many parameters, contrary to the case of equations in three unknowns. In this paper we give a short, elementary proof of Hmelevskii's result.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,