The hereditariness problem for the Černý conjecture
European Journal of Combinatorics · 2026-07 · 136 · 104388
DOI: 10.1016/j.ejc.2026.104388 ↗Kurz gefasst
Fachartikel in der Zeitschrift European Journal of Combinatorics, 2026-07. Verfasst von Emanuele Rodaro und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 36 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
This paper addresses the lifting problem for the \v{C}ern\'y 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 \v{C}ern\'y 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.
Zitieren
APA
Rodaro, E., & Venturi, R. (2026). The hereditariness problem for the Černý conjecture. European Journal of Combinatorics, 136, 104388. https://doi.org/10.1016/j.ejc.2026.104388
Vancouver
Rodaro E, Venturi R. The hereditariness problem for the Černý conjecture. European Journal of Combinatorics. 2026;136:104388. doi:10.1016/j.ejc.2026.104388
BibTeX
@article{Rodaro2026,
author = {Rodaro, Emanuele and Venturi, Riccardo},
title = {The hereditariness problem for the Černý conjecture},
journal = {European Journal of Combinatorics},
year = {2026},
volume = {136},
pages = {104388},
doi = {10.1016/j.ejc.2026.104388}
}
EUVIMED