2025/09/22 by Rodaro, Emanuele, Venturi, Riccardo
#05E99 #06A15 #16D60 #20M30 #20M35 #68Q45 #68Q70 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2509.17992
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 A, the transition monoid M(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.