Metraipolis › archive › dc_e488bbe51d86

Separating Words with Automata in the Half-adversarial Case — arXiv:2608.28385

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.28385
License (as archived)
CC0-1.0
Archived
2026-10-17T11:57:14.072Z
SHA-256 of the archived text
0ae4701448aa88eb81c18d3f475ce8537dc38979d932c451475f0fc86098a181
Stable URL of this page
https://metraipolis.com/documento/dc_e488bbe51d86

How to cite

Separating Words with Automata in the Half-adversarial Case — arXiv:2608.28385 — arXiv (en), https://arxiv.org/abs/2608.28385 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e488bbe51d86 (Metraipolis archive dc_e488bbe51d86, sha256 0ae4701448aa88eb81c18d3f475ce8537dc38979d932c451475f0fc86098a181)
BibTeX
@misc{dce488bbe51d86,
  title = {Separating Words with Automata in the Half-adversarial Case — arXiv:2608.28385},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.28385},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e488bbe51d86; sha256 0ae4701448aa88eb81c18d3f475ce8537dc38979d932c451475f0fc86098a181},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.28385. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\Omega(\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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-31 in cs.FL).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL).
Pagina del lavoro: https://arxiv.org/abs/2608.28385 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T11:27:34.038Z dalla pagina https://arxiv.org/catchup/cs.FL/2026-08-31?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).