2026/07/13 by Mikhail V. Volkov, Yinfeng Zhu · 1 voice
#cs.FL #cs.CC
We determine which digraphs admit an edge labeling by letters from a finite alphabet such that the resulting labeled digraph is a completely reachable automaton. Such digraphs are recognizable in polynomial time; however, the problem becomes NP-complete when the size of the label alphabet is fixed. We also classify the digraphs for which every edge labeling results in a completely reachable automaton.