论文标题
Cerny-Starke的猜想是XX世纪的六十年代
Cerny-Starke conjecture from the sixties of XX century
论文作者
论文摘要
确定性有限自动机（DFA）的基础图$γ$的边缘上的单词$ s $，如果$ s $将所有自动机的所有状态发送到唯一状态，则称为同步。 J.Centy在1964年发现了一个$ n $ state完整的DFA的序列，其长度$（n-1）^2 $的同步单词最小。该假设（如今已被称为černy猜想）声称，$（n-1）^2 $是在每个完整的$ n $ n $ state dfa上的$γ$上的字母上的此单词$σ$的长度上的精确上限。该假设由Starke于1966年提出。在边缘标签字母中引起的单词引起的特殊矩阵的特殊矩阵的代数操作用于证明猜想。证明是基于单词$ u $的长度与矩阵方程$ l_x $生成的空间维度之间的连接，用于同步单词$ s $，以及$ m_U $和$ l_x $的等级之间的关系。下面的重要作用放置了伪反转矩阵的概念，有时可逆。
A word $s$ of letters on edges of underlying graph $Γ$ of deterministic finite automaton (DFA) is called synchronizing if $s$ sends all states of the automaton to a unique state. J. Černy discovered in 1964 a sequence of $n$-state complete DFA possessing a minimal synchronizing word of length $(n-1)^2$. The hypothesis, mostly known today as Černy conjecture, claims that $(n-1)^2$ is a precise upper bound on the length of such a word over alphabet $Σ$ of letters on edges of $Γ$ for every complete $n$-state DFA. The hypothesis was formulated in 1966 by Starke. Algebra with nonstandard operation over special class of matrices induced by words in the alphabet of labels on edges is used to prove the conjecture. The proof is based on the connection between length of words $u$ and dimension of the space generated by solution $L_x$ of matrix equation $M_uL_x=M_s$ for synchronizing word $s$, as well as on relation between ranks of $M_u$ and $L_x$. Important role below placed the notion of pseudo inverseL matrix, sometimes reversible.
