On the synchronizing probability function and the triple rendezvous time
(2015) International conference on language and automata theory and applications, LATA — Location: Nice, France (2.March.2015)
Files
document.pdf
Restricted Access - Adobe PDF
- 227.68 KB
Details
- Authors
- Abstract
- We push further a recently proposed approach for studying synchronizing automata and Čerńy’s conjecture, namely, the synchronizing probability function. In this approach, the synchronizing phenomenon is reinterpreted as a Two-Player game, in which the optimal strategies of the players can be obtained through a Linear Program. Our analysis mainly focuses on the concept of triple rendezvous time, the length of the shortest word mapping three states onto a single one. It represents an intermediate step in the synchronizing process, and is a good proxy of its overall length. Our contribution is twofold. First, using the synchronizing probability function and properties of linear programming, we provide a new upper bound on the triple rendezvous time. Second, we disprove a conjecture on the synchronizing probability function by exhibiting a family of counterexamples. We discuss the game theoretic approach and possible further work in the light of our results.
- Affiliations
Citations
Gonze, F., & Jungers, R. (2015). On the synchronizing probability function and the triple rendezvous time. Lecture Notes in Computer Science, 8977, 212-223. https://doi.org/10.1007/978-3-319-15579-1_16 (Original work published 2015)