2014/10/15 by François Gonze, Raphaël M. Jungers, Gonze, François +1
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.1410.4034
openalex publication_date 2014/10/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Cerny's conjecture is a longstanding open problem in automata theory. We study two different concepts, which allow to approach it from a new angle. The first one is the triple rendezvous time, i.e., the length of the shortest word mapping three states onto a single one. The second one is the synchronizing probability function of an automaton, a recently introduced tool which reinterprets the synchronizing phenomenon as a two-player game, and allows to obtain optimal strategies through a Linear Program. Our contribution is twofold. First, by coupling two different novel approaches based on the synchronizing probability function and properties of linear programming, we obtain a new upper bound on the triple rendezvous time. Second, by exhibiting a family of counterexamples, we disprove a conjecture on the growth of the synchronizing probability function. We then suggest natural follow-ups towards Cernys conjecture.