The class of row monomial matrices (one unit and rest zeros in every row) with some non-standard operations of summation and usual multiplication is our main object. These matrices generate a space with respect to the mentioned operations. A word w of letters on edges of underlying graph of deterministic finite automaton (DFA) is called synchronizing if w sends all states of the automaton to a unique state J. \v{C}erny discovered in 1964 a sequence of n-state complete DFA possessing a minimal synchronizing word of length (n-1)(n-1). The hypothesis, well known today as the \v{C}erny conjecture, claims that (n-1)(n-1) is also precise upper bound on the length of such a word for a complete DFA. The hypothesis was formulated in 1966 by Starke. The problem has motivated great and constantly growing number of investigations and generalizations. We present the proof of the \v{C}erny-Starke conjecture: the deterministic complete n-state synchronizing automaton has synchronizing word of length at most (n-1)(n-1). The proof used connection between dimension of the space and the length of words on paths of edges in underlying graph of automaton.
翻译:单体矩阵( 单体矩阵和每行零位和零位) 类别, 具有某些非标准的总和和和通常乘法操作, 是我们的主要对象。 这些矩阵生成了与上述操作有关的空间。 在确定性自定义自动图( DFA) 底图边缘的字母值是同步的。 如果将自动图的所有状态发送到一个独特的状态J.\v{C}}erny 发现1964年的N- state 完整的 DFA序列, 具有最小同步的长度( n-1( n-1) ) 。 假设, 现今又被称为\v{C} erny 推测, 声称( n-1) 也精确地将这种单词的长度与完整的 DFA 。 假设是1966年 Starke 制定的。 问题促使大量且不断增长的调查和概括。 我们展示了N- v{C} Stake 直观信号: 确定性全正态同步的 n- sn- 同步化同步化的自动直径连接到最长的磁度路径的磁度 。