CS Paper Radar

The triple rendezvous time of a synchronizing automaton can be floor(4n/3)

Enkai Zhang

cs.FL ·submitted 2026-09-14 14:53 UTC · v1
theorycode/data

Abstract

For every $n\ge9$, we construct a strongly connected synchronizing automaton with two input letters and $n$ states whose shortest word merging some three distinct states has length $\lfloor4n/3\rfloor$. One letter is a permutation; the other has an image of size $n-1$. We give complete transition maps and an explicit word attaining the bound. For the lower bound, we assign an integer to each unordered pair of states and prove that applying either input letter can decrease it by at most one. For $n\not\equiv0\pmod3$, the same construction contains a specified state whose shortest merging word, with its partner chosen freely, has length $\lfloor4n/3\rfloor-1$.

Comment
42 pages, including additional results and computational notes. Computational data are available at https://doi.org/10.5281/zenodo.22561629

Closest papers

Nearest neighbours by meaning across the whole index.

An exact compress-with-another threshold in a binary automaton family

cs.FL math.CO ·2026-10-05 ·Qichao Wang, Daoyu Dong
theory similarity 0.70
Abstract · 9 pages, 1 figure. Revised proofs and exposition, corrected boundary transitions, updated references, and added a coauthor

For a state $q$ in a synchronizing automaton, let $μ(q)$ be the minimum length of a word merging $q$ with another initial state. Szykuła asked whether $μ(q)=O(n)$ for strongly connected synchronizing automata and described a binary family attributed to Dżyga, with $n=3p$ states and a conjectured threshold $4n/3$. We specify the boundary transitions omitted from the published piecewise definition and prove that the resulting automata $\mathcal A_p$ satisfy $μ(q_0)=4p=4n/3$ for all $p\geq3$. A shortest word merging $q_0$ with another state is $(ba)^p(ab)^p$. We also construct a reset word of length $3p^2+4p-1$. Consequently, any uniform linear upper bound for $μ(q)$ on binary strongly connected synchronizing automata with corank-one letters has leading constant at least $4/3$.

0.20

Synchronizing Automata: Open Problems

cs.FL ·2026-08-25 ·Marek Szykuła
publishedsurveyhot direction similarity 0.64
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

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)^2. 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.

0.72

An Elementary Proof of the $\widetilde O(n^{1/3})$ Bound for Separating Words

cs.FL cs.CCmath.CO ·2026-09-08 ·Chen Xu
theory similarity 0.59
Abstract

For two distinct binary words of length $n$, the separating words problem asks for a small deterministic finite automaton that accepts exactly one of them. Chase proved a $\widetilde O(n^{1/3})$ upper bound using a complex-analytic estimate for sparse polynomials. We replace that estimate by a finite-difference argument and a second-order real recurrence cutoff. The resulting elementary proof gives an explicit bound of $O(n^{1/3}(\log n)^{7/3})$ states.

0.09

On smallest synchronizing terms over constant alphabets

cs.FL ·2026-09-01 ·Luisa Herrmann, Richard Mörbitz
theory similarity 0.58
Abstract

We show a subexponential lower bound on the reset threshold of synchronizing deterministic finite tree automata (DTA) over alphabets of just two symbols. This significantly improves the previous one, which was quadratic in the number of states. Our result also narrows the gap towards the lower bound for DTA over alphabets that grow linearly with the number of states, as well as the best known upper bound, both of which are currently exponential.

0.08

Shortest Synchronizing Words on Product Automata

cs.FL ·2026-11-06 ·Henning Fernau, Igor Rystsov
similarity 0.58
Abstract

We consider some operations on finite automata graphs, in particular various product, union and merge operations, and investigate how they relate to the parameter~$\mathrm{rt}$, the \emph{length of a shortest synchronizing word}. We derive some lower and upper bounds for the operations that we study. We also examine several classes of automata (for instance, partially ordered, commutative or idempotent automata) that are preserved under these operations and show in which way the parameter $\mathrm{rt}$ behaves in these automata classes. Also, we consider automata classes that can be constructed by combining automata from better known classes; in particular, these new classes of automata will also satisfy the bound of the famous Černý conjecture. This also motivates us to study even more closure properties. In particular, we show that certain automata classes related to synchronization form pseudo-varieties. We also commence a similar study concerning the length of shortest homing sequences of Mealy automata.

0.13

A Factor-Two Lower Bound for Complementing Two-Way Deterministic Finite Automata

cs.FL cs.CC ·2026-10-10 ·Sudais Arif
theoryhot direction similarity 0.57
Abstract · 18 pages, 1 figure

For every $n\ge22$, we construct a language over a fixed three-letter alphabet whose two-way deterministic state complexity is $n$ and whose complement has state complexity $2n$. Acceptance is at the left endmarker, and infinite computations reject. The lower bound holds for arbitrary deterministic recognizers. The proof uses the group of transformations induced by the witness to constrain the behavior of a smaller recognizer, then derives a contradiction from a permutation query problem. A matching halting complement follows from a $2n$-state construction for sources whose destination states determine the direction of each transition. Splitting states by incoming direction gives a $2n+2b$ upper bound for general sources, where $b$ counts states entered in both directions. In the acceptance-anywhere model of Geffert, Mereghetti, and Pighizzini, the same family has exact complexities $N$ and $2N-1$ for every $N\ge23$.

0.39

Two barriers for minimal time firing squads, with applications to four and five states

cs.FL nlin.CG ·2026-11-08 ·Kia Keng Giam
publishedtheory similarity 0.55
Abstract · 34 pages, 18 figures, accepted (awaiting print) at the Journal of Cellular Automata

A minimal-time solution of the firing squad synchronization problem synchronizes every line of n cells at time 2n minus 2. Six states suffice; whether five do has been open since 1987. Every line agrees with the half line until its right ends echo returns. For minimal time solutions with any number of states, we prove that cells at distance j behind the half lines front become time-periodic only after time (1.5 minus epsilon)j, for every epsilon greater than 0 and infinitely many j, and that the half line is never periodic in time and space on a wedge at its left border, hence not eventually regular in our sense. With certified satisfiability checks, we exclude four states using the lines of lengths 2 to 5 and parts of the next five, and show that every five state minimal time solution uses at least 15 non quiescent neighbourhoods on its half lines first 78 anti-diagonals. We give five state rules synchronizing exactly the lengths 2 to 14.

0.47

Two-State Max-Plus Comparison Is Decidable

cs.FL cs.DS ·2026-09-01 ·Keigo Oka
similarity 0.55
Abstract · 8 pages. Revised presentation and clarified the proof; main result unchanged

Daviaud, Guillon, and Merlet proved that comparison of max-plus automata is undecidable under a fixed state bound of 553 and explicitly left the range from 2 to 552 states open. We resolve the two-state endpoint. More strongly, given an arbitrary finite max-plus automaton $A$ and a max-plus automaton $B$ with at most two states, it is decidable whether $[\![A]\!](w)\leq [\![B]\!](w)$ for every word $w$. The structural reason is a one-dimensional projective normal form for two-state dynamics. Outside an effective bounded region, a transition has one of three tail behaviors: it propagates the unbounded projective gap with gap-independent height increment, forgets the gap with gap-independent height increment, or reads the gap magnitude into the height increment and then forgets it. In particular, any transition whose output depends on the unbounded gap necessarily destroys that gap. This yields an exact one-counter realization of $B$. Effective semilinearity of context-free Parikh images then reduces comparison to Presburger arithmetic. As a consequence, two-state max-plus comparison, equivalence, and positivity are decidable.

0.21