The Černý Conjecture and 1-Contracting Automata

[摘要] A deterministic finite automaton is synchronizing if there exists a word that sends all states of the automaton to the same state. Černý conjectured in 1964 that a synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2

[学科分类] 离散数学和组合数学

[关键词] Deterministic finite automaton;Synchronizing word