Slowly Synchronizing Automata with Idempotent Letters of Low Rank

Abstract

We use a semigroup-theoretic construction by Peter Higgins in order to produce, for each even $n$, an $n$-state and 3-letter synchronizing automaton with the following two features: 1) all its input letters act as idempotent selfmaps of rank $\frac{n}{2}$; 2) its reset threshold is asymptotically equal to $\frac{n^2}{2}$. In the revised version a few inaccuracies (spotted by the anonymous referees of the previous version) have been removed and several relevant references have been added.

15 pages, 4 figures