pith. sign in

arxiv: 2509.17992 · v2 · submitted 2025-09-22 · 💻 cs.FL · math.CO

The hereditariness problem for the v{C}ern\'y conjecture

Emanuele Rodaro , Riccardo Venturi This is my paper

Pith reviewed 2026-05-18 14:28 UTC · model grok-4.3

classification 💻 cs.FL math.CO
keywords Černý conjecturereset automatalifting problemGalois connectiontransition monoidsynchronizing automatacongruencesideals
0
0 comments X

The pith

It suffices to check the Černý conjecture only on radical, simple, and quasi-simple reset automata to resolve the lifting problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the lifting problem for the Černý conjecture reduces to verifying the conjecture on three specific subclasses of reset automata: radical, simple, and quasi-simple. A sympathetic reader would care because this reduction narrows an open general question about whether synchronizing properties transfer from quotients back to the original automata, potentially simplifying the path to a full resolution. The main tool is a Galois connection between the lattices of congruences and ideals in the transition monoid, which also yields concrete structural results such as unique covering ideals over the minimal ideal of constant maps.

Core claim

The authors prove that it is sufficient to verify the Černý conjecture for the three subclasses of radical, simple, and quasi-simple reset automata in order to solve the lifting problem. Their approach relies on a Galois connection between the lattice of congruences and the lattice of ideals of the transition monoid; this connection serves as the primary proof tool and supplies a systematic method for computing the radical ideal. For every simple or quasi-simple automaton the transition monoid possesses a unique ideal covering the minimal ideal of constant maps, and a result of similar flavor holds for radical automata.

What carries the argument

The Galois connection between the lattice of congruences and the lattice of ideals of the transition monoid, which classifies automata into radical, simple, and quasi-simple classes while preserving reset-word information.

If this is right

  • If the conjecture holds for all radical, simple, and quasi-simple reset automata, the lifting problem for the full class is solved.
  • Every simple or quasi-simple automaton has a transition monoid with exactly one ideal covering the minimal ideal of constant maps.
  • Radical automata satisfy an analogous unique-covering-ideal property.
  • The Galois connection yields an algorithmic procedure for computing the radical ideal of any given transition monoid.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Computational searches for counterexamples to the Černý conjecture could now be restricted to the three named classes without loss of generality for the lifting question.
  • The same Galois connection may supply new invariants for deciding membership in the simple or quasi-simple classes directly from the monoid structure.
  • Similar lattice-theoretic reductions might apply to other hereditary properties of synchronizing automata beyond reset-word length bounds.

Load-bearing premise

The Galois connection between the lattice of congruences and the lattice of ideals of the transition monoid preserves the necessary information about reset words and synchronizing properties.

What would settle it

An explicit reset automaton lying outside the radical, simple, and quasi-simple classes for which some quotient satisfies the Černý bound on reset-word length but the original automaton violates it would show that checking the three classes is not sufficient.

Figures

Figures reproduced from arXiv: 2509.17992 by Emanuele Rodaro, Riccardo Venturi.

Figure 1
Figure 1. Figure 1: Venn diagram of the main automata classes considered in the paper. [PITH_FULL_IMAGE:figures/full_fig_p022_1.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper addresses the lifting (hereditariness) problem for the Černý conjecture: it claims that verifying the conjecture on the three subclasses of radical, simple, and quasi-simple reset automata is sufficient to solve the problem in general. The central tool is a Galois connection between the lattice of congruences of an automaton and the lattice of ideals of its transition monoid; this connection is used both to define the subclasses and to establish structural facts, including that every simple or quasi-simple automaton has a unique ideal covering the minimal ideal of constant maps (with an analogous result for radical automata).

Significance. If the reduction is valid, the result would meaningfully narrow the lifting problem to three structurally characterized classes, supplying an order-theoretic framework for computing radical ideals and isolating the 'hard cases' for the Černý bound. The explicit Galois connection and the uniqueness statements about covering ideals constitute concrete technical contributions that could support future algorithmic or classification work on synchronizing automata.

major comments (1)
  1. Abstract, paragraph on the main tool, and the proofs of the structural facts for simple/quasi-simple and radical automata: the Galois connection is shown to control ideal membership and to define the three subclasses, yet no explicit lemma derives an inequality relating the shortest reset-word length in the original automaton to the length in the reduced subclass or quotient. Because the Černý conjecture is a quantitative statement (reset word of length ≤ (n−1)²), the absence of such a length-control transfer means the reduction establishes only that the subclasses are the hard cases, not that a bound verified on them lifts. This is load-bearing for the central sufficiency claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation of the significance of our results and for the constructive comment regarding the quantitative transfer in our reduction. We address the major comment below.

read point-by-point responses

  1. Referee: Abstract, paragraph on the main tool, and the proofs of the structural facts for simple/quasi-simple and radical automata: the Galois connection is shown to control ideal membership and to define the three subclasses, yet no explicit lemma derives an inequality relating the shortest reset-word length in the original automaton to the length in the reduced subclass or quotient. Because the Černý conjecture is a quantitative statement (reset word of length ≤ (n−1)²), the absence of such a length-control transfer means the reduction establishes only that the subclasses are the hard cases, not that a bound verified on them lifts. This is load-bearing for the central sufficiency claim.

    Authors: We agree that an explicit lemma relating reset-word lengths is necessary to rigorously establish the sufficiency claim for the quantitative Černý bound. The Galois connection between congruences and ideals is used to reduce any reset automaton to one in the radical, simple, or quasi-simple classes via covering ideals and quotients, with reset words in the reduced structure corresponding to reset words in the original. However, we acknowledge that this correspondence was not isolated as a standalone lemma deriving the required length inequality. In the revised manuscript we will insert a new lemma (immediately following the structural facts in Section 4) that explicitly states: if a reset word of length at most (k−1)² exists in the reduced automaton on k states, then a reset word of length at most (n−1)² exists in the original automaton on n states, with the additive term controlled by the size of the congruence classes and the rank of the covering ideal. This addition will make the lifting of the bound fully transparent while leaving all existing proofs and results unchanged. revision: yes

Circularity Check

0 steps flagged

No significant circularity; Galois connection is independent structural tool

full rationale

The paper constructs a Galois connection between the lattice of congruences of the automaton and the lattice of ideals of its transition monoid as a primary mathematical device. This connection is used to define the radical, simple, and quasi-simple subclasses and to establish that each such automaton has a unique ideal covering the minimal ideal of constant maps. The central claim—that verifying the Černý conjecture on these three subclasses suffices to solve the lifting problem—follows from order-theoretic properties and structural facts derived from the connection, without presupposing the conjecture itself, without fitting parameters to data, and without load-bearing self-citations that encode the target statement. The derivation remains self-contained against external automata-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence and properties of a Galois connection between congruence and ideal lattices together with the standard definitions of radical, simple, and quasi-simple automata; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption A Galois connection exists between the lattice of congruences and the lattice of ideals of the transition monoid for reset automata.
    This connection is invoked as the main tool for establishing the reduction and for deriving structural properties of the three subclasses.

pith-pipeline@v0.9.0 · 5697 in / 1316 out tokens · 48051 ms · 2026-05-18T14:28:58.874065+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    Representation Theory of Finite Semi- groups,SemigroupRadicalsandFormalLanguageTheory

    J. Almeida, S. Margolis, B. Steinberg, and M. V. Volkov. “Representation Theory of Finite Semi- groups,SemigroupRadicalsandFormalLanguageTheory”.In:Transactions of the American Math- ematical Society361.3 (2009), pp. 1429–1461.issn: 00029947

    work page 2009

  2. [2]

    Semisimple Synchronizing Automata and the Wedderburn-Artin The- ory

    J. Almeida and E. Rodaro. “Semisimple Synchronizing Automata and the Wedderburn-Artin The- ory”. In:International Journal of Foundations of Computer Science27.02 (2016), pp. 127–145.doi: 10.1142/S0129054116400037. 22

    work page doi:10.1142/s0129054116400037 2016

  3. [3]

    Primitive groups, graph endo- morphisms and synchronization

    J. Araújo, W. Bentz, P. J. Cameron, G. Royle, and A. Schaefer. “Primitive groups, graph endo- morphisms and synchronization”. In:Proceedings of the London Mathematical Society113.6 (2016), pp. 829–867.doi:https://doi.org/10.1112/plms/pdw040

    work page doi:10.1112/plms/pdw040 2016

  4. [4]

    Synchronizing groups and automata

    F. Arnold and B. Steinberg. “Synchronizing groups and automata”. In:Theoretical Computer Sci- ence359.1 (2006), pp. 101–110.issn: 0304-3975.doi:https://doi.org/10.1016/j.tcs.2006. 02.003

    work page doi:10.1016/j.tcs.2006 2006

  5. [5]

    Aquadraticupperboundonthesizeofasynchronizing word in one-cluster automata

    M.-P.Béal,M.V.Berlinkov,andD.Perrin.“Aquadraticupperboundonthesizeofasynchronizing word in one-cluster automata”. In:International Journal of Foundations of Computer Science22.02 (2011), pp. 277–288.doi:10.1142/S0129054111008039

    work page doi:10.1142/s0129054111008039 2011

  6. [6]

    Unambiguously coded shifts

    M.-P. Béal, D. Perrin, and A. Restivo. “Unambiguously coded shifts”. In:European Journal of Combinatorics119 (2024). Dedicated to the memory of Pierre Rosenstiehl, p. 103812.issn: 0195- 6698.doi:https://doi.org/10.1016/j.ejc.2023.103812

    work page doi:10.1016/j.ejc.2023.103812 2024

  7. [7]

    Synchronizing Times fork-sets in Automata

    N. Behague and R. Johnson. “Synchronizing Times fork-sets in Automata”. In:The Electronic Journal of Combinatorics29 (2022).doi:10.37236/9819

    work page doi:10.37236/9819 2022

  8. [8]

    Poznámka k homogénnym experimentom s konečnými automatmi

    J. Černý. “Poznámka k homogénnym experimentom s konečnými automatmi”. slo. In:Matematicko- fyzikálny časopis14.3 (1964), pp. 208–216

    work page 1964

  9. [9]

    The Černý Conjecture and 1-Contracting Automata

    H. Don. “The Černý Conjecture and 1-Contracting Automata”. In:Electron. J. Comb.23 (2015), p. 3

    work page 2015

  10. [10]

    Sur les automates circulaires et la conjecture de Černý

    L. Dubuc. “Sur les automates circulaires et la conjecture de Černý”. In:RAIRO-Theor. Inf. Appl. 32.1-3 (1998), pp. 21–34.doi:10.1051/ita/1998321-300211

    work page doi:10.1051/ita/1998321-300211 1998

  11. [11]

    Reset Sequences for Monotonic Automata

    D. Eppstein. “Reset Sequences for Monotonic Automata”. In:SIAM Journal on Computing19.3 (1990), pp. 500–510.doi:10.1137/0219033

    work page doi:10.1137/0219033 1990

  12. [12]

    A Primer on Galois Connections

    M. Erné, J. Koslowski, A. Melton, and G. E. Strecker. “A Primer on Galois Connections”. In: Annals of the New York Academy of Sciences704.1 (1993), pp. 103–125.doi:https://doi.org/ 10.1111/j.1749-6632.1993.tb52513.x

    work page doi:10.1111/j.1749-6632.1993.tb52513.x 1993

  13. [13]

    An Extremal Problem for two Families of Sets

    P. Frankl. “An Extremal Problem for two Families of Sets”. In:European Journal of Combinatorics 3.2 (1982), pp. 125–127.issn: 0195-6698.doi:https : / / doi . org / 10 . 1016 / S0195 - 6698(82 ) 80025-5

    work page 1982

  14. [14]

    J. E. Hopcroft, J. D. Ullman, and R. Motwani.Introduction to automata theory, languages, and computation.English. 2nd ed. Reading, MA: Addison-Wesley, 2001.isbn: 0-201-44124-1

    work page 2001

  15. [15]

    Maggiore,Gravitational Waves

    J.MHowie.Fundamentals of Semigroup Theory.OxfordUniversityPress,Dec.1995.isbn:9780198511946. doi:10.1093/oso/9780198511946.001.0001

    work page doi:10.1093/oso/9780198511946.001.0001 1995

  16. [16]

    Synchronizing finite automata on Eulerian digraphs

    J. Kari. “Synchronizing finite automata on Eulerian digraphs”. In:Theoretical Computer Science 295.1 (2003). Mathematical Foundations of Computer Science, pp. 223–232.issn: 0304-3975.doi: https://doi.org/10.1016/S0304-3975(02)00405-X

    work page doi:10.1016/s0304-3975(02)00405-x 2003

  17. [17]

    Černý’s conjecture and the road colouring problem

    J. Kari and M. V. Volkov. “Černý’s conjecture and the road colouring problem”. English. In: Handbook of automata theory. Volume I. Theoretical foundations. Berlin: European Mathematical Society (EMS), 2021, pp. 525–565.isbn: 978-3-98547-002-0; 978-3-98547-006-8; 978-3-98547-506-3. doi:10.4171/Automata-1/15

    work page doi:10.4171/automata-1/15 2021

  18. [18]

    T. Y. Lam.A first course in noncommutative rings. English. Vol. 131. Grad. Texts Math. New York etc.: Springer-Verlag, 1991.isbn: 0-387-97523-3

    work page 1991

  19. [19]

    On two Combinatorial Problems Arising from Automata Theory

    J. E. Pin. “On two Combinatorial Problems Arising from Automata Theory”. In:Combinatorial Mathematics. Ed. by C. Berge, D. Bresson, P. Camion, J.F. Maurras, and F. Sterboul. Vol. 75. North-Holland Mathematics Studies. North-Holland, 1983, pp. 535–548.doi:https://doi.org/ 10.1016/S0304-0208(08)73432-7

    work page doi:10.1016/s0304-0208(08)73432-7 1983

  20. [20]

    Strongly connected synchronizing automata and the language of minimal reset words

    E. Rodaro. “Strongly connected synchronizing automata and the language of minimal reset words”. English. In:Adv. Appl. Math.99 (2018), pp. 158–173.issn: 0196-8858.doi:10.1016/j.aam.2018. 04.006

    work page doi:10.1016/j.aam.2018 2018

  21. [21]

    A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number

    E. Rodaro. “A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number”. English. In:J. Algebr. Comb.50.3 (2019), pp. 237–253.issn: 0925-9899.doi:10.1007/s10801-018-0851-1

    work page doi:10.1007/s10801-018-0851-1 2019

  22. [22]

    Primitive and irreducible automata

    I. K. Rystsov. “Primitive and irreducible automata”. English. In:Cybern. Syst. Anal.51.4 (2015), pp. 506–513.issn: 1060-0396.doi:10.1007/s10559-015-9742-9. 23

    work page doi:10.1007/s10559-015-9742-9 2015

  23. [23]

    An improvement to a recent upper bound for synchronizing words of finite automata

    Y. Shitov. “An improvement to a recent upper bound for synchronizing words of finite automata”. English. In:J. Autom. Lang. Comb.24.2-4 (2019), pp. 367–373.issn: 1430-189X.doi:10.25596/ jalc-2019-367

    work page 2019

  24. [24]

    A theory of transformation monoids: combinatorics and representation theory

    B. Steinberg. “A theory of transformation monoids: combinatorics and representation theory”. English. In:Electron. J. Comb.17.1 (2010), research paper r164, 56.issn: 1077-8926

    work page 2010

  25. [25]

    The Černý conjecture for one-cluster automata with prime length cycle

    B. Steinberg. “The Černý conjecture for one-cluster automata with prime length cycle”. English. In:Theor. Comput. Sci.412.39 (2011), pp. 5487–5491.issn: 0304-3975.doi:10.1016 /j .tcs . 2011.06.012

    work page 2011

  26. [26]

    Improving the upper bound on the length of the shortest reset word

    M. Szykuła. “Improving the upper bound on the length of the shortest reset word”. English. In: 35th symposium on theoretical aspects of computer science, STACS 2018, Caen, France, February 28 – March 3, 2018. Id/No 56. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik, 2018, p. 13.isbn: 978-3-95977-062-0.doi:10.4230/LIPIcs.STACS.2018.56

    work page doi:10.4230/lipics.stacs.2018.56 2018

  27. [27]

    TheČernýconjectureforaperiodicautomata

    A.N.Trahtman. “TheČernýconjectureforaperiodicautomata”. English.In:Discrete Math. Theor. Comput. Sci.9.2 (2007), pp. 3–10.issn: 1365-8050

    work page 2007

  28. [28]

    Theroadcoloringproblem

    A.N.Trahtman.“Theroadcoloringproblem”.In:Israel Journal of Mathematics172(2009),pp.51– 60.issn: 1565-8511.doi:10.1007/s11856-009-0062-5

    work page doi:10.1007/s11856-009-0062-5 2009

  29. [29]

    Synchronizing automata preserving a chain of partial orders

    M. V. Volkov. “Synchronizing automata preserving a chain of partial orders”. English. In:Imple- mentation and application of automata. 12th international conference, CIAA 2007, Prague, Czech Republic, July 16–18, 2007. Revised selected papers. Berlin: Springer, 2007, pp. 27–37.isbn: 978- 3-540-76335-2.doi:10.1007/978-3-540-76336-9_5

    work page doi:10.1007/978-3-540-76336-9_5 2007

  30. [30]

    Synchronizing automata and the Černý conjecture

    M. V. Volkov. “Synchronizing automata and the Černý conjecture”. English. In:Language and automata theory and applications. Second international conference, LATA 2008, Tarragona, Spain, March 13–19, 2008. Revised papers. Berlin: Springer, 2008, pp. 11–27.isbn: 978-3-540-88281-7.doi: 10.1007/978-3-540-88282-4_4

    work page doi:10.1007/978-3-540-88282-4_4 2008

  31. [31]

    Synchronization of finite automata

    M. V. Volkov. “Synchronization of finite automata”. English. In:Russ. Math. Surv.77.5 (2022), pp. 819–891.issn: 0036-0279.doi:10.4213/rm10005e

    work page doi:10.4213/rm10005e 2022

  32. [32]

    Synchronization of primitive automata

    M. V. Volkov. “Synchronization of primitive automata”. English. In:RAIRO, Theor. Inform. Appl. 58 (2024). Id/No 3, p. 7.issn: 0988-3754.doi:10.1051/ita/2024003

    work page doi:10.1051/ita/2024003 2024

  33. [33]

    M. V. Volkov.List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata. 2025. arXiv:2508.15655 [cs.FL].url:https://arxiv.org/abs/2508.15655. 24

    work page arXiv 2025