4 papers
Completely Reachable Road Coloring
Mikhail V. Volkov, Yinfeng Zhu
We characterize the digraphs that admit an edge labeling by letters from a finite alphabet such that the resulting labeled digraph is a completely reachable automaton. This class o…
The Černý Conjecture for One-Cluster Automata via Annular Spectral Descent
Yinfeng Zhu
We prove the Černý conjecture for synchronizing one-cluster automata. More precisely, let a synchronizing automaton with state set , , have a letter whose functional…
A quadratic upper bound on the reset thresholds of synchronizing automata containing a transitive permutation group
Yinfeng Zhu
For any synchronizing -state deterministic automaton, Černý conjectures the existence of a synchronizing word of length at most . We prove that there exists a synchroni…
Around Don's conjecture for binary completely reachable automata
Yinfeng Zhu
A word is called a reaching word of a subset of states in a deterministic finite automaton (DFA) if is the image of under the action of . A DFA is called complet…