文章基本信息

标题：Fast Synchronization of Random Automata
本地全文：下载
作者：Cyril Nicaud
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：60
页码：43:1-43:12
DOI：10.4230/LIPIcs.APPROX-RANDOM.2016.43
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：A synchronizing word for an automaton is a word that brings that automaton into one and the same state, regardless of the starting position. Cerny conjectured in 1964 that if a $n$-state deterministic automaton has a synchronizing word, then it has a synchronizing word of length at most (n-1)^2. Berlinkov recently made a breakthrough in the probabilistic analysis of synchronization: he proved that, for the uniform distribution on deterministic automata with n states, an automaton admits a synchronizing word with high probability. In this article, we are interested in the typical length of the smallest synchronizing word, when such a word exists: we prove that a random automaton admits a synchronizing word of length O(n log^{3}n) with high probability. As a consequence, this proves that most automata satisfy the Cerny conjecture.
关键词：random automata; synchronization; the Čern{\'y