CS Paper Radar

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

Qichao Wang, Daoyu Dong

cs.FL math.CO ·submitted 2026-10-05 01:15 UTC · v2
theory

Abstract

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$.

Comment
9 pages, 1 figure. Revised proofs and exposition, corrected boundary transitions, updated references, and added a coauthor

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.FL ·2026-09-14 ·Enkai Zhang
theorycode/data similarity 0.70
Abstract · 42 pages, including additional results and computational notes. Computational data are available at https://doi.org/10.5281/zenodo.22561629

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$.

0.35

Synchronizing Automata: Open Problems

cs.FL ·2026-08-25 ·Marek Szykuła
publishedsurveyhot directionhighly cited similarity 0.63
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.62
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

Quadratic reset bounds for finite maximal prefix codes

cs.FL ·2026-11-03 ·Samrath Singh Chadha
theory similarity 0.62
Abstract

Let $C$ be a finite maximal prefix code of maximum codeword length $k\ge2$. We prove that, whenever the literal decoder of $C$ is synchronizing, it has a reset word of length at most $(k-1)(4k-5)$. The bound is independent of the alphabet and the number of decoder states. Its main ingredient is a short-detection theorem: a linear observation of the decoder, with terminal weight constant on states of depth $k-1$, is either identically zero or nonzero on a word of length at most $2k-3$. The proof uses a first-return decomposition in noncommuting variables and cancellation of a highest-degree coefficient. For codes whose codeword lengths are $k-1$ and $k$, we prove the sharper bound $2(k-1)^2-1$ and characterize equality. The binary code with the single short word $a^{k-1}$ attains this bound for every $k\ge2$; an age representation and a potential on circular arcs give the matching lower bound. Both upper bounds yield polynomial-time constructions in the explicit code size. The mathematical results and the algorithms are formalized in Lean, with polynomial work bounds in a specified binary cost model.

0.12

On smallest synchronizing terms over constant alphabets

cs.FL ·2026-09-01 ·Luisa Herrmann, Richard Mörbitz
theory similarity 0.61
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

Separating Words with Automata in the Half-adversarial Case

cs.FL ·2026-08-28 ·Gabriel Bathie
theory similarity 0.60
Abstract

We consider the problem of separating words with deterministic finite automata (DFA) (Goral{č}{í}k and Koubek, 1986). This problem asks: given two distinct words $u,v$ of length at most $n$, what is the size of the smallest DFA that accepts one and rejects the other? The best upper bound on the worst-case over all pairs of words of length at most $n$ is $\tilde{O}(n^{1/3})$ states (Chase, 2021), while the best lower bound is $Ω(\log n)$. In this work, we consider the half-random, half-adversarial case: we show that if $u$ is a uniformly random binary word of length $n$, then with high probability, for any word $v$ not equal to $u$, there is a DFA with $O(\log^{7/3} n \mathrm{poly}\log\log n)$ states that separates $u$ and $v$. Our results are based on a novel analysis that exploits the structural sparsity of random words: we show how to apply block-wise compaction with small deterministic transducers to reduce the separation problem to the case of words with short run-length encodings.

0.21

The Ternary and Quaternary Cases of the $\{2,4\}$-Distance Code Conjecture

cs.IT math.CO ·2026-10-22 ·Yen-Chi Roger Lin, Valjakas Djaljapayan, Wei-Hsuan Yu
theory similarity 0.59
Abstract

For an integer $q\ge2$, let $A_q(n,\{2,4\})$ be the largest cardinality of an unrestricted $q$-ary code of length $n$ in which any two distinct words have Hamming distance $2$ or $4$. We prove that \[ A_q(n,\{2,4\})=1+\binom n2 \qquad(q\in\{3,4\},\ n\ge6), \] thereby settling the two remaining alphabet sizes in the conjecture of Boyvalenkov, Delchev, Zinoviev, and Zinoviev; the binary case was settled previously. The quaternary result implies the ternary result by alphabet inclusion. For $n\ge16$, the quaternary upper bound is proved combinatorially. After normalizing one word to zero, the weight-four supports form a $2$-intersecting family; exact support intersections force symbol synchronization and restrict support multiplicities. We combine the nontrivial intersection theorem with matching arguments and a three-coordinate projection lemma. The finite lengths $6\le n\le13$ are handled by a complete Hamming-isometry reduction to exact clique decisions, and $n=14,15$ by a smaller exact weighted-clique relaxation. All finite decisions are reproduced by two standalone integer-only C++17 verifiers provided as supplementary source files.

0.20

Quadratic bounds for uncompletable words and matrix mortality

cs.FL math.CO ·2026-09-25 ·Rahul Chandelkar, Samrath Singh Chadha
similarity 0.59
Abstract · Lean formalization and implementation pilot included as ancillary material

Every finite nonempty incomplete uniquely decipherable code with maximum word length $k$ has an uncompletable word of length at most $4k^2-3k$. The bound is independent of the number of codewords and their total length. Deleting a complete codeword cycle gives a finite path-counting identity; Kraft equality then supplies a short word of deficient compressed mass. Cyclic averaging and padding turn it into an uncompletable word. Conditional expectation makes the construction polynomial-time and also decides completeness. First-return words extend the bound to mortal families of nonnegative integer $n\times n$ matrices with joint spectral radius at most one, provided every strongly connected component has a vertex meeting every cycle. Such a family has a zero product of length at most $4n^2-3n$. A binary partial deterministic family with $2k-1$ states has shortest zero product of length $k^2+k-1$, establishing the optimal quadratic order. The bounds and the explicit-code algorithm, including its polynomial work bound, are proved in Lean.

0.33