AI summaryⓘ
The authors revisit questions about how to distinguish pairs of words based on patterns in their differences, building on work by Demaine, Eisenstat, Shallit, Wilson, and Ebrahimnejad. They prove a new bound that depends on the number of specific pattern runs in the difference between two words, extending previous results on word differences. They also analyze pairs of words that are circular shifts (conjugates) and relate their bounds to the shift's properties. Additionally, the authors solve open problems about how the order of words affects certain measures of separation and show that reversing words can greatly change deterministic separation, while nondeterministic separation remains unaffected by reversal.
word separationrunsHamming distanceconjugate wordsnondeterministic separationdeterministic separationreversalopen problems
Abstract
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.