Cerny type automata and rank conjecture

Abstract

The aim of this paper is to prove the Černý conjecture and the rank conjecture for Černý type automata and monoids. A transformation monoid is said to be Černý type if it is generated by a simple idempotent and a regular group of permutations. We prove Černý conjecture for the Černý type synchronizing automata and the rank conjecture for the Černý type transformation monoids. In particular, we obtain the tight bound for the reset threshold of Černý type synchronizing monoids.