Cerny type automata and rank conjecture

2025/01/31 by И. К. Рысцов, Rystsov, Igor
Computer Science · #Advanced Algebra and Logic #Coding theory and cryptography #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2501.19166

openalex publication_date 2025/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• Reset thresholds of transformation monoids
• The hereditariness problem for the Černý conjecture
• On the interplay between Babai and Cerny's conjectures
• List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata
• The vCerny Conjecture for aperiodic automata