Simpler proof shows small automata separate binary words efficiently
An Elementary Proof of the $\widetilde O(n^{1/3})$ Bound for Separating Words
Formal Languages and Automata TheoryComputational Complexity
Summary
The paper deals with a puzzle about telling two different binary strings apart using a very simple machine called a deterministic finite automaton (DFA). Previous work showed that such a machine only needs about the cube root of the string length in states, but the proof was complicated. The authors found a much simpler way to prove this, using basic math tools, and gave a clear formula for how big the machine needs to be. This makes understanding and using the result easier for people working with these machines.
What this means in practice
- •For software verification engineers: Create more efficient testers that distinguish program behaviors represented by binary sequences using small finite automata constructions.
- •For hardware design teams: Build compact hardware controllers that differentiate input signal patterns modeled as binary words with fewer states in deterministic finite automata.
A theory result. No direct application yet.
Authors
Chen Xu
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.