CS Paper Radar

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

Chen Xu

cs.FL cs.CCmath.CO ·submitted 2026-09-08 03:26 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

An Improved Lower Bound for Separating Words by Permutation Automata

cs.FL ·2026-10-08 ·Chen Xu, Kenneth Regan
theoryhot direction similarity 0.71
Abstract

We prove that some pairs of binary words of every sufficiently large prescribed length $n$ require $Ω(\log n\log\log n)$ states to separate by a deterministic finite automaton whose letters act as permutations. We obtain this bound by constructing distinct equal-length positive binary words that form an identity of $\mathfrak{S}_k$ of length $\exp(O(k/\log k))$. This improves the previous lower bound $(3/2-o(1))\log n$ of Bulatov, Karpova, Shur, and Startsev (arXiv:1609.03199). The proof combines a positive-word construction with a cover of permutation orders. Consecutive segments of prime powers reduce the covering problem to enumerating sets of positive integers with bounded sum. The required estimates use the central binomial coefficient and the classical asymptotic formula for partitions into distinct parts. An appendix gives sharper constants and lower-order terms using a greedy cover and a quantitative prime number theorem.

0.28

Separating Words with Automata in the Half-adversarial Case

cs.FL ·2026-08-28 ·Gabriel Bathie
theory similarity 0.70
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

Further Remarks on Separating Words

cs.FL ·2026-08-31 ·John Nicol
theory similarity 0.63
Abstract · 7 pages, 2 figures

We revisit questions on separating words raised by Demaine, Eisenstat, Shallit, and Wilson, together with Ebrahimnejad's follow-up to their reversal problem. For length-$n$ pairs whose difference word has $d$ runs, we prove an $O(d\log n)$ bound, extending the Hamming-distance theorem of Demaine et al. For conjugate words, we give bounds controlled by the arithmetic of the shift. We resolve Demaine et al.'s Open Problem 2 by showing that the order of two words can change nondeterministic separation by an unbounded factor. Our reversal construction addresses Ebrahimnejad's follow-up to Open Problem 1: forward and reversed deterministic separation can differ by an unbounded factor. Since nondeterministic separation is invariant under reversal, the same construction also improves the lower bound in Open Problem 3.

0.18

Exact versus unique nondeterministic automatic complexity

cs.FL math.LO ·2026-08-23 ·Bjørn Kjos-Hanssen, Travis Rivera Petit
similarity 0.63
Abstract

The exact nondeterministic automatic complexity $A_{Ne}(x)$ of a word $x$ is the minimum number of states of a nondeterministic finite automaton that accepts $x$ and no other word of length $|x|$; the unique nondeterministic automatic complexity $A_N(x)$ additionally requires the accepting computation to be unique. Chen, Kjos-Hanssen, Koswara, Richter, and Stephan (FSTTCS 2025) asked whether the two measures can differ. We answer this affirmatively: the binary word $w=1101000000100$ satisfies $A_{Ne}(w)=6<7=A_N(w)$. The separation is witnessed by a six-state automaton whose sole accepted word of length $13$ is $w$, accepted along exactly three computation paths. The matching lower bounds were established by exhaustive search and by SAT solvers, with proofs of unsatisfiability certified in the DRAT format. An exhaustive census shows that $13$ is the least length of a separating word over any alphabet, binary or not, and that up to renaming of letters the separating words of length $13$ are precisely $365$ letter-mergings of the single seven-letter word $0123444445126$, all with $A_{Ne}=6<7=A_N$; exactly eight of them are binary. The separating word and the core of the verification were found by an artificial intelligence agent.

0.22

Stronger bounds on the degree of ambiguity of finite automata

cs.FL ·2026-10-06 ·Stefan Kiefer, Filip Mazowiecki, Andrew Ryzhikov, Antoni Wiśniewski
similarity 0.63
Abstract

Ambiguity measures the number of accepting runs in nondeterministic finite automata (NFA). We consider finitely ambiguous NFA, where there exists a constant $N$ such that over every word $w$ there are at most $N$ accepting runs. In such a case we also say that the NFA is $N$-ambiguous. Importantly $N$ depends only on the NFA, it does not depend on the length of the word. Weber and Seidl showed that every NFA is $N$-ambiguous for $N = 2^{O(n \log n)}$, where $n$ is the number of states. We improve this to $N = 2^{O(n)}$, which is asymptotically tight.

0.32

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

Towards A Parametrized Complexity of Determinization

cs.FL ·2026-11-07 ·Ivan Baburin, Ryan Cotterell
similarity 0.62
Abstract

Given a nondeterministic finite automaton (NFA), we want to estimate the difficulty of finding an equivalent deterministic finite automaton (DFA). We demonstrate that computing the state complexity of an NFA within polynomial precision is \textsf{PSPACE}-hard, and furthermore the same holds for the complexity of the subset construction, Brzozowski's algorithm, or, indeed, \emph{any} determinization algorithm which runs at least as fast. This result implies that making any \textit{a priori} estimate of the running time of the major determinization algorithms is inherently hard. To circumvent this---in the spirit of parametrized complexity---we try to identify complexity measures which can guarantee efficient determinization. Our main idea rests on linking the complexity of the subset construction to transition monoids using the semigroup complexity. We show that the semigroup complexity by itself can be reasonably approximated for certain classes of NFAs, and then introduce \emph{subset complexity}---a refinement of the semigroup complexity which has a tighter connection with the subset construction. In certain scenarios, the subset complexity can be approximated in polynomial time, making it potentially viable for more practical applications.

0.25

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.61
Abstract · 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised.…

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

0.24