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^[1]. Le lemme n'a pas eu autant de retentissement que le lemme d'Ogden par exemple^[2].

Formulation

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

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}$.

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

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}$.

Exemple d'application

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

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

Pour le lemme de Bader et Moura, on exclut la première position d’un mot ${\displaystyle ab^{p}}$ de ${\displaystyle L}$ et on distingue les autres. Le facteur ${\displaystyle uv}$ est alors formé uniquement de lettres ${\displaystyle 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^[4] 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.

Notes et références

1. Bader et Moura 1982.
2. Berstel et Boasson 1990.
3. Cet énoncé, tel que donné dans Berstel et Boasson 1990, est légèrement plus précis que l'énoncé original. Il est qualifié de « version forte » dans le livre de Dömösi et Ito 2014.
4. Pál Dömösi et Masami Ito, Context-free languages and primitive words, World Scientific Publishing, 2014, 520 p. (ISBN 978-981-4271-66-0, OCLC 897020798, présentation en ligne)

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