The hereditariness problem for the Černý conjecture
This addresses a theoretical problem in automata theory for researchers, but it is incremental as it provides partial progress without a complete solution.
The paper tackles the problem of whether the Černý conjecture for quotient automata can be transferred to original automata, showing it suffices to verify the conjecture for three subclasses of reset automata: radical, simple, and quasi-simple.
This paper addresses the lifting problem for the Černý conjecture: namely, whether the validity of the conjecture for a quotient automaton can always be transferred (or "lifted") to the original automaton. Although a complete solution remains open, we show that it is sufficient to verify the Černý conjecture for three specific subclasses of reset automata: radical, simple, and quasi-simple. Our approach relies on establishing a Galois connection between the lattices of congruences and ideals of the transition monoid. This connection not only serves as the main tool in our proofs but also provides a systematic method for computing the radical ideal and for deriving structural insights about these classes. In particular, we show that for every simple or quasi-simple automaton $\mathcal{A}$, the transition monoid $\text{M}(\mathcal{A})$ possesses a unique ideal covering the minimal ideal of constant (reset) maps; a result of similar flavor holds for the class of radical automata.