The averaging trick and the Cerny conjecture

2009/10/02 by Benjamin Steinberg, Steinberg, Benjamin · 1 citation
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic, programming, and type systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0910.0410

openalex publication_date 2009/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The results of several papers concerning the Černý conjecture are deduced as consequences of a simple idea that I call the averaging trick. This idea is implicitly used in the literature, but no attempt was made to formalize the proof scheme axiomatically. Instead, authors axiomatized classes of automata to which it applies.

Cited by

• List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata

Related

• The Cerny Conjecture
• The Černý conjecture for small automata: experimental report
• List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata
• Cerny type automata and rank conjecture
• On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata