The synchronizing probability function for primitive sets of matrices

Catalano, Costanza;Jungers, Raphaël
(2020) International Journal of Foundations of Computer Science — Vol. 31, n° 06, p. 777-803 (2020)

Files

Thesynchronizing.pdf
  • Open Access
  • Adobe PDF
  • 627.05 KB
Download

Details

Authors
  • Catalano, CostanzaGran Sasso Science Institute, Viale Francesco Crispi 7, L’Aquila, Italy
    Author
  • Jungers, RaphaëlUCLouvain
    Author
Abstract
Motivated by recent results relating synchronizing automata 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 report numerical results and supported by them we state a conjecture that, if true, would imply an upper bound of n ( n − 1) on the reset threshold of a certain class of automata.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Catalano, C., & Jungers, R. (2020). The synchronizing probability function for primitive sets of matrices. International Journal of Foundations of Computer Science, 31(06), 777-803. https://doi.org/10.1142/S0129054120410051 (Original work published 2020)