Winning Strategies for the Synchronization Game
on Subclasses of Finite Automata^††thanks: Mikhail Volkov was supported by the Ministry of Science and Higher Education of the Russian Federation, project FEUZ-2023-2022.

For a DFA $\mathrsfs{A}=(Q,\Sigma)$, the map $\tau_{a}\colon Q\to Q$ defined by the rule $q\mapsto q{\cdot}a$ is a transformation on the set $Q$.

We denote the transition monoid of a DFA $\mathrsfs{A}=(Q,\Sigma)$ by $T(\mathrsfs{A})$. It is easy to see that any product $\tau_{a_{1}}\tau_{a_{2}}\cdots\tau_{a_{n}}$ is nothing but the transformation $\tau_{w}$ defined by the rule $q\mapsto q{\cdot}w$ where $w$ stands for the word $a_{1}a_{2}\cdots a_{n}$. Thus, the transition monoid $T(\mathrsfs{A})$ can alternatively be defined as the monoid of all transformations on the set $Q$ caused by the action of words over $\Sigma$.

If $\mathrsfs{A}=(Q,\Sigma)$ is a synchronizing DFA and $w$ is a reset word for $\mathrsfs{A}$, then the transformation $\tau_{w}$ is a constant map on $Q$, that is, $Q\tau_{w}=\{q\}$ for a certain $q\in Q$. Thus, the transition monoid of a synchronizing automaton always contains a constant transformation. Conversely, if $\zeta\in T(\mathrsfs{A})$ is a constant transformation, then any word $w$ with $\tau_{w}=\zeta$ is a reset word for $\mathrsfs{A}$ and so $\mathrsfs{A}$ is synchronizing. We see that synchronization is actually a property of the transition monoid of an automaton rather than the automaton itself: for DFAs $\mathrsfs{A}=(Q,\Sigma)$ and $\mathrsfs{A}^{\prime}=(Q,\Sigma^{\prime})$ with the same state set but different input alphabets, the equality $T(\mathrsfs{A})=T(\mathrsfs{A}^{\prime})$ guarantees that $\mathrsfs{A}^{\prime}$ is synchronizing if and only if so is $\mathrsfs{A}$.

We can say a bit more about transition monoids of synchronizing automata, but for this, we first need to recall some concepts of semigroup theory. A nonempty subset $I$ of a semigroup $S$ is called an ideal in $S$ if, for all $s\in S$ and $i\in I$, both products $si$ and $is$ lie in $I$. If $I$ and $J$ are two ideals in $S$, their intersection $I\cap J$ contains any product $ij$ with $i\in I$, $j\in J$. So $I\cap J$ is nonempty, and then it is easy to verify that $I\cap J$ is again an ideal in $S$. Therefore, each finite semigroup $S$ has a least ideal called the kernel of $S$ and denoted $\operatorname{Ker}S$.

The following observation is folklore but we provide a proof for the sake of completeness.

Green [9] defined five important relations on every semigroup $S$, collectively referred to as Green’s relations, of which we need the following three:

• $a\mathrel{\mathfrak{R}}b\Longleftrightarrow{}$ either $a=b$ or $a=bs$ and $b=at$ for some $s,t\in S$;

• $a\mathrel{\mathfrak{L}}\,b\Longleftrightarrow{}$ either $a=b$ or $a=sb$ and $b=ta$ for some $s,t\in S$;

• $a\mathrel{\mathfrak{D}}b\Longleftrightarrow{}$ $a\mathrel{\mathfrak{R}}c$ and $c\mathrel{\mathfrak{L}}b$ for some $c\in S$.

The relations $\mathrel{\mathfrak{R}}$ and $\mathrel{\mathfrak{L}}$ are obviously equivalencies. The definition of ${\mathrel{\mathfrak{D}}}$ means that ${\mathrel{\mathfrak{D}}}$ is the product of $\mathrel{\mathfrak{R}}$ and $\mathrel{\mathfrak{L}}$ as binary relations. As observed in [9], ${\mathrel{\mathfrak{D}}}$ is also the product of $\mathrel{\mathfrak{L}}$ and $\mathrel{\mathfrak{R}}$, and this implies that $\mathrel{\mathfrak{D}}$ is the least equivalence containing both $\mathrel{\mathfrak{R}}$ and $\mathrel{\mathfrak{L}}$.

An element $a$ of a semigroup $S$ is said to be regular if $asa=a$ for some $s\in S$. A $\mathrel{\mathfrak{D}}$-class $D$ is called regular if it contains a regular element. (In this case, every element of $D$ is known to be regular; see [9, Theorem 6].) We denote by $\mathbf{DS}$ the set of all finite semigroups $S$ such that the regular $\mathrel{\mathfrak{D}}$-classes of $S$ are subsemigroups in $S$.

The structure of semigroups $\mathbf{DS}$ is well understood in terms of their decompositions into some basic blocks. As we will use this structural result, we recall the notions involved.

A semilattice is a semigroup satisfying the laws of commutativity $xy=yx$ and idempotency $x^{2}=x$.

We say that a semigroup $S$ is $m$-nilpotent over its kernel ($m$ being a positive integer) if every product of $m$ elements of $S$ belongs to $\operatorname{Ker}S$. We call a semigroup nilpotent over its kernel if it is $m$-nilpotent over its kernel for some $m$. (To a semigroupist, finite semigroups nilpotent over their kernels are familiar as finite Archimedean semigroups.)

The following is a specialization of the equivalence (4c) $\Leftrightarrow$ (1b) in [18, Theorem 3] to finite semigroups¹¹1Theorem 3 in [18] deals with semigroups in which every element has a power that belongs to a subgroup. Every finite semigroup has this property..

In the introduction, we mentioned a few previously known families of A-automata. Now we show that all these families consist of DS-automata so their winning strategies are subsumed by that of Theorem 3.

Theorem 3 generalizes several earlier results on A-automata. Can it be further generalized? This is an interesting question, but it requires specification.

We mentioned in Section 2.1 that synchronization is a property of transition monoids. This is not true for the property of being an A-automaton. Moreover, for every synchronizing DFA $\mathrsfs{A}=(Q,\Sigma)$, there exists an A-automaton $\mathrsfs{A}^{\prime}=(Q,\Sigma^{\prime})$ such that $T(\mathrsfs{A})=T(\mathrsfs{A}^{\prime})$. To see this, let $\Sigma^{\prime}:=\Sigma\cup\{c\}$ where the action of the added letter $c$ coincides with the action of a fixed reset word for $\mathrsfs{A}$. The transformations caused by the letters in $\Sigma^{\prime}$ generate the same submonoid of the monoid of all transformations on the set $Q$ as do the transformations caused by the letters in $\Sigma$. Still, Alice instantly wins the synchronization game on $\mathrsfs{A}^{\prime}$ by choosing the letter $c$ on her first move.

Thus, one cannot hope for a characterization of A-automata in terms of transition monoids. One can, however, try to find new sets $\mathbf{P}$ of finite semigroups such that $\mathbf{DS}\subsetneq\mathbf{P}$ and every synchronizing DFA whose transition monoid lies in $\mathbf{P}$ is an A-automaton.

It is easy to verify that the property of being an A-automaton is inherited by subautomata, homomorphic images, and finite direct products. This suggests looking for sets $\mathbf{P}$ closed under corresponding operations with semigroups. A set of finite semigroups closed under forming finite direct products and taking subsemigroups and homomorphic images is called a pseudovariety; the set $\mathbf{DS}$ is an example of a pseudovariety. Using the notion of a pseudovariety, we can specify a possible direction towards generalizing Theorem 3 as follows:

The 5-element Brandt semigroup $B_{2}$ consists of the following five $2\times 2$-matrices, multiplied according to the usual rule:

The monoid $B_{2}^{1}$ obtained by adding the identity $2\times 2$-matrix to $B_{2}$ is the syntactic monoid of the language $(ab)^{*}$, and hence, the transition monoid of the minimal automaton $\mathrsfs{M}$ of this language (shown below).

It is known that every pseudovariety of finite semigroups not contained in $\mathbf{DS}$ must include the semigroup $B_{2}$ (this fact occurs as Exercise 8.1.6 in [1]; the solution to this exercise follows from the proof of [13, Theorem 3]). Thus, if Bob had a winning strategy on the automaton $\mathrsfs{M}$, then the answer to Question 1 would be ‘No’, and moreover, $\mathbf{DS}$ would be the largest pseudovariety $\mathbf{P}$ with the property that Alice can win the synchronization game on every synchronizing DFA whose transition monoid lies in $\mathbf{P}$. However, it is easy to see that Alice wins on $\mathrsfs{M}$: she can start with choosing $a$; if Bob replies with $a$, he loses, and if he replies with $b$, Alice wins by choosing $b$.

The fact that $\mathrsfs{M}$ is an A-automaton, along with other examples of A-automata beyond the family of DS-automata, indicates that Question 1 might have an affirmative answer. We have a candidate pseudovariety to witness such an answer but its definition requires more structure theory of semigroups than assumed here.

Another question of interest concerns the speed of synchronization for A-automata. When we mentioned in the introduction that A-automata seem more amenable to synchronization, we meant that they tend to have short reset words. Indeed, in all examples we know, an A-automaton with $n$ states admits a reset word of length at most $n-1$. For DFAs in the range of Theorem 3, that is, synchronizing DS-automata, this was established in [3, Theorem 2.6]. The DFA $\mathrsfs{M}$ with 3 states is reset by the words $a^{2}$ and $b^{2}$ of length 2 and hence provides another example. These observations lead to the next question.

Recall that for each $n>2$, there exist synchronizing DFAs with $n$ states whose shortest reset words have length $(n-1)^{2}$; see [6, Lemma 1]. It can be verified that none of these ‘slowly synchronizing’ DFAs are A-automata.