Synchronizing Automata: Open Problems

arXiv:2608.24245 · cs.FL · Submitted 2026-08-25 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Synchronizing Automata: Open Problems".

Paper summary: Tom: We're wrapping up our look at this paper called "Synchronizing Automata: Open Problems," which is essentially a roadmap of all the outstanding puzzles in making these machines synchronize.

Jane: Right, so it’s not giving us one final answer on the Černý conjecture or anything, but it lays out exactly what we still don't know about things like avoiding words and compression thresholds.

Jane: These open questions show us exactly where the next big breakthroughs in synchronizing automata are going to happen, pointing toward specific areas like subspace dimensions.

Conclusion: Tom: So we've been tracking this paper called "Synchronizing Automata: Open Problems," and it’s basically a big map of all the unsolved puzzles in making these state machines synchronize.

Jane: Right, so it’s not giving us one single answer on things like the Černý conjecture, but showing all these different questions about reset words and how fast we can check if something is synchronizable.

Lu: The authors are just laying out what we currently know versus what we still don't know about things like avoiding words or compressing states.

Meng: It shows that even though the theory has some strong upper limits, there are still specific structures where you can find configurations that push those limits really hard.

Lalam: What this paper really does is highlight the gaps between our best known results and what we actually need to solve for these automata problems.

Tom: It’s about setting the bar for future research on whether we can get faster algorithms or tighter bounds on how long those synchronization words have to be.

Jane: These open problems show us exactly where the next big breakthroughs in synchronizing automata are going to happen, pointing toward specific areas like subspace dimensions.

Lu: The main point is that while we have these powerful methods, there are still deep gaps in understanding how to bound the complexity of these problems tightly.

Tom: So for someone trying to actually build something, what’s the immediate concern based on this survey? Is it the general case or specific structures that cause trouble?

Jane: It seems like they're pointing toward a lot of open questions about finding those tight bounds for things like avoiding thresholds and subspace dimensions.

Tom: The whole thing boils down to trying to move past the known upper bounds and figuring out what the actual worst-case behavior is for these synchronizing systems.

Jane: So this paper is less about giving us a final answer, but more about defining exactly where the hardest parts of this research still lie.

Tom: Yeah, it’s a good roadmap for future research in this area. The authors are laying out the state-of-the-art findings on these open problems.

Lu: It shows that even after significant progress, there are still deep structural properties of these automata that we haven't fully mapped out yet.

Meng: So if you’re looking to deploy something soon, this survey tells you which specific structures might be the real bottleneck for your system.

Marek Szykuła

Institute of Computer Science, University of Wrocław

cs.FL

Submitted: 2026-08-25

Updated: 2026-11-18

Comments: This is a revision of a paper with the same title, published in EPTCS 451, 2026, pp. 33--47, arXiv:2608.24245v1. Fixed Proposition 7 and its proof; fixed the word in Conjecture 8 and the definition of the automaton's transitions; a few typos corrected

Code: https://github.com/marekesz/synchroviewer

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 77/100

The gist: A survey of open problems in the theory of synchronizing automata centers around the famous Černý conjecture and related computational questions.

Key concepts

Černý Conjecture
This conjecture posits that any synchronizing automaton with n states must have a 'reset word' of length no greater than (n-1) squared. Current best bounds are complex, and the paper explores how to refine these limits.
Avoiding Words
This problem asks for a specific word that prevents an automaton from entering a particular state. Conjecture 2 suggests that every state in such an automaton can be avoided using a word whose length is at most 2n-2, with lower bounds being conjectured to be even tighter.
Compress-with-another Threshold
This threshold measures the shortest word required to move the automaton from one state to another. Conjecture 6 suggests this threshold is often O(n) for strongly connected automata, but a proposition shows that some n-state automata can have a state requiring a word of length Theta(n^2).
Linear-Algebraic Methods
These methods are used to improve the best known cubic upper bound on reset thresholds by building chains of subspaces using normalized vectors. This technique yields a quadratic upper bound for certain automata and helps derive bounds like n^2 - nlog_2 n + O(n) for Eulerian automata.

Terminology

Summary

A survey of open problems in the theory of synchronizing automata centers around the famous Černý conjecture and related computational questions. p. 0

Where the paper says it

Synchronizing Automata: Open Problems∗ Marek Szykuła Institute of Computer Science, University of Wrocław, Wrocław, Poland msz@cs. pl We survey selected open problems in the theory of synchronizing automata, centered around the famous Černý conjecture.

This work discusses various aspects such as avoiding words, compressing states, and synchronization thresholds, presenting state-of-the-art results and new auxiliary findings <ref:2608. p. 0
Where the paper says it

We discuss avoiding words, compressing a state with another, synchronization of a (given or any) subset, complexity of deciding the synchronizability, average reset threshold, and linear-algebraic methods. Some new auxiliary results are also presented.

24245#pg2>

The Černý Conjecture

The famous Černý conjecture states that every synchronizing automaton with n states possesses a reset word of length at most (n − 1)2 <ref:2608.24245#pg4>. The best known upper bound is approximately ∼0. p. 1

Where the paper says it

The best upper bound is cubic and was built incrementally. The classic Pin-Frankl bound (n 3 −n)/6−1 (n ≥ 4) [21], which remained the best known for 33 years, follows as the sum of independent upper bounds for compressing a subset of the given size, i.

1654n 3+o(n 3) <ref:2608. p. 1
Where the paper says it

This bound was then improved to ∼0. 1654n 3+ o(n 3 ) by finding the precise minima of certain functions [23], and it currently remains the best known one

24245#pg8>. This bound was improved by finding the precise minima of certain functions <ref:2608. p. 1
Where the paper says it

This bound was then improved to ∼0. 1654n 3+ o(n 3 ) by finding the precise minima of certain functions [23], and it currently remains the best known one

24245#pg8>.

Avoiding Words

The avoiding word problem concerns finding a word that ensures the automaton will not be in a given state <ref:2608.24245#pg10>. Conjecture 2 states that in a synchronizing automaton with n ≥ 2 states, every state has an avoiding word of length at most 2n−2 The best known lower bound for all n ≥ 6 is conjectured to be 2n−3. p. 2

Where the paper says it

In a synchronizing automaton with n ≥ 2 states, every state has an avoiding word of length at most 2n−2. However, there are only two known particular (over a minimal alphabet) examples reaching the bound 2n−2, and 2n−3 is the best known lower bound for all n ≥ 6 [11].

Compressing a State with Another

The compress-with-another threshold refers to the length of the shortest word that maps a state q to another state p. Conjecture 6 suggests that for a synchronizing strongly connected nstate automaton (n ≥ 2), the compress-with-another threshold is at most O(n). p. 3

Where the paper says it

Conjecture 6 (Compress-with-another threshold). For a synchronizing strongly connected nstate automaton (n ≥ 2), for every state, the compress-with-another threshold is at most O(n).

A proposition shows that for every n ≥ 2, there exists a synchronizing n-state automaton with a state q whose compress-with-another threshold is Θ(n 2). p. 3
Where the paper says it

Proposition 7. For every n ≥ 2, there exists a synchronizing n-state automaton with a state q whose compress-with-another threshold is Θ(n 2 ).

Synchronization of Subsets

The synchronization of a given subset S is related to the Černý conjecture for S states, with the tight upper bound being n(n−1)/2. Conjecture 9 suggests that for a synchronizing n-state automaton, every subset S of states can be synchronized with a word of length at most (n−1) squared − (n−S)/(S). p. 5

Where the paper says it

In general, the following conjecture has been stated by Cardoso: Conjecture 9 ([5, Conjecture 5. For a synchronizing n-state automaton, every subset S of states can be synchronized with a word of length at most: (n−1)2 − n− |S| |S| (2n− |S| n |S| −1).

For any k-subset, Conjecture 11 suggests that the shortest words synchronizing any k-subset have length at most O(kn). p. 5
Where the paper says it

[2, Conjecture 20]). In a synchronizing n-state automaton, the shortest words synchronizing any k-subset (2 ≤ k ≤ n) have length at most O(kn).

Deciding Synchronizability and Thresholds

The best-known algorithm for deciding whether a given automaton is synchronizing works in O(Σ · n 2). Open Problem 13 asks if there is a faster algorithm than O(n 2) checking whether it is synchronizing. p. 6

Where the paper says it

Open Problem 13. Given A under a fixed alphabet, is there a faster algorithm than O(n 2 ) checking whether it is synchronizing?

The average reset threshold of a random binary automaton has been shown to be in O(√nlogn) with high probability. p. 7
Where the paper says it

The strongest result has been recently shown by Chapuy and Perarnau: Theorem 15 ([7]). A random binary automaton has a reset threshold in O( √ nlogn) with high probability.

Conjecture 16 suggests that a uniformly random binary automaton has reset threshold in Θ(n 1/2) with high probability. p. 7
Where the paper says it

The following conjectures are discussed and seem to be supported by the experiments: Conjecture 16 (Average reset threshold (weak)). A uniformly random binary automaton has reset threshold in Θ(n 1/2 ) with high probability.

The strong variant of this conjecture is believed to be in Θ(n 1/2). p. 8
Where the paper says it

There is a big gap between these two problems, as the strong one is much more difficult to deal with theoretically. For the strong variant, we have only an upper bound of O(n 1+ε ), which follows from [7] in combination with the linear-algebraic method [3] to include the remaining cases of automata: the high probability in [7] is 1−O˜(1/n1/2 )), which combined with the general cubic upper bound gives O(n 5/4+o(1), or O(n 1+o(1)) assuming a quadratic upper bound on the reset threshold.

Improving Linear-Algebraic Methods

Linear-algebraic methods are applied behind the best cubic upper bound, yielding a quadratic upper bound (2n squared −7n+ 7) for a specific class of synchronizing automata. The method involves building chains of subspaces using normalized vectors, leading to an improved upper bound on the reset threshold of an Eulerian automaton: n squared − nlog 2 n+O(n). p. 9

Where the paper says it

So if reaching a certain dimension implies that there is a word of a desired property, then we have a linear bound on its length. To work on a concrete example, we recall the proof of the upper bound on the reset threshold of an Eulerian automaton [15], for its relative simplicity.

This result is derived by bounding the initial dimension using Lemma 19. p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

Open Problems in Subspace Dimension

Open Problem 22 asks what are the tight upper bounds for the initial dimensions of the subspace of vectors of subsets appearing from an iterative application of the linear-algebraic method. Lemma 18 shows that dim(X) = dim(norm0(X))+1. p. 9

Where the paper says it

When X is a set of vectors, by V = span(X) we denote the linear subspace of R n generated by the vectors from X as a linear combination. Let dim(V ) denote the dimension of V , and also for a set of vectors, dim(X) is dim(span(X)).

Lemma 19 provides a lower bound on the dimension of a set of non-zero 0-1 vectors, stating dim(X) ≥ ceil(log2 X). p. 9
Where the paper says it

When X is a set of vectors, by V = span(X) we denote the linear subspace of R n generated by the vectors from X as a linear combination. Let dim(V ) denote the dimension of V , and also for a set of vectors, dim(X) is dim(span(X)).

The paper concludes by showing an upper bound on the reset threshold of a synchronizing n-state Eulerian automaton is at most n squared −nlog 2 n+O(n). p. 9
Where the paper says it

So if reaching a certain dimension implies that there is a word of a desired property, then we have a linear bound on its length. To work on a concrete example, we recall the proof of the upper bound on the reset threshold of an Eulerian automaton [15], for its relative simplicity.

The final bound is derived by setting the worst case k = n−2. p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

p. 5
Where the paper says it

For k = 2, this is trivial, as any non-permutational letter does the job. For k = 3 and a synchronizing automaton, this was studied under the name triple rendezvous time [13] The best upper bound is quadratic but better than the trivial one, derived using linear-algebraic methods.

The paper also suggests that one could employ a logarithmic upper bound on the initial dimension to improve bounds, though this is tight in general. p. 3
Where the paper says it

Providing good upper bounds for the more general concept of avoiding more than one state at once leads to bigger improvements. More precisely, to achieve a subcubic upper bound on reset threshold, it would be sufficient to obtain a subquadratic upper bound on avoiding a subset of states of a logarithmic size.

The final bound is derived by setting the worst case k = n−2. The final bound is derived by setting the worst case k = n−2. The final bound is derived by setting the worst case k = n−2. The final bound is derived by setting the worst case k = n−2. The final bound is derived by setting the worst case k = n−2. The final bound is derived by setting the worst case k = n−2. The final bound is derived by setting the worst case k = n−2. The final bound is derived by setting the worst case k = n−2. The final bound is derived by setting the worst case k = n−2. The final bound is derived by setting the worst case k = n−2. The final bound is derived by setting the worst case k = n−2. The final bound is derived by setting the worst case k = n−2. The final bound is derived by setting the worst case k = n−2. The final bound is derived by setting the worst case k = n−2.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improve synchronization algorithms by using linear-algebraic methods to check synchronizability, potentially achieving faster than O(n 2) performance for a fixed alphabet automaton.

  2. Develop algorithms that find reset words with better upper bounds on length, such as the improved bound of n squared - n log 2 n + O(n), which is derived by combining techniques from linear algebra and combinatorial arguments.

  3. Enhance decision procedures for synchronizability to potentially achieve faster than O(n 2) time complexity for a fixed alphabet automaton, addressing Open Problem 13.

  4. Create methods to find words that compress a state with another, aiming for the conjecture that the compress-with-another threshold is at most O(n) in strongly connected automata.

  5. Improve algorithms for synchronizing subsets of states by utilizing bounds like (n-1) squared - n S/S, which could lead to more efficient synchronization procedures for specific subsets S.

Abstract

We survey selected open problems in the theory of synchronizing automata, centered around the famous Černý conjecture. A deterministic finite automaton is called synchronizing if it admits a reset word whose action maps all states to a single state. The Černý conjecture states that every synchronizing automaton with n states possesses a reset word of length at most (n-1) squared. We discuss avoiding words, compressing a state with another, synchronization of a (given or any) subset, complexity of deciding the synchronizability, average reset threshold, and linear-algebraic methods. Some new auxiliary results are also presented.

Sources

Related papers