Source-linked AI summary
Separating Words with Automata in the Half-adversarial Case
Gabriel Bathie
TL;DR
The paper asks how large a DFA is needed to separate two distinct words, focusing on the case where one word is random and the other adversarial. It uses block-wise compaction with small deterministic transducers to exploit random-word sparsity, and proves an O(log^7/3 n poly log log n)-state separator with high probability. The analysis also identifies hierarchical factor repetitions as a feature of potential hard instances.
Problem
The problem is to determine the smallest DFA separating two distinct words of length at most n, whose general upper and lower bounds remain ˜O(n^1/3) and Ω(log n).
Method
The paper uses block-wise compaction with small deterministic transducers to exploit the structural sparsity of random words and reduce separation to short run-length encodings.
Results
With high probability, every word v distinct from a uniformly random binary u of length n can be separated from u by a DFA with O(log^7/3 n poly log log n) states.
Takeaways & Limitations
The half-random, half-adversarial case admits a polylogarithmic-state separator, while candidate hard pairs must exhibit hierarchical factor repetitions.
Takeaways & Limitations
The general-case lower bound remains Ω(log n), and the paper leaves open whether a hierarchical recursive construction can exceed the O(log n) conjecture.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies how many DFA states are needed to separate two distinct words and focuses on the half-random, half-adversarial setting. For a random word u, it proves a polylogarithmic-state upper bound against every distinct v.
- Problem setting: The separating-words problem asks for the smallest DFA that accepts one of two distinct words and rejects the other.The words have length at most n, and the objective is a tight worst-case asymptotic bound.
- Known bounds: The general problem remains open, with an upper bound of ˜O(n^1/3) states and a lower bound of Ω(log n).The gap has persisted for more than 40 years.
- Related special case: O(log n) states suffice with high probability when both words are uniformly random binary words.This is a restricted case in which both inputs are random rather than one being adversarial.
- Main result: The paper proves that a uniformly random binary u can be separated from every distinct v using O(log^7/3 n poly log log n) states with high probability.This treats the half-random, half-adversarial case as an intermediate setting between the exact worst-case problem and the fully random case.
- Approach: The proof exploits structural sparsity in random words through block-wise compaction by small deterministic transducers.The resulting separation problem is reduced to words with short run-length encodings.
- Related work: The literature also studies variants involving nondeterministic and quantum automata, context-free grammars, finite groups, and alternative starting-state requirements.Special cases include words differing near an endpoint or having bounded Hamming distance.
2 Technical preliminaries
This section defines words, DFAs, separation, and transducers, then records composition principles and simplifying assumptions used for upper-bound arguments. These preliminaries let small transformations be combined with automata that separate transformed words.
- Words: A word is a finite ordered sequence over a finite alphabet, with notation for length, positions, concatenation, substrings, powers, prefixes, and the empty word.Σ^n denotes words of length n, while Σ^≤n denotes words of length at most n.
- Deterministic finite automata: A DFA consists of an alphabet, finite state set, transition function, initial state, and accepting states.Its extended transition function determines the state reached after reading a word.
- Separation: Two words are separated by a DFA when exactly one is accepted, and sep(u,v) is the minimum number of states of such an automaton.sep(n) is the maximum of sep(u,v) over words of length at most n.
- Transducers: A deterministic finite transducer extends a DFA with outputs, mapping input words over one alphabet to output words over another.The paper uses deterministic finite transducers throughout.
- Composition: Composing a t-state transducer with an s-state automaton yields an automaton with s · t states recognizing inputs whose transformed outputs are accepted.The composition tracks the states of both devices in a product automaton.
- Composition: If a small transducer maps u and v to easily separable words, then the original words are also easily separable.Corollary 2.4 gives the multiplicative state bound s · t.
- Simplifying assumptions: For upper bounds, one may assume equal input lengths, equal symbol counts, and a binary alphabet after handling separable exceptional cases.Different lengths can be separated with O(log n) states, and unequal occurrence counts can be detected modulo a suitable prime.
- Simplifying assumptions: The proof extends morphism-based reductions by applying the morphism to blocks rather than individual letters.This block-level transformation is the bridge to the main construction.
3 Proof overview
The proof partitions the inputs into logarithmic-length blocks and uses a small transducer to compact a distinguishing block. The transformed words have short run-length encodings, which can then be separated with polylogarithmic-size automata.
- Block transformation: The construction divides u and v into blocks of length k = O(log n), producing words U and V over a larger alphabet.Because u ≠ v, some block position differs between U and V.
- Random-word sparsity: With high probability, a random u contains at most O(log n) occurrences of any length-k block, including a block B that differs between U and V.The sparsity bound holds with probability at least 1 − 1/n^C.
- Block compaction: A morphism maps the distinguishing block to a and all other blocks to b, yielding transformed words u′ and v′ with O(log n) occurrences of a in u′.The morphism is implemented by a transducing DFA with 2^k = O(log n) states.
- Run-count separation: If the transformed run counts differ, counting occurrences of ab modulo a prime p = O(log n) separates the words using O(log^2 n) states after composition.The first factor comes from the transducing construction and the second from modular counting.
- Run-length separation: If the run counts agree, a prime modulo test distinguishes a differing run length, after which another transducer reduces the words to length t = O(log n).The transducer counts successive a's modulo p and outputs according to the selected residue.
- Final bound: The reduced words are separated using Chase’s construction, giving the overall O(log^7/3 n poly log log n) bound.The final composition combines the transducer reductions with the separator for the shortened words.
4 The Half-Random, Half-Adversarial Case
The section reduces separation for a random word to sparse-word separation using small block-wise transducers, then combines this reduction with deterministic automata constructions. With high probability, every adversarial word distinct from the random word can be separated using O(log^{7/3} n poly log log n) states.
- 4.1 Separating sparse words: A t-sparse word contains at most t occurrences of a, and any such word can be separated from every other word using O(log n · t^{1/3} polylog t) states.The proof transduces the pair to distinct words of length O(t), applies Chase’s construction, and composes the automaton with the transducer.
- 4.1 Separating sparse words: Run-length encodings with different numbers of runs are separated by counting occurrences of ab or ba modulo a small prime, using O(log n) states.This is Case 1 of the sparse-word separation argument.
- 4.1 Separating sparse words: For run-length encodings of equal length, a transducer counts successive a’s or b’s modulo p and marks runs whose residues match a differing run length.A suitable prime p = O(log n) distinguishes a differing run length modulo p; the resulting words remain distinct and have length at most 2t.
- 4.2 Properties of random words: The transducer family F_k maps each length-k block to a if it equals w and to b otherwise, using 2k − 1 states.Each transducer therefore tests occurrences of one chosen block w.
- 4.2 Properties of random words: For k = log n and t = (C + 1) log n, a random word is mapped to a t-sparse word by every transducer in F_k with probability at least 1 − 1/n^C.Chernoff’s bound controls occurrences of each block, and a union bound makes the property simultaneous for all length-k blocks.
- 4.3 Separating a random word from an adversarial word: For every v ≠ u, some transducer in F_k maps u and v to distinct words; composing it with sparse-word separation yields O(log^{7/3} n poly log log n) states.The distinguishing transducer selects a block of u aligned with a differing block of v, while the random-word property supplies sparsity.
5 Conclusion
The paper characterizes hard-to-separate word pairs through repeated blocks whose repetition must persist across scales. This rules out simple random interleavings and points toward recursive constructions, while the general lower-bound question remains open.
- Insights on hard-to-separate words: Blocks that differ between u and v must occur many times in both words; otherwise, block transducers produce sparse words that are easy to separate.This applies particularly when the block length k is small.
- Future work: Θ(n/k) repetitions and many mismatches make randomly interleaved blocks a plausible candidate construction for hard-to-separate pairs.Such constructions also avoid the low-Hamming-distance case.
- Insights on hard-to-separate words: Hardness must be hierarchical: after mapping blocks to letters, the resulting word must retain the same repeated-subword property.Random interleaving does not preserve this property; recursive structures such as the Thue–Morse sequence are suggested instead.
- Future work: The best known general-case lower bound remains Ω(log n), and constructing a recursive counterexample to the O(log n) conjecture is open.The analysis indicates that candidate hard pairs need scale-invariant factor repetitions.
A Chernoff’s Bound
Chernoff’s bound concerns independent Bernoulli variables and their expected total. It applies when the threshold is at least six times that expectation.
- Xi, for i = 1, . . . , m, are assumed to be i.i.d. Bernoulli random variables with parameter p.
- The expectation parameter is defined as μ = m · p.
- The stated bound applies for any R ≥ 6μ.