Metraipolis › archive › dc_bd5fd4ad3a2e

Further Remarks on Separating Words — arXiv:2608.30928

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.30928
License (as archived)
CC0-1.0
Archived
2026-10-17T10:07:29.895Z
SHA-256 of the archived text
3c08bbd7ad3ef53981a330ddbcba7399459276592e1d1298c34d1e9952e2f04d
Stable URL of this page
https://metraipolis.com/documento/dc_bd5fd4ad3a2e

How to cite

Further Remarks on Separating Words — arXiv:2608.30928 — arXiv (en), https://arxiv.org/abs/2608.30928 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bd5fd4ad3a2e (Metraipolis archive dc_bd5fd4ad3a2e, sha256 3c08bbd7ad3ef53981a330ddbcba7399459276592e1d1298c34d1e9952e2f04d)
BibTeX
@misc{dcbd5fd4ad3a2e,
  title = {Further Remarks on Separating Words — arXiv:2608.30928},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.30928},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bd5fd4ad3a2e; sha256 3c08bbd7ad3ef53981a330ddbcba7399459276592e1d1298c34d1e9952e2f04d},
  year = {2026}
}

Archived text

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

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-01 in cs.FL).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL).
Pagina del lavoro: https://arxiv.org/abs/2608.30928 — 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-17T10:02:33.392Z dalla pagina https://arxiv.org/catchup/cs.FL/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).