Lemme d'itération de Bader et Moura

Modèle:Article général 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,\dots ,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,\dots ,n\}$ de positions contenant $N$ éléments. De même, un choix de positions exclues est un autre sous-ensemble de $\{1,2,\dots ,n\}$. Avec ces définitions, le lemme s'énonce comme suit :

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

Exemple d'application

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

$L=b^{*}\cup a{a}^{+}{b}^{*}\cup \{a{b}^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 $a{b}^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

• Modèle:Chapitre
• Modèle:Article

Articles connexes

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