completely reachable automata 1computational complexity 1digraph labeling 1np-completeness 1road coloring 1
From the 1 of 3 linked papers with an AI index.
3 papers
cs.FL2026
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 functiona…
cs.FL2026
Completely Reachable Road Coloring
Mikhail V. Volkov, Yinfeng Zhu
The paper characterizes directed graphs that can be edge‑labeled by a finite alphabet to produce a completely reachable automaton, provides a polynomial‑time recognition algorithm,…
cs.FL2024
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 synchro…