Solving one-variable equations in free groups

Dimitri Bormotov, Robert Gilman, Alexei Myasnikov

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

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 languageEnglish
Pages (from-to)317-330
Number of pages14
JournalJournal of Group Theory
Volume12
Issue number2
DOIs
StatePublished - Mar 2009

Fingerprint

Dive into the research topics of 'Solving one-variable equations in free groups'. Together they form a unique fingerprint.

Cite this