Preset Distinguishing Sequences and Diameter of Transformation Semigroups

Abstract

We investigate the length $\ell (n,k)$ of a shortest preset distinguishing sequence (PDS) in the worst case for a $k$-element subset of an $n$-state Mealy automaton. It was mentioned by Sokolovskii that this problem is closely related to the problem of finding the maximal subsemigroup diameter $\ell ({\mathbf{T}}_n)$ for the full transformation semigroup ${\mathbf{T}}_n$ of an $n$-element set. We prove that $\ell ({\mathbf{T}}_n)=2^n\exp \{\sqrt{\frac{n}{2}\ln n}(1+o(1))\}$ as $n\to \infty$ and, using approach of Sokolovskii, find the asymptotics of ${\log }_2\ell (n,k)$ as $n,k\to \infty$ and $k/n\to a\in (0,1)$.

13 pages, 3 figures, LATA 2015