Abstract
Equations in free groups have become prominent recently in connection with the solution to the well-known Tarski conjecture. Results of Makanin and Rasborov show that solvability of systems of equations is decidable and there is a method for writing down in principle all solutions. However, no practical method is known; the best estimate for the complexity of the decision procedure is P-space. The special case of one-variable equations in free groups has been open for a number of years, although it is known that the solution sets admit simple descriptions. We use cancellation arguments to give a short and direct proof of this result and also to give a practical polynomial-time algorithm for finding solution sets. One-variable equations are the only general subclass of equations in free groups for which such results are known. We improve on previous attempts to use cancellation arguments by employing a new method of reduction motivated by techniques from formal language theory. Our paper is self-contained; we assume only knowedge of basic facts about free groups.
Original language | English |
---|---|
Pages (from-to) | 317-330 |
Number of pages | 14 |
Journal | Journal of Group Theory |
Volume | 12 |
Issue number | 2 |
DOIs | |
State | Published - Mar 2009 |