The hereditariness problem for the Černý conjecture
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910126941667328 |
|---|---|
| author | Rodaro, Emanuele Venturi, Riccardo |
| author_facet | Rodaro, Emanuele Venturi, Riccardo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_17992 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The hereditariness problem for the Černý conjecture Rodaro, Emanuele Venturi, Riccardo Formal Languages and Automata Theory Combinatorics 68Q70, 68Q45, 20M35, 20M30, 06A15, 16D60, 05E99 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. |
| title | The hereditariness problem for the Černý conjecture |
| topic | Formal Languages and Automata Theory Combinatorics 68Q70, 68Q45, 20M35, 20M30, 06A15, 16D60, 05E99 |
| url | https://arxiv.org/abs/2509.17992 |