2018/05/17 by Costanza Catalano, Raphaël M. Jungers, Catalano, Costanza +1
Computer Science · #05C57 #15B48 #90C05 #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #F.1.1 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #G.1.6 #G.2.1 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1805.06685
openalex publication_date 2018/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Motivated by recent results relating synchronizing DFAs and primitive sets, we tackle the synchronization process and the related longstanding Černý conjecture by studying the primitivity phenomenon for sets of nonnegative matrices having neither zero-rows nor zero-columns. We formulate the primitivity process in the setting of a two-player probabilistic game and we make use of convex optimization techniques to describe its behavior. We develop a tool for approximating and upper bounding the exponent of any primitive set and supported by numerical results we state a conjecture that, if true, would imply a quadratic upper bound on the reset threshold of a new class of automata.