论文标题
自动机的$ k $ - 集的同步时间
Synchronizing Times for $k$-sets in Automata
论文作者
论文摘要
如果有一个单词将所有状态映射到同一状态，则自动机正在同步。坎尼关于最短这个词长度的猜想可能是自动机理论中最著名的开放问题。我们考虑确定将$ k $状态映射到一个状态的单词的最小长度的密切相关的问题。对于同步自动机，我们在单词的最小长度上提高了上限，该单词的最小长度从$ 0.5N^2 $到$ \ $ \ of 0.19n^2 $。我们进一步将其扩展到了针对4个州和5个州的这样一个词的长度的改进。在非同步自动机的情况下，我们举例说明将$ k $状态发送到单个状态的单词的最小长度可以大至$θ\ left（n^{k-1} \ right）$。
An automaton is synchronizing if there is a word that maps all states onto the same state. Černý's conjecture on the length of the shortest such word is probably the most famous open problem in automata theory. We consider the closely related question of determining the minimum length of a word that maps $k$ states onto a single state. For synchronizing automata, we improve the upper bound on the minimum length of a word that sends some triple to a a single state from $0.5n^2$ to $\approx 0.19n^2$. We further extend this to an improved bound on the length of such a word for 4 states and 5 states. In the case of non-synchronizing automata, we give an example to show that the minimum length of a word that sends $k$ states to a single state can be as large as $Θ\left(n^{k-1}\right)$.
