LES AUTOMATES CIRCULAIRES BIAISÉS VÉRIFIENT LA CONJECTURE DE CERNY

摘要

An action X x A~+ → X : (x, w) |→ x * w of the free semigroup A~+ over the alphabet A is synchronised by a word w ∈ A~+ if x * w = y * w for all x, y ∈ X. Cerny conjectured that if there is such a w and |X = n, then there is one of length ≤ (n -1)~2. The conjecture remains open, except for particular classes of actions. An action is circular if there is c ∈ A acting as a circular permutation, and biaised if there is b ∈ A with only one x ∈ X such that |x * b~(-1)| ≥ 2. We confirm here Cerny conjecture for biaised circular actions.%Une action X x A~+ → X : (x, w) |→ x * w du semigroupe libre A~+ sur un alphabet A est dit synchronisé par un mot w ∈ A~+ si x * w = y * w pour tous x, y ∈ X. Cerny a conjecturé, que si un tel mot existe, alors il en existe un de longueur |w| ≤ (n- l)~2, où n = |X|. Cette conjecture reste ouverte, sauf pour certaines classes d'actions. Une action est dite circulaire s'il existe c ∈ A agissant comme une permutation circulaire, et biaisée s'il existe b ∈ A tel que |x * b~(-1) | ≥ 2 pour un unique x ∈ X. Nous vérifions ici la conjecture de Cerny pour les actions circulaires biaisées.