Lemme d'itération de Bader et Moura

Lemme de Bader et Moura — Soit ${\displaystyle L}$ un langage algébrique. Il existe un entier ${\displaystyle N}$ tel que pour tout mot ${\displaystyle w}$ de ${\displaystyle L}$, et pour tout choix de ${\displaystyle d}$ positions distinguées et de e position exclues dans ${\displaystyle w}$ avec ${\displaystyle d>N^{1+e}}$, il existe une factorisation ${\displaystyle w=xuyvz}$ telle que :

1. (${\displaystyle x}$ et ${\displaystyle u}$ et ${\displaystyle y}$) ou (${\displaystyle y}$ et ${\displaystyle v}$ et ${\displaystyle z}$) contiennent au moins une position distinguée ;
2. le mot ${\displaystyle uv}$ ne contient pas de position exclue :
3. si ${\displaystyle uyv}$ contient ${\displaystyle r}$ position distingues et ${\displaystyle s}$ positions exclues, alors ${\displaystyle r\leq N^{1+s}}$ ;
4. ${\displaystyle xu^{n}yv^{n}z\in L}$ pour tout ${\displaystyle n\geq 0}$.

Lemme d'Ogden — Soit ${\displaystyle L}$ un langage algébrique. Il existe un entier ${\displaystyle N}$ tel que pour tout mot ${\displaystyle w}$ de ${\displaystyle L}$ de longueur ${\displaystyle |w|\geq N}$, et pour tout choix de ${\displaystyle N}$ positions distinguées dans ${\displaystyle w}$, il existe une factorisation ${\displaystyle w=xuyvz}$ telle que :

1. (${\displaystyle x}$ et ${\displaystyle u}$ et ${\displaystyle y}$) ou (${\displaystyle y}$ et ${\displaystyle v}$ et ${\displaystyle z}$) contiennent au moins une position distinguée ;
2. ${\displaystyle uyv}$ contient au plus ${\displaystyle N}$ positions distinguées ;
3. ${\displaystyle xu^{n}yv^{n}z\in L}$ pour tout ${\displaystyle n\geq 0}$.