The Synchronizing Probability Function for Primitive Sets of Matrices

Autor:	Catalano, Costanza, Jungers, Raphaël M.
Rok vydání:	2018
Předmět:	Computer Science - Formal Languages and Automata Theory Computer Science - Discrete Mathematics 15B48 05C57 90C05 F.1.1 G.2.1 G.1.6
Druh dokumentu:	Working Paper
Popis:	Motivated by recent results relating synchronizing DFAs and primitive sets, we tackle the synchronization process and the related longstanding \v{C}ern\'{y} 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. Comment: 24 pages, 9 figures. Submitted to DLT 2018 Special Issue
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1805.06685 Zobrazit plný text záznamu View this record from Arxiv