Chapter 9 - Equations in Words

Summary

Introduction

Let us consider two words x, y of the free monoid A^*, satisfying the equality:

By Proposition 1.3.2 of Chapter 1, there exist a word u ∈ A^* and two integers n, p ≥ 0 such that

In this chapter, we will view x and y as the letters of an alphabet Ξ. We will say that xy = yx is an equation in the unknowns Ξ = {x, y} and that the morphism α: Ξ^* → A^* defined by α(x) = uⁿ and α(y) = u^p is a solution of the equation. Observe that all solutions of this particular equation are of this type.

The basic notions on equations are presented in Section 9.1. In Section 9.2, we consider a few equations whose families of solutions admit a finite description, as in the preceding example. Indeed, the family of solutions of Eq. (9.0.1) is entirely described by the unique expression (9.0.2), where u runs over all words and n, p over all positive integers. This idea is formalized in Section 9.3, which introduces the notion of parametrizable equations and where it is recalled that all equations in three unknowns are parametrizable.

Not all equations are parametrizable, however. We are thus led in Section 9.4 to define the rank of an equation, which is the maximum number of the letters occurring in the expression of particular solutions called principal.