Algebraic synchronization criterion and computing reset words

详细信息    查看全文

• 作者：Mikhail V. Berlinkov^a ; ^{berlm@mail.ru" class="auth_mail" title="E-mail the corresponding author} ; Marek Szykuła ; ^b ; ^{msz@cs.uni.wroc.pl" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Černý ; conjecture ; Huffman code ; Prefix code ; Random automaton ; Reset word ; Synchronizing automaton
• 刊名：Information Sciences
• 出版年：2016
• 出版时间：10 November 2016
• 年：2016
• 卷：369
• 期：Complete
• 页码：718-730
• 全文大小：625 K

文摘

We refine a uniform algebraic approach for deriving upper bounds on reset thresholds of synchronizing automata. We express the condition that an automaton is synchronizing in terms of linear algebra, and obtain new upper bounds for automata with a short word of small rank. The results are applied to make several improvements in the area.

In particular, we improve the upper bound for reset thresholds of finite prefix codes (Huffman codes): we show that an n-state synchronizing decoder has a reset word of length at most O(nlog³n). In addition to that, we prove that the expected reset threshold of a uniformly random synchronizing binary n-state decoder is at most O(nlog n). We prove the Černý conjecture for n  -state automata with a letter of rank $\le \sqrt[3]{6n-6}$. In another corollary, we show that the probability that the Černý conjecture does not hold for a random synchronizing binary automaton is exponentially small in terms of the number of states, and that the expected value of the reset threshold is at most n3/2+o(1)$n^{3/2+o\left(1\right)}$.

Moreover, all of our bounds are constructible. We present suitable polynomial algorithms for the task of finding a reset word of length within our bounds.