On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata
(2016) SIAM Journal on Discrete Mathematics — Vol. 30, n° 2, p. 995-1014 (2016)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- (en) t. Cern´y’s conjecture is a longstanding open problem in autom ˇ ata 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 followups towards Cern´y’s conjecture. ˇ
- Affiliations
Citations
Gonze, F., & Jungers, R. (2016). On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata. SIAM Journal on Discrete Mathematics, 30(2), 995-1014. https://doi.org/10.1137/15M1024603 (Original work published 2016)