论文标题
行单矩阵和černy的猜想，简短的证明
Row monomial matrices and Černy conjecture, short proof
论文作者
论文摘要
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.这些矩阵在上述操作方面产生了一个空间。 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. Č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 Černy conjecture, claims that (n-1)(n-1) is also precise upper bound on the length of such a word for a complete DFA.该假设由Starke于1966年提出。这个问题促使了大量的调查和概括。 We present the proof of the Černy-Starke conjecture: the deterministic complete n-state synchronizing automaton has synchronizing word of length at most (n-1)(n-1).空间维度和单词长度之间的证明连接在自动机的下图中的边路路径上。
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. Č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 Č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 Č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.
