The Synchronizing Probability Function for Primitive Sets of Matrices

Catalano, Costanza;Jungers, Raphaël
(2018) DLT 2018 — Location: Tokyo, Japan (10.September.2018)

Files

Catalano-Jungers2018_Chapter_TheSynchronizingProbabilityFun.pdf
  • Closed Access
  • Adobe PDF
  • 493.87 KB
Request a copy

Details

Authors
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. (2018). The Synchronizing Probability Function for Primitive Sets of Matrices. Developments in Language Theory : Lecture Notes in Computer Science, p. 194-205. https://doi.org/10.1007/978-3-319-98654-8_16