arXiv Open Access 2014

Synchronizing automata with random inputs

Vladimir V. Gusev

Lihat Sumber

Abstrak

We study the problem of synchronization of automata with random inputs. We present a series of automata such that the expected number of steps until synchronization is exponential in the number of states. At the same time, we show that the expected number of letters to synchronize any pair of the famous Cerny automata is at most cubic in the number of states.

Topik & Kata Kunci

cs.FL

Penulis (1)

Vladimir V. Gusev

Format Sitasi

APA MLA BibTeX

Gusev, V.V. (2014). Synchronizing automata with random inputs. https://arxiv.org/abs/1404.6731

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2014
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓