New answers tagged automata-theory
5
The second section of Robson's "Separating strings with small automata" proves $F(n) = O((n \log n)^{1/2})$. The string sequence $(10^n)^n$ gives a lower bound of $\Omega(n^{1/2})$. If the automaton has $<n$ states then both of the sequences $\delta_0^{\circ m} (\delta_{(10^n)^{n-1}1}(q_0))$ and $\delta_{10^n}^{\circ m}(q_0)$ will reach a cycle ...
Top 50 recent answers are included
