Quadratic equations in free groups and free monoids

Abstract

We consider word equations over a free monoid or group where every variable occurs at most twice, also called quadratic equations. First, we recount some previously established facts about quadratic equations. We then present the classic solution algorithm for quadratic equations over free monoids based on Nielsen transformations. Next, we prove a theorem that is in some ways analogous to the Pumping Lemma for regular languages: If a quadratic equation permits infinitely many solutions, this already implies the existence of solutions with arbitrarily high exponent of periodicity; this statement is proven both for free monoids and free groups. Finally, we present an algorithm which computes the exponent of periodicity for general equations over free monoids.