Source-linked AI summary
Further Remarks on Separating Words
John Nicol
TL;DR
The paper revisits separating-word questions about structured pairs, conjugate words, word order, and reversal. It develops run-based and shift-arithmetic bounds, then proves unbounded orientation effects for nondeterministic and deterministic separation, with reversal also improving an Open Problem 3 lower bound.
Problem
The paper addresses unresolved bounds and open problems concerning separating words, including structured differences, conjugate words, word order, and reversal.
Method
The paper uses boundary-based fingerprints, arithmetic analysis of cyclic shifts, and reversal constructions based on a small reversed-language DFA and diagonalization over bounded-state DFAs.
Results
The paper proves O(d log n) separation for d difference runs, gives shift-arithmetic conjugate-word bounds, and establishes unbounded orientation ratios for nondeterministic and deterministic separation.
Takeaways & Limitations
The results answer or refine Demaine et al.’s questions and show that word order and reversal can fundamentally alter separation complexity.
Takeaways & Limitations
The optimal run-based and conjugate-word bounds remain unknown, as do the exact asymptotic order for Open Problem 3 and a reduced reversal length threshold.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper revisits structured separating-word questions and resolves open problems about word order and reversal. It proves new bounds for difference runs and conjugate words, including unbounded separations between orientations.
- Runs of differences: O(d log n) states detect d runs of differences, regardless of how many positions differ.This generalizes the Hamming-distance bound O(h log n) for h differing positions.
- Conjugate words: Conjugate-word separation depends on the arithmetic of the cyclic shift, including its greatest common divisor.Large gcd shifts contain shorter separating-word instances, while small gcd shifts admit small fingerprints.
- Open Problem 2: The order of two equal-length binary words can change nondeterministic separation by an arbitrarily large difference and ratio, even when they differ in only two positions.This resolves Open Problem 2.
- Reversal: Forward and reversed deterministic separation can differ by an unbounded ratio: one orientation needs more than N states while the other needs O(log N).This addresses Ebrahimnejad’s follow-up to Open Problem 1.
- Open Problem 3: Because nondeterministic separation is invariant under reversal, the reversal construction also improves the lower bound in Open Problem 3.The paper is organized around questions posed by Demaine, Eisenstat, Shallit, and Wilson.
2. Hamming distance and runs of differences
The paper extends Hamming-distance separation from individual differing positions to runs in the difference word. A boundary-based parity fingerprint yields an O(d log n)-state DFA.
- Proof strategy: The proof replaces differing positions with the 2d boundaries of the difference runs.A suitable prime p = O(d log n) isolates one boundary in its residue class.
- Theorem 1: sep(w, x) = O(d log n) when the difference word of w and x has d runs.The bound is the main theorem for structured pairs.
- Proof strategy: A two-ring DFA tracks input position modulo p and switches rings on a selected residue-class symbol, using 2p = O(d log n) states.The appropriate ring is chosen as accepting after a parity fingerprint differs.
- Consequences: The Hamming-distance theorem follows because h differing positions create at most h runs, giving sep(w, x) = O(h log n).Thus the new theorem contains the earlier result as a direct consequence.
- Consequences: Thue–Morse words and their complements differ by one complemented middle interval, so the theorem gives an O(log n)-state separator.Here d = 1 despite the words’ self-similar structure.
3. Conjugate words
For conjugate words related by a cyclic shift, separation complexity is governed by both the shift arithmetic and the distance of the shift from the endpoints. The paper combines lower and upper bounds under the exact-length convention.
- Convention: The results use the exact-length convention, whereas some earlier work maximized over pairs whose lengths were at most n.This convention is stated explicitly before the conjugate-word bounds.
- Consequences: When g = 1, the upper bound is O(log^2 n), while fixed k or fixed n − k gives O(1) states.These are consequences of the theorem’s upper bounds.
- Arithmetic of the shift: R(n, k) is bounded below by the ordinary separating-word complexity at length g = gcd(n, k).The lower bound embeds any pair of distinct binary words of length g into conjugate words of length n.
- Endpoint bounds: A separate construction gives R(n, k) ≤ 2 min{k, n − k} + 1 = O(min{k, n − k}).It follows the shift using k states, then uses a k + 1-cycle after the first deviation from periodicity.
4. Nondeterministic separation
The paper shows that nondeterministic separation depends strongly on word order: swapping two equal-length binary words can produce unbounded differences and ratios. It also constructs reversals with large deterministic-versus-nondeterministic separation, while nondeterministic separation itself is reversal-invariant.
- 4.1. The order of the two words: nsep(us, vs) > s2 while nsep(vs, us) ≤ s + 1 for equal-length binary words us and vs.Thus both the difference and the ratio between the two orientations are unbounded.
- 4.1. The order of the two words: The constructed words have the same length and differ in only two positions, yet their nondeterministic separation changes by an unbounded factor when their order is swapped.This resolves Open Problem 2 and rules out a constant upper bound on the orientation ratio.
- 4.1. The order of the two words: An (s + 1)-state NFA separates vs from us, whereas every NFA with at most M = s2 states fails to separate us from vs.The construction uses M = s2, T = 2M, and P = lcm(1, 2, . . . , T).
- 4.1. The order of the two words: The exact growth of A(q) remains open.The paper therefore leaves the asymptotic behavior of this quantity unresolved.
- 4.2. Deterministic versus nondeterministic separation: Nondeterministic separation is unchanged by reversing both words: nsep(w, x) = nsep(wR, xR).Reversing an NFA preserves its state set and exchanges its initial and accepting-state roles appropriately.
- 4.2. Deterministic versus nondeterministic separation: The reversal construction yields pairs whose forward deterministic separation exceeds N while the reversed pair has an O(log N)-state separator.Determinization then implies nondeterministic separation Θ(log N) for the forward pair.
5. Reversals
The reversal construction creates equal-length pairs whose forward deterministic separation exceeds N while their reversed separation is O(log N). The construction uses a delimiter language with a small reversed automaton, diagonalization, binary encoding, and padding.
- 5.3. Completing the construction: The reversed pair has an O(log N)-state separator, and binary coding plus padding preserves the separation bounds up to constant and additive overhead.The binary reduction uses fixed-length palindromic codewords, while padding reaches every larger prescribed length with reversed separation increasing by at most 1.
- 5.1. The delimiter language: The delimiters # and @ uniquely decompose words into blocks, enabling the language distinction used by the construction.The symbol # ends inner blocks, while @ separates blocks; consequently, @z@ is excluded when z belongs to G_k, whereas @h@ is included.
- 5.1. The delimiter language: O(k)-state DFAs recognize the reversed delimiter language C_k^R.The construction uses a partial DFA for G_R and complements it to recognize the relevant delimiter language.
- 5.2. Replacement and a common suffix: A universal replacement word z has length N^O(N) and preserves the relevant state-set action for every DFA with at most N states.The proof minimizes reachable image sizes and concatenates fewer than 2N replacement words for each transition table.
- 5.3. Completing the construction: Diagonalization yields equal-length words u_N and v_N with sep(u_N, v_N)>N, while u_N∈C_k and v_N∉C_k.No DFA with at most N states separates the pair, because the construction equalizes the action on every state pair considered.
6. Conclusion
The paper answers or refines the motivating separation questions, including unbounded orientation effects for nondeterministic and deterministic separation. Several optimal asymptotic bounds remain open.
- Conclusion: The Hamming-distance bound extends from h differing positions to d runs of differences with O(d log n) states.This bound holds regardless of how many positions differ.
- Conclusion: For conjugate words, separation complexity depends on the arithmetic of the shift.
- Conclusion: Nondeterministic separation can change by an unbounded difference and ratio when the order of two equal-length binary words is swapped.The pairs can differ in only two positions.
- Conclusion: The reversal construction gives an unbounded forward-versus-reversed deterministic ratio and improves the lower bound for Open Problem 3.This transfer uses invariance of nondeterministic separation under reversal.
- Open questions: The optimal run-based and conjugate-word bounds remain unknown, as do the correct asymptotic order and length threshold for Open Problem 3.The exchange function A(q) also remains between quadratic and exponential.