Hereditariness conjecture for the Černý bound
Hereditariness conjecture for the Černý bound
Let be a synchronizing automaton, and let be a non-trivial congruence, so that the quotient automaton 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.