completely reachable automata 1computational complexity 1digraph labeling 1np-completeness 1road coloring 1
From the 1 of 6 linked papers with an AI index.
Showing cs.FLShow all
3 papers · 1 filter
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.FL2026★ 1 cited
Adversarial Synchronization
Anton E. Lipin, Mikhail V. Volkov
We study a variant of the synchronization game on finite deterministic automata. In this game, Alice chooses one input letter of an automaton on each of her moves while Bob may…
cs.FL2026★ 1 cited
List of Results on the Äerný Conjecture and Reset Thresholds for Synchronizing Automata
Mikhail V. Volkov
We survey results in the literature that establish the Äerný conjecture for various classes of finite automata. We also list classes for which the conjecture remains open, but a…