Reset thresholds in bounded-response sink games
How long can the shortest reset word be in a finite automaton with a fixed sink when one player can force synchronization against bounded replies? A reset word sends every state to the sink. In the k-game, Alice chooses one letter and Bob may reply with fewer than k letters. M(n,k) is the largest reset threshold among n-state automata where Alice can force a reset.
Why it matters and what counts as progress
Why it matters: The game links an adversarial ability to synchronize with the length of a fixed reset word. Sharp bounds show how the allowed reply length restricts the worst case.
What counts as progress: Prove matching upper and lower bounds for M(n,k), extend the known parameter range, or give a counterexample to a proposed formula. Preserve the sink assumption and exact move convention.
How the problem developed
- 26 Jan 2026 · Research framework [1]
Anton E. Lipin and Mikhail V. Volkov Studied adversarial synchronization, supplied endpoint results and lower-bound automata, and conjectured the sharp threshold when k divides n−1.
Claude Opus and GPT-6 Astra, directed by Ben Keene Developed matching upper and lower bounds for k=1 or n≤k+3, including M(5,2)=6. The broader conjecture and the prose strategy interpretation remain separate.
Selected milestones. The later conference chapter was not reviewed in full; no worldwide priority claim is made.
AI contribution
Sharp reset thresholds for bounded-response synchronization games with a sink
For n≥2 and k≥1 with k=1 or n≤k+3, the largest shortest-reset-word length among n-state A_k automata with a fixed sink is M(n,k)=∑_{i=1}^{n−1}⌈i/k⌉. Alice chooses one letter per round and Bob replies with fewer than k letters, including the empty word; A_k means Alice can force a reset. In particular M(k+2,k)=k+2 and M(k+3,k)=k+4 for k≥2, and M(5,2)=6.
Sources
Website timeline
Sharp reset thresholds for bounded-response synchronization games with a sink