Synchronizing Automata: Open Problems
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 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. 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.Where the paper says it
Where the paper says it
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 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. 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 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 oneWhere the paper says it
Where the paper says it
Where the paper says it
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 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].Where the paper says it
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 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). 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
).Where the paper says it
Where the paper says it
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 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). [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).Where the paper says it
Where the paper says it
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 Open Problem 13. Given A under a fixed alphabet, is there a faster algorithm than O(n
2
)
checking whether it is synchronizing? 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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)). 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)). 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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
-
Improve synchronization algorithms by using linear-algebraic methods to check synchronizability, potentially achieving faster than O(n 2) performance for a fixed alphabet automaton.
-
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.
-
Enhance decision procedures for synchronizability to potentially achieve faster than O(n 2) time complexity for a fixed alphabet automaton, addressing Open Problem 13.
-
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.
-
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
- Quantitative Verification of Infinite-State Networks
- A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata
- Positive-Data Learning of Fixed-Observation Linear MCFGs from Working Binary Presentations
- On the Separability Problem of VASS Reachability Languages
- Exact Accepting-State Spectrum for Reversal of Permutation Automata
- On Word Representations and Embeddings in Complex Matrices