Improved state complexity lower bound for permutation automata separation
An Improved Lower Bound for Separating Words by Permutation Automata
Formal Languages and Automata Theory
Summary
Some pairs of binary words need surprisingly big machines to tell them apart when the machines act by rearranging letters in fixed ways. The authors found that this complexity grows faster than previously known, meaning you need even larger machines to separate certain word pairs as the words get longer. They built special word pairs linked to permutations and used number theory tools to prove this stronger requirement. This shows a more difficult limit on the size of these machines than was known before.
What this means in practice
- •For automata designers: Designers now have a higher proven lower bound on the number of states required for permutation automata separating long binary words, informing practical limits.
- •For cryptographers: Cryptographers can rule out certain efficient permutation-based finite automata constructions when designing state-limited cryptographic protocols involving word distinctions.
A theory result. No direct application yet.
Authors
Chen Xu, Kenneth Regan
Abstract
We prove that some pairs of binary words of every sufficiently large prescribed length $n$ require $Ω(\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 of $\mathfrak{S}_k$ of length $\exp(O(k/\log k))$. This improves the previous lower bound $(3/2-o(1))\log n$ of Bulatov, Karpova, Shur, and Startsev (arXiv:1609.03199). The proof combines a positive-word construction with a cover of permutation orders. Consecutive segments of prime powers reduce the covering problem to enumerating sets of positive integers with bounded sum. The required estimates use the central binomial coefficient and the classical asymptotic formula for partitions into distinct parts. An appendix gives sharper constants and lower-order terms using a greedy cover and a quantitative prime number theorem.