Résumé : On donne des
résultats partiels sur les conjectures suivantes, issues de la
théorie des automates. La première conjecture est la
conjecture du triangle, due à Perrin et Schützenberger. Soit
A = {a, b} un alphabet à deux lettres, d un entier
positif et soit Bd = {aibaj | 0
≤ i+j ≤ d}. Si X ⊂
Bd est un code, alors |X| ≤ d+1. La seconde
conjecture est due à Cerný et à l'auteur. Soit
A un automate à n états. S'il existe un
mot de rang ≤ k dans A, il en existe un de
longueur ≤ (n-k)2.
Abstract : We present some partial results on the
following conjectures arising from automata theory. The first conjecture is
the triangle conjecture due to Perrin and Schützenberger. Let A =
{a, b} be a two-letter alphabet, d a positive integer and let
Bd = {aibaj | 0 ≤ i+j
≤ d}. If X ⊂ Bd
is a code, then |X| ≤ d+1. The second conjecture is due to
Cerný and the author. Let A be an automaton with
n states. If there exists a word of rank ≤ k in
A, there exists such a word with length ≤
(n-k)2.