On the separating words problem
Zachary Chase (UCSD)
Monday, October 28th 2024, 2-3pm
Abstract:
We show for any distinct n-bit strings x,y, that there is a deterministic finite automaton on n^{1/3} states that accepts x but not y. This gives a minor improvement to a result of Robson. The methods involve elementary number theory and complex analysis.