Lemme d'itération de Bader et Moura

En informatique théorique, et notamment en théorie des langages, le lemme d'itération de Bader et Moura est un lemme d'itération pour les langages algébriques qui généralise le lemme d'itération d'Ogden. L'extension consiste à introduire, en plus de la notion de position distinguée, la notion de position exclue. La contrainte sur la présence de positions distinguées dans un mot s'enrichit d'une contrainte sur l'absence de positions exclues dans les facteurs itérés. Le lemme a été établi en 1982 par Christopher Bader et Arnaldo Moura. Le lemme n'a pas eu autant de retentissement que le lemme d'Ogden par exemple.

Formulation

Comme pour le lemme d'Ogden, on utilise la notion de position. Étant donné un mot $w=a_{1}a_{2}\cdots a_{n}$, où les $a_{i}$ sont des lettres, on appelle position dans $w$ tout entier de l'ensemble $\{1,2,\ldots ,n\}$. Un choix de positions distinguées ou positions marquées dans $w$ (ceci est la terminologie traditionnelle) est simplement un sous-ensemble $\{1,2,\ldots ,n\}$ de positions contenant $N$ éléments. De même, un choix de positions exclues est un autre sous-ensemble de $\{1,2,\ldots ,n\}$. Avec ces définitions, le lemme s'énonce comme suit :

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

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

Pour mémoire et comparaison, voici l'énoncé du lemme d'Ogden :

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

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

Exemple d'application

Voici un exemple de langage où le lemme peut servir. Sur l’alphabet $A=\{a,b\}$, soit

$L=b^{*}\cup aa^{+}b^{*}\cup \{ab^{p}\mid p\in P\}$, où $P$ est l'ensemble des nombres premiers.

Pour le lemme de Bader et Moura, on exclut la première position d’un mot $ab^{p}$ de $L$ et on distingue les autres. Le facteur $uv$ est alors formé uniquement de lettres $b$.

Le langage des mots primitifs

Dans leur tentative de démontrer que le langage des mots primitifs n'est pas algébriques, Dömösi et Ito constatent que ce langage vérifie les hypothèses du lemme de Bader et Moura pour la constante N=5, et donc qu'il n'aide pas dans leur tentative.

Bibliographie

• Jean Berstel et Luc Boasson, « Context-Free Languages », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Theoretical Computer Science, vol. B : Formal Models and Sematics, Elsevier et MIT Press, 1990 (ISBN 0-444-88074-7), p. 59-102
• (en) Christopher Bader et Arnaldo Moura, « A Generalization of Ogden's Lemma », Journal of the ACM, vol. 29, n^o 2,‎ 1982, p. 404–407 (DOI 10.1145/322307.322315)

Articles connexes

• Lemme d'itération
• Lemme d'Ogden
• Théorie des langages