SUR LES AUTOMATES CIRCULAIRES ET LA CONJECTURE DE CERNY

摘要

A reset word takes all states of a finite automaton to a single state. Cerny conjectured that every n-state automaton admitting a reset word admits a short reset word, i.e. one of length at most (n - 1)~2. In this paper, we generalize our earliest result (the proof of the conjecture about biaised circular automata) to all circular automata.%Un mot synchronisant amène tous les états d'un automate fini à un unique état. Cerny a conjecturé que la longueur minimale des mots synchronisants d'un automate à n états est au plus (n - 1)~2. Dans cet article, nous généralisons notre précédent résultat (la confirmation de la conjecture pour les automates circulaires biaises) aux automates circulaires.