论文标题
部分自动机的同步
On synchronization of partial automata
论文作者
论文摘要
本文的目的是引入最短同步$ o（d^{\ frac {n} {d}}）$的新构造，其中$ d \ in \ mathbb {n} $，$ n $是该自动机的州数量。此外，我们引入了从任何可同步的DFA或$ n $状态的可同步的PFA的新转换，以仔细同步的PFA $ d \ cdot n $状态，其长度最短$ω（d^{\ frac {n} d}}}}}）$。
A goal of this paper is to introduce the new construction of an automaton with shortest synchronizing word of length $O(d^{\frac{n}{d}})$, where $d \in \mathbb{N}$ and $n$ is the number of states for that automaton. Additionally we introduce new transformation from any synchronizable DFA or carefully synchronizable PFA of $n$ states to carefully synchronizable PFA of $d \cdot n$ states with shortest synchronizing word of length $Ω(d^{\frac{n}{d}})$.
