K. Regan

An Improved Lower Bound for Separating Words by Permutation Automata

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 whose letters act as permutations. We obtain this bound by constructing distinct equal-length positive binary words that form an identity o...