On the probability of being synchronizable
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2013
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929414181224448 |
|---|---|
| author | Berlinkov, Mikhail V. |
| author_facet | Berlinkov, Mikhail V. |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1304_5774 |
| institution | arXiv |
| publishDate | 2013 |
| record_format | arxiv |
| spellingShingle | On the probability of being synchronizable Berlinkov, Mikhail V. Formal Languages and Automata Theory Discrete Mathematics Combinatorics F.4.3 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. |
| title | On the probability of being synchronizable |
| topic | Formal Languages and Automata Theory Discrete Mathematics Combinatorics F.4.3 |
| url | https://arxiv.org/abs/1304.5774 |