betaFeedback

WorksComputer Science

The Černý (1969) conjecture holds for quasi-Eulerian automata of degree one

Abstract

An automaton with nn states is quasi-Eulerian of degree dd if there are positive letter weights summing to one, a set XX of dd exceptional states and a further state ss such that every state outside X∪{s}X\cup\{s\} receives total weight one and every edge that starts in XX ends in X∪{s}X\cup\{s\}. Berlinkov bounded the reset threshold of strongly connected synchronizing ones by 2d(n−d+1)(n−1)2^d(n-d+1)(n-1). We prove that every synchronizing quasi-Eulerian automaton of degree one has a reset word of length at most (n−1)2(n-1)^2, so the Černý (1969) conjecture holds for this family; the Černý automata belong to it and attain the bound. The same bound holds for every synchronizing automaton whose transition matrix, weighted by some positive, possibly irrational, letter weights, has a positive stationary vector that is constant on all states but one; for this family Berlinkov's bound was 2n(n−1)2n(n-1). For synchronizing quasi-Eulerian automata of degree two, the bound holds whenever the automaton is not strongly connected, whenever its two exceptional states form a block of a congruence, and, for binary strongly connected automata, in 4646 of the 4949 configurations (up to renaming) of the edges at the two exceptional states. The key step in degree one is elementary: a shortest word that takes the exceptional state out of a set KK of states that contains it has length at most ∣K∣|K|, and one that takes it into a set KK that does not contain it has length at most n−∣K∣n-|K|.

Introduction

The Černý (1969) conjecture states that if some word maps all nn states of an automaton to one state, then some such word has length at most (n−1)2(n-1)^2. We prove it for the quasi-Eulerian automata of degree one, a family introduced by Berlinkov, and for several families of quasi-Eulerian automata of degree two.

Background

A (complete deterministic) automaton A=(Q,Σ)\mathcal{A}=(Q,\Sigma) has a finite nonempty set QQ of nn states and a finite nonempty alphabet Σ\Sigma; every letter maps QQ to QQ; we write q.bq.b for the image of a state qq under a letter bb, and call q→q.bq \to q.b an edge with label bb. The automaton is synchronizing if some word, a reset word, maps all states to one state; the least length of a reset word is the reset threshold rt⁡(A)\operatorname{rt}(\mathcal{A}). In 1964 Černý [3] described automata CnC_n with nn states, two letters and rt⁡(Cn)=(n−1)2\operatorname{rt}(C_n)=(n-1)^2: on Q={0,…,n−1}Q=\{0,\ldots,n-1\} the letter aa maps 00 to 11 and fixes every other state, and bb maps qq to q+1 mod nq+1 \bmod n (Figure 1, right). He stated the conjecture in a talk in 1969, and it first appeared in print in [4] (see [14 Section 1] and, for its history, [15 Section 3.1]). It is open in general: the best known upper bounds are cubic, from Pin and Frankl’s (n3−n)/6(n^3-n)/6 [9, 5] to the small improvements of Szykuła [12] and Shitov [10]. The conjecture has been proved for many special families of automata; Volkov’s list [16] records them, together with the families for which only a quadratic bound is known. Kari [7] proved rt≤1+(n−2)(n−1)r_t \le1 + (n-2)(n-1) for Eulerian automata (strongly connected, with every state entered by exactly ∣Σ∣|\Sigma| edges), and Steinberg [11] extended this to pseudo-Eulerian automata: strongly connected automata with positive letter weights for which every state receives total weight one. Berlinkov [1, 2] introduced the following generalization.

Figure 1. Left: a witness (E,s,p)(E,s,p) of degree two (Definition 1.1; pp gives the letter weights). Every state of EE other than ss has in-weight one, every edge that starts in the set XX of exceptional states ends in X∪{s}X \cup\{s\}, and edges from EE may enter XX (dotted); only some edges are drawn. Right: the Černý automaton C4C_4 (letter aa solid, letter bb dashed) with the witness of degree one used in Theorem 4.1: x=0x=0, s=1s=1 and E={1,2,3}E=\{1,2,3\}.

Definition 1.1 (Berlinkov [1, 2]; see [16 item D3]). An automaton A=(Q,Σ)\mathcal{A}=(Q,\Sigma) is quasi-Eulerian of degree dd if there are a set E⊆QE\subseteq Q with ∣E∣=n−d|E|=n-d, a state s∈Es\in E and letter weights p=(pb)b∈Σp=(p_b)_{b\in\Sigma} with pb>0p_b>0 and ∑bpb=1\sum_b p_b=1 such that

(a) every edge that starts in X:=Q∖EX:=Q\setminus E ends in X∪{s}X\cup\{s\}, and

(b) every state r∈E∖{s}r\in E\setminus\{s\} has in-weight one: ∑b∈Σpb∣{q∈Q:q.b=r}∣=1\sum_{b\in\Sigma}p_b|\{q\in Q:q.b=r\}|=1.

We call (E,s,p)(E,s,p) a witness, XX its exceptional states, and pp admissible.

The Černý automata are quasi-Eulerian of degree one [1 Section 4], [16 item D3], so (n−1)2(n-1)^2 is the best possible bound for this family (Figure 1). For a strongly connected synchronizing quasi-Eulerian automaton of degree dd, Berlinkov proved rt(A)≤2d(n−d+1)(n−1)r_t(\mathcal{A})\le2^d(n-d+1)(n-1) [2 Theorem 8] (see also [1 Theorem 2]).

Admissible weights pp give the row-stochastic matrix M=∑bpbMbM=\sum_b p_bM_b, where MbM_b is the 0/10/1 transition matrix of the letter bb, and a stationary vector is a nonzero vector α\alpha with αTM=αT\alpha^{\mathsf{T}}M=\alpha^{\mathsf{T}} (Section 2). For a strongly connected automaton it can be taken equal to 1 on EE and positive on the exceptional states (Lemma 5.5). In degree two we write t1,t2t_1,t_2 for its values on the two exceptional states and call the unordered pair {t1,t2}\{t_1,t_2\} the class of the witness. For binary automata (two letters, Σ={a,b}\Sigma=\{a,b\}) of degree two, the configuration of the witness records where the four edges that start at the exceptional states end, and how many edges from EE enter each exceptional state. For a strongly connected binary automaton the class is always computed with the weights (12,12)(\frac{1}{2},\frac{1}{2}), which are then admissible (Lemma 5.7); the configuration of the witness is then one of 49, up to renaming the two exceptional states and the two letters, and its class one of 14 (Lemma 5.8 and Table 1). The two exceptional states form a block of a congruence if every letter maps them to one state or to the pair itself (Proposition 5.6).

Results

The table compares our main results with the best results known before this paper.

Best result before this paperNew result
rt≤2n(n−1)r_t\le2n(n-1) for strongly connected ones [2 Theorem 8]; the Černý conjecture was open for this family [16 item D3].Quasi-Eulerian, degree one: rt≤(n−1)2r_t\le(n-1)^2, attained by CnC_n (Theorem 4.1).
rt≤2n(n−1)r_t\le2n(n-1) [1 Proposition 4].A positive stationary vector that is constant off one state, for some positive (possibly irrational) letter weights: rt≤(n−1)2r_t\le(n-1)^2 (Theorem 3.1).
rt≤4(n−1)2r_t\le4(n-1)^2 for strongly connected ones [2 Theorem 8]; [16 item D3] lists it for the whole family.Degree two, not strongly connected: rt≤(n−1)2r_t\le(n-1)^2 (Theorem 5.1).
rt≤4(n−1)2r_t\le4(n-1)^2 [2 Theorem 8]; (n−1)2(n-1)^2 for all nn only in the class {1,1}\{1,1\}, where the stationary vector is constant (pseudo-Eulerian) [7, 11]; Volkov’s list [16] records no other.Degree two, binary, strongly connected: rt≤(n−1)2r_t\le(n-1)^2 in 46 of the 49 configurations, covering every configuration of 12 of the 14 classes (Theorem 5.9).

Table 1.

  • We prove the Černý (1969) conjecture for quasi-Eulerian automata of degree one (Berlinkov’s family, Definition 1.1): every synchronizing one has rt≤(n−1)2r_t\le(n-1)^2, and the Černý automata attain this bound (Theorem 4.1, proved in Section 4). The best bound before was 2n(n−1)2n(n-1), for strongly connected ones [2]. Strong connectivity is not assumed: if the automaton is not

strongly connected, then either every letter fixes the exceptional state or EE is closed (no edge leaves EE), and in both cases Kari’s argument gives rt≤1+(n−2)(n−1)rt \le1 + (n-2)(n-1).

  • We improve Berlinkov’s bound 2n(n−1)2n(n-1) [1 Proposition 4] to (n−1)2(n-1)^2 for every synchronizing automaton with positive letter weights whose stationary vector is positive and constant on all states but one; the weights need not be rational (Theorem 3.1, proved in § 3). This family contains every strongly connected synchronizing quasi-Eulerian automaton of degree one (by Berlinkov’s observation in the proof of [1 Theorem 2] and Lemma 4.2), and others (Example 3.5).

  • Degree two. We prove rt≤(n−1)2rt \le(n-1)^2 for every synchronizing quasi-Eulerian automaton of degree two that is not strongly connected (Theorem 5.1, proved in § 5.1), for every one whose two exceptional states form a block of a congruence (Proposition 5.6, § 5.3), and for binary strongly connected ones in 46 of the 49 configurations, which include every configuration of 12 of the 14 classes (Theorem 5.9, proved in § 5.4; Figure 2). For the three classes {2,2}\{2,2\}, {2,3}\{2,3\} and {2,4}\{2,4\} and at most six states, the bound follows from the computation of Kisielewicz, Kowalski and Szykuła [8], who verified the Černý conjecture for all binary automata with at most 12 states. For n≥7n \ge7, Corollary 5.15 also gives the bound in the integer classes {2,k}\{2,k\} (kk a positive integer) over every alphabet. The best bound before was Berlinkov’s 4(n−1)24(n-1)^2 for strongly connected ones [2 Theorem 8]; [16 item D3] lists it without that hypothesis.

Comparison of known bounds before and after this paper across classes

Figure 2. Green squares: the bound (n−1)2(n-1)^2 is known for all nn; grey squares with a question mark: it is known only for n≤12n \le12 [8]. The squares are the 49 configurations of Lemma 5.8 (binary strongly connected automata of degree two), in rows by class {t1,t2}\{t_1,t_2\} (Table 1). Left: before this paper, the bound (n−1)2(n-1)^2 was known for all nn only in the class {1,1}\{1,1\}, where the stationary vector is constant [7, 11]; Berlinkov’s bound 4(n−1)24(n-1)^2 [2] holds in all of them. Right: after this paper; each row names the results that give (n−1)2(n-1)^2, and the three grey squares are the configurations excluded in Theorem 5.9.

Recently Zhu Zhu [17] announced a proof of the conjecture for one-cluster automata (some letter has only one cycle; [16 item D1]). This family and the family of Theorem 4.1 are incomparable (Remark 4.4).

Method

All proofs use the extension method: a reset word is built from right to left by enlarging preimages of a set. Kari’s step [7], with letter weights as in Steinberg’s averaging trick [11] and with Berlinkov’s stationary vector α\alpha as the measure of a set [1], finds for a nonempty proper set KK a word ww of at most n−1n-1 letters that raises α\alpha: the preimage Kw−1Kw^{-1} has α(Kw−1)>α(K)\alpha(Kw^{-1}) > \alpha(K). Here α(K)=∑q∈Kαq\alpha(K)=\sum_{q\in K}\alpha_q, and α\alpha is a stationary vector of the weighted transition matrix (Lemma 2.2). When α\alpha is constant off one state xx, a raising word either enlarges the set or moves xx from one side of the set to the other. The key observation is that such moves are short. By the orbit lemma (Lemma 2.3), an elementary bound on shortest paths, a shortest word that moves xx across a set KK has length at most ∣K∣|K| if x∈Kx \in K, and at most n−∣K∣n-|K| if x∉Kx \notin K. Scale α\alpha so that α=1\alpha=1 off xx, and put t=αxt=\alpha_x. When 0<t<20<t<2 and t≠1t\ne1, a raising word never shrinks the set, and it keeps the size only by moving xx across the set; and every word that moves xx across a set changes α\alpha, as set sizes are integers and t−1t-1 is not. So a move of xx and the step that follows it cost at most ∣K∣|K| and n−∣K∣n-|K| letters (in this order if t<1t<1, in the reverse order if t>1t>1), by the orbit lemma, and at most nn together. After a first letter that merges two states, at most n−2n-2 enlargements of at most nn letters each give 1+(n−2)n=(n−1)21+(n-2)n=(n-1)^2. Figure 3 shows these steps for the Černý automaton C4C_4, where every bound is attained.

Extension method on the Černý automaton

Figure 3. The extension method on the Černý automaton C4C_4 of Figure 1 (right), with the exceptional state x=0x = 0 (thick circle). Each box shows a set of states; its members are grey; an arrow labelled cc goes from a set KK to its preimage Kc−1Kc^{-1}. As in Remark 4.3, t=αx<1t = \alpha_x < 1, and each row, read from right to left, spells its word: the merging letter aa, then w0=abbbw_0 = abbb, then w1=abbbw_1 = abbb; the reset word w1w0a=abbb abbb aw_1w_0a = abbb\ abbb\ a has length 1+(n−2)n=9=(4−1)21 + (n - 2)n = 9 = (4 - 1)^2 for n=4n = 4. The braces mark the two bounds of the orbit lemma (Lemma 2.3) used in the proof of Proposition 3.3: in each extension both are attained, so it costs exactly nn letters.

References

  1. [1]M. V. Berlinkov, Synchronizing automata on quasi Eulerian digraph, arXiv:1203.3402v1 (2012; statement numbers as in this version); conference version in: Implementation and Application of Automata (CIAA 2012), Lecture Notes in Comput. Sci. 7381, Springer (2012), 90–100.arxiv.org/abs/1203.3402
  2. [2]M. V. Berlinkov, Synchronizing quasi-Eulerian and quasi-one-cluster automata, Internat. J. Found. Comput. Sci. 24(6) (2013), 729–745.DOI
  3. [3]J. Černý, Poznámka k homogénnym experimentom s konečnými automatmi, Mat.-Fyz. Časopis Sloven. Akad. Vied 14(3) (1964), 208–216; English translation: A note on homogeneous experiments with finite automata, J. Autom. Lang. Comb. 24(2–4) (2019), 123–132.
  4. [4]J. Černý, A. Pirická and B. Rosenauerová, On directable automata, Kybernetika 7(4) (1971), 289–298.
  5. [5]P. Frankl, An extremal problem for two families of sets, European J. Combin. 3(2) (1982), 125–127.DOI
  6. [6]V. V. Gusev and E. V. Pribavkina, On synchronizing colorings and the eigenvectors of digraphs, in: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), LIPIcs 58 (2016), 48:1–48:14.DOI
  7. [7]J. Kari, Synchronizing finite automata on Eulerian digraphs, Theoret. Comput. Sci. 295(1–3) (2003), 223–232.
  8. [8]A. Kisielewicz, J. Kowalski and M. Szykula, Experiments with synchronizing automata, in: Implementation and Application of Automata (CIAA 2016), Lecture Notes in Comput. Sci. 9705, Springer (2016), 176–188; arXiv:1607.04025.DOI
  9. [9]J.-E. Pin, On two combinatorial problems arising from automata theory, Ann. Discrete Math. 17 (1983), 535–548.DOI
  10. [10]Y. Shitov, An improvement to a recent upper bound for synchronizing words of finite automata, J. Autom. Lang. Comb. 24(2–4) (2019), 367–373.arxiv.org/abs/1901.06542
  11. [11]B. Steinberg, The averaging trick and the Černý conjecture, Internat. J. Found. Comput. Sci. 22(7) (2011), 1697–1706.
  12. [12]M. Szykula, Improving the upper bound on the length of the shortest reset word, in: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), LIPIcs 96 (2018), 56:1–56:13.DOI
  13. [13]M. Szykula, Synchronizing automata: open problems, in: 17th International Conference on Automata and Formal Languages (AFL 2026), EPTCS 451 (2026), 33–47; arXiv:2608.24245.
  14. [14]M. V. Volkov, Synchronizing automata and the Černý conjecture, in: Language and Automata Theory and Applications (LATA 2008), Lecture Notes in Comput. Sci. 5196, Springer (2008), 11–27.DOI
  15. [15]M. V. Volkov, Synchronization of finite automata, Russian Math. Surveys 77(5) (2022), 819–891.DOI
  16. [16]M. V. Volkov, List of results on the Černý conjecture and reset thresholds for synchronizing automata, arXiv:2508.15655v4 (2026).arxiv.org/abs/2508.15655
  17. [17]Y. Zhu, The Černý conjecture for one-cluster automata via annular spectral descent, arXiv:2607.19675 (2026).arxiv.org/abs/2607.19675

Paper details

vlnc:W_5ydr7bqq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude, ChatGPT

View statement
Looking for related papers…
Contents