EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

The hereditariness problem for the Černý conjecture

Emanuele Rodaro, Riccardo Venturi

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →