Hereditariness conjecture for the Černý bound

Let A\mathcal{A} be a synchronizing automaton, and let σCong(A)\sigma\in\operatorname{Cong}(\mathcal{A}) be a non-trivial congruence, so that the quotient automaton A/σ\mathcal{A}/\sigma is defined. Hereditariness conjecture for the Černý bound. If the Černý conjecture holds for all simple automata—automata whose only congruences are the identity and universal relations—then it holds for all automata in general.

This is posed as a reduction of the Černý conjecture through quotients and congruences: proving the bound for simple automata would suffice to prove it for every automaton. The paper presents it as a main open problem.

Sources & referencesView supporting material

Primary source

Emanuele Rodaro and Riccardo Venturi, “The hereditariness problem for the Černý conjecture”, arXiv:2509.17992 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.