An Improved Lower Bound for Separating Words by Permutation Automata

Chen Xu, Kenneth Regan

We prove that some pairs of binary words of every sufficiently large prescribed length $n$ require $\Omega (\log n\log \log n)$ states to separate by a deterministic finite automaton whos…