Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2013
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1304.5774 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- We prove that a random automaton with $n$ states and any fixed non-singleton alphabet is synchronizing with high probability (modulo an unpublished result about unique highest trees of random graphs). Moreover, we also prove that the convergence rate is exactly $1-Θ(\frac{1}{n})$ as conjectured by [Cameron, 2011] for the most interesting binary alphabet case. Finally, we present a deterministic algorithm which decides whether a given random automaton is synchronizing in linear in $n$ expected time and prove that it is optimal.