On randomized generation of slowly synchronizing automata
(2018) 43rd International Symposium on Mathematical Foundations of Computer Science — Location: Liverpool(UK) (27.August.2018)
Files
180506723.pdf
Closed Access - Adobe PDF
- 756.66 KB
Details
- Authors
- Abstract
- Motivated by the randomized generation of slowly synchronizing automata, we study automata made of permutation letters and a merging letter of rank n−1. We present a constructive randomized procedure to generate synchronizing automata of that kind with (potentially) large alphabet size based on recent results on \textit{primitive} sets of matrices. We report numerical results showing that our algorithm finds automata with much larger reset threshold than a mere uniform random generation and we present new families of automata with reset threshold of Ω(n2/4). We finally report theoretical results on randomized generation of primitive sets of matrices: a set of permutation matrices with a 0 entry changed into a 1 is primitive and has exponent of O(nlogn) with high probability in case of uniform random distribution and the same holds for a random set of binary matrices where each entry is set, independently, equal to 1 with probability p and equal to 0 with probability 1−p, when np−logn→∞ as n→∞.
- Affiliations
Citations
Catalano, C., & Jungers, R. (2018). On randomized generation of slowly synchronizing automata. 43rd International Symposium on Mathematical Foundations of Computer Science, Liverpool(UK). https://hdl.handle.net/2078.5/227701