Summary
The problem is about creating a very simple computer that can tell two different strings of zeros and ones apart by accepting one and rejecting the other. Previously, someone showed that this computer only needs about the cube root of the string length in size, but their method was complicated. The authors provide a much simpler proof using basic math techniques, resulting in a similar but explicit size bound for these machines. This makes understanding and using these small computers easier.
deterministic finite automatonbinary wordsstate complexityseparating words problemupper boundsparse polynomialsfinite differencesrecurrence relations
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.