论文标题
完全可达到的自动机：二次决策算法和达到阈值的二次上限
Completely reachable automata: a quadratic decision algorithm and a quadratic upper bound on the reaching threshold
论文作者
论文摘要
如果每个非空的子集的每个非公平子集的每个非公平子集都是应用于$ Q $的单词的动作的图像，则具有一组状态的完整确定性有限（SEMI）自动机（DFA）是$ q $。特别是与同步自动机有关，完全可以达到自动机的概念。该类包含čern{歧}自动机，并涵盖了几个区别的子类。该概念是由Bondar和Volkov（2016）引入的，他们还提出了有关确定自动机是否完全可以达到的复杂性的问题。我们开发了一个解决此问题的算法，该算法以$ {\ Mathcal {o}（|σ| \ cdot n^2）} $时间和$ \ Mathcal {o}（| = | \ cdot n）$ space，其中$ n = | q |是$ | $ | $ | =是neput apput apput Alplaf。在第二部分中，我们证明了这类自动机的一个薄弱的猜想：$ s \ subseteq q $的非空s子集可以达到$ 2N（n- | s |） - n \ cdot h_ {n- | s | s |} $，其中$ h_i $ h_i $ h_i is $ h_i is是$ i $ i $ i $ -th harmorical norkon。这意味着对于完全可触及的自动机的类别的最短同步单词（重置阈值）的长度上，$ n $中的二次上限，并概括了为其子类得出的早期上限。
A complete deterministic finite (semi)automaton (DFA) with a set of states $Q$ is \emph{completely reachable} if every nonempty subset of $Q$ is the image of the action of some word applied to $Q$. The concept of completely reachable automata appeared, in particular, in connection with synchronizing automata; the class contains the Čern{ý} automata and covers several distinguished subclasses. The notion was introduced by Bondar and Volkov (2016), who also raised the question about the complexity of deciding if an automaton is completely reachable. We develop an algorithm solving this problem, which works in ${\mathcal{O}(|Σ|\cdot n^2)}$ time and $\mathcal{O}(|Σ|\cdot n)$ space, where $n=|Q|$ is the number of states and $|Σ|$ is the size of the input alphabet. In the second part, we prove a weak Don's conjecture for this class of automata: a nonempty subset of states $S \subseteq Q$ is reachable with a word of length at most $2n(n-|S|) - n \cdot H_{n-|S|}$, where $H_i$ is the $i$-th harmonic number. This implies a quadratic upper bound in $n$ on the length of the shortest synchronizing words (reset threshold) for the class of completely reachable automata and generalizes earlier upper bounds derived for its subclasses.
