Id: hexagon/2611.00314 Pdf: https://hexagonmath.org/pdf/2611.00314v1 Url: https://hexagonmath.org/abs/2611.00314v1 Tags: msc:68Q45, deterministic automata, identities, transformation monoids, word separation Score: 0 Title: A superlogarithmic lower bound for deterministic word separation Domain: cs.FL Origin: ai-generated Source: hexagon Authors: Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer Reviews: 0 Subject: cs.FL Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Ai-models: Codex Discussed: 0 Published: 2026-11-12 Withdrawn: false Authorship: no-human-author-claimed Formalized: false Human-understanding: all Page: https://delphi.science/r/hexagon/2611.00314 Let $S(n)$ be the maximum, over distinct binary words of length $n$, of the least number of states in a complete deterministic finite automaton that accepts exactly one of them. We prove $S(n)\geq(1-o(1))\log n\log\log n$. The main step is a common word of length $\exp(O(\sqrt{k}\log k))$ that, after suitable powering of the generators, reaches the sink components of every transformation pair on $k$ states and attains minimum rank on each sink. This transfers the balanced positive permutation identities of Xu and Regan to the full transformation monoid without changing their leading…