Cerný type problems and transformation semigroups

M. V. Volkov (Ural State University, Ekaterinburg, Russia)

Suppose that we have a series of ``natural" transformation semigroups $\Sigma(Q)$ assigned to each finite set $Q$. (In general, transformations in $\Sigma(Q)$ can be partial and/or multi-valued or they can even act on a structure naturally determined by $Q$--say, on a vector space spanned by $Q$--rather than on $Q$ itself.) Let $K$ denote the kernel of $\Sigma(Q)$. Clearly, for each subset $\Gamma\subseteq \Sigma(Q)$ such that $\langle\Gamma\rangle\cap K\ne\varnothing$, there exists the least positive integer $k=k(\Gamma)$ such that $\Gamma^k\cap K\ne\varnothing$. By the Cerný problem for the series $\Sigma(Q)$ we understand the problem of determining the maximum value of the numbers $k(\Gamma)$ (if such a maximum exists) as the function of $\vert Q\vert$. For example, we may speak of the Cerný problem for semigroups $B(Q)$ of all binary relations on the set $Q$--it is easy to see that being retold back in the automata-theoretic terms this problem may be naturally thought of as the Cerný problem for non-deterministic finite automata. The well-known mortality problem for matrices and several important problems concerning Markov chains constitute further instances of Cerný type problems in the suggested setting.

In the talk, we mainly concentrate on Cerný type problems for semigroups of transformations that preserve the order (respectively the orientation) of a finite linearly (cyclically) ordered set. We present the results by Eppstein [2] (which seem to be overlooked by researchers in the area) and a few new results by Ananichev and the author.