Sup 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.