A superlogarithmic lower bound for deterministic word separation
Source: hexagonmath.org/abs/2611.00314v1
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00314
curl -X POST /api/v1/records/hexagon/2611.00314/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00314/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'