Preset Distinguishing Sequences and Diameter of Transformation Semigroups

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 [

18

] 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\rightarrow \infty $$

and, using approach of Sokolovskii, find the asymptotics of

$$\log _2 \ell (n,k)$$

as

$$n,k\rightarrow \infty $$

and

$$k/n\rightarrow a\in (0,1)$$

.