The pseudovariety $Com\ast D$ viewed as a power pseudovariety

1. Introduction

The semidirect product on the level of pseudovarieties of semigroups has been widely studied in the past. See [2, Chap. 10] for a survey of results obtained until mid-nineties in this direction. Likewise the power operator on the level of pseudovarieties of semigroups has been the subject of intensive study in the past. See [2, Chap. 11] for an overview of results obtained by that time in this area. From time to time these two routes of research have met up with each other. One particular instance of such a fruitful encounter is represented by the study of locally commutative power pseudovarieties, whose results are summarized in [2, Sec. 11.9]. In this context, the pseudovariety $Com\ast D$ has arisen, which has been previously the object of concern of researchers in the domain of semidirect products of pseudovarieties of semigroups. See [2, Sec. 10.7] in this respect, for example.

Recall yet that $Com$ is the pseudovariety of all commutative semigroups, $D$ is the pseudovariety of all definite semigroups, that is, the pseudovariety of all semigroups whose idempotents act as right zeros and $Com\ast D$ is the pseudovariety of semigroups generated by the class of all semidirect products of commutative semigroups by definite semigroups. An effective characterization of the pseudovariety $Com\ast D$ has been provided by Thérien and Weiss in [10]. Their result actually says that $Com\ast D$ is the pseudovariety of semigroups determined by the pseudoidentity $exfyezf\bumpeq ezfyexf$. See also [2, Sec. 10.7] once again in this regard.

Let $LCom$ be the pseudovariety of all locally commutative semigroups. That is, $LCom$ consists of all finite semigroups S having the property that, for every idempotent e in S, the submonoid $eSe$ of S is a commutative monoid. Yet otherwise stated, $LCom$ is the pseudovariety of semigroups determined by the pseudoudentity $exeye\bumpeq eyexe$. In this context, Almeida has proposed in [1] and in [2, Sec. 11.9] to consider the subpseudovariety $U$ of the pseudovariety $LCom$ determined within $LCom$ by the additional pseudoidentity ${(ef)}^{\omega }exf\bumpeq exf$. It is easy to check that, within $LCom$, the pseudoidentity ${(ef)}^{\omega }exf\bumpeq exf$ is equivalent to the pseudoidentity $exf{(ef)}^{\omega }\bumpeq exf$, which shows that the pseudovariety $U$ is self-dual. In fact, it is straightforward to infer hence that the pseudovariety $U$ consists of all finite semigroups S having the property that, for every idempotents $e,f$ in S, the subsemigroup $eSf$ of S is a commutative monoid which admits the element ${(ef)}^{\omega }$ for its identity.

Furthermore, Almeida considered in [1] and in [2, Sec. 11.9] the power pseudovariety $PU$. Recall that $PU$ is the pseudovariety generated by the class of all power semigroups $\mathcal{𝒫}(S)$, where S are arbitrary semigroups from the pseudovariety $U$. Having this pseudovariety in view, Almeida has shown in [1] and in [2, Sec. 11.9] that the pseudovariety $Com\ast D$ provides an upper bound for the power pseudovariety $PU$. That is, he has established the inclusion $PU\subseteq Com\ast D$, and he has done so by verifying directly that the power semigroups $\mathcal{𝒫}(S)$, for all semigroups S in the pseudovariety $U$, do satisfy the above-mentioned pseudoidentity $exfyezf\bumpeq ezfyexf$. He has also shown, in addition, that, for any pseudovariety $V$ of semigroups, the condition $PV\subseteq Com\ast D$ is equivalent to the condition $V\subseteq U$. Thus $U$ is the largest pseudovariety for which the inclusion $PU\subseteq Com\ast D$ holds. However, the question whether the equality $PU=Com\ast D$ actually holds here has been left open in [2, Sec. 11.9].

The purpose of this paper is to establish the missing inclusion $Com\ast D\subseteq PU$. This is the inclusion that is opposite relative to the one discussed above. In this way, it eventually emerges that, in reality, the equality $PU=Com\ast D$ does hold. Therefore the pseudovariety $Com\ast D$ is indeed a power pseudovariety. It is equal to the pseudovariety $PU$, where $U$ is the pseudovariety introduced above.

In order to achieve the appointed goal, we shall take advantage of the tools furnished by formal language theory. It is a celebrated result in the theory of varieties of recognizable languages attributed to Eilenberg that there are mutually inverse order preserving one-to-one correspondences between the lattice of all pseudovarieties of semigroups and the lattice of all varieties of languages. See [3, Sec. VII.3] for Eilenberg’s original treatment of this subject. Having this in view, we shall let $\mathcal{𝒱}$ be the variety of languages corresponding to the pseudovariety $Com\ast D$, and we shall let $\mathcal{𝒲}$ be the variety of languages corresponding to the pseudovariety $PU$. Then, in our efforts to establish the inclusion $Com\ast D\subseteq PU$, we shall be done if we can show that we have $\mathcal{𝒱}\subseteq \mathcal{𝒲}$. This is exactly what we shall strive for in this paper.

The other tools from formal language theory that we shall make use of include Straubing’s wreath product principle, expounded in detail by Pin and Weil in [7], which makes it possible to underpin the languages appertaining to the variety $\mathcal{𝒱}$ corresponding to the pseudovariety $Com\ast D$, and Straubing’s characterization of languages recognized by power semigroups, obtained in [9], which allows us to handle the languages belonging to the variety $\mathcal{𝒲}$ corresponding to the power pseudovariety $PU$.

2. Preliminaries

All semigroups appearing in this paper, with the exception of free semigroups, will be finite. For every semigroup S, we shall denote by $E(S)$ the set of all idempotents in S. We shall denote by $S^1$ the monoid which is equal to S provided that S already is a monoid, and which is obtained from S by adjoining an identity to it otherwise.

By a pseudovariety of semigroups we shall mean any class of finite semigroups which is closed under the formation of direct products of finite families of semigroups and under the formation of subsemigroups and homomorphic images of semigroups. Such pseudovarieties can be determined by collections of pseudoidentities, as it has been the case on several instances in the previous section. We shall not need the concept of pseudoidentity in its full generality, and so we shall not embark on this subject here. We only mention that, in such a pseudoidentity $u\bumpeq v$, apart from letters like $x,y,z,\dots$ which are reserved for variables that may be substituted by arbitrary elements from a semigroup S in which the pseudoidentity $u\bumpeq v$ is evaluated, also letters like $e,f,g,\dots$ may appear which are reserved for constituents that may be substituted only by idempotents from $E(S)$.

We have met already in the previous section the pseudovariety $D$ of all definite semigroups. This pseudovariety consists of all finite semigroups S having the property that every idempotent in $E(S)$ acts as a right zero in S. Thus $D$ is the pseudovariety determined by the pseudoidentity $xe\bumpeq e$. For every positive integer m, let $D_m$ be the pseudovariety determined by the pseudoidentity $x{y}_1{y}_2\cdots y_m\bumpeq y_1{y}_2\cdots y_m$. Then it turns out that $D={\bigcup }_{m=1}^{\infty }{D}_m$. Later on, we shall also need the pseudovariety $K$ which is dual with respect to the pseudovariety $D$. That is, $K$ consists of all finite semigroups S having the property that every idempotent in $E(S)$ acts as a left zero in S. Thus $K$ is the pseudovariety determined by the pseudoidentity $ex\bumpeq e$. For every positive integer m, let $K_m$ be the pseudovariety determined by the pseudoidentity $x_1{x}_2\cdots x_{m}y\bumpeq x_1{x}_2\cdots x_m$. Then it turns out that $K={\bigcup }_{m=1}^{\infty }{K}_m$.

We shall have to deal in this paper with semidirect products of pseudovarieties of semigroups. To start with, we shall have to work with semidirect products of individual semigroups of the form $S\ast T$, where S and T are arbitrary semigroups. We shall observe here the custom introduced by Almeida at the beginning of [2, Sec. 10.1], according to which, even if T is viewed as a semigroup, if T happens coincidentally to be a monoid, then the underlying left action of T on S giving rise to the semidirect product $S\ast T$ should be left unitary. With that, if $V$ and $W$ are any pseudovarieties of semigroups, then the semidirect product $V\ast W$ of these two pseudovarieties is defined to be the pseudovariety of semigroups generated by the class of all semidirect products of the form $S\ast T$, where S is a semigroup from $V$ and T is a semigroup from $W$, observing the custom regarding the underlying left action of T on S mentioned above. It is easy to verify that this semidirect product $V\ast W$ consists, in fact, of all divisors of the semidirect products $S\ast T$ just described.

Aside from ordinary semigroups, we shall have to deal also with transformation semigroups. To begin with, let P be a finite set. We shall denote by ${\mathcal{𝒯}}_P$ the monoid of all transformations of the set P. Note that we shall let the transformations from ${\mathcal{𝒯}}_P$ act on the elements of the set P on the right. That is, given an element $p\in P$ and a transformation $\tau$ of the set P, we shall denote by $p\tau$ the result of the application of $\tau$ on p. Therefore the composition of transformations from ${\mathcal{𝒯}}_P$ should be interpreted accordingly, that is, it has to be read from the left to the right. Having this at hand, by a transformation semigroup we shall mean any pair $X=(P,S)$ where P is a finite set and S is a subsemigroup of the monoid ${\mathcal{𝒯}}_P$ of all transformations of the set P. The set P will be called the underlying set of X and the semigroup S will be called the action semigroup of X.

In accordance with [3, Sec. I.10] or [2, Sec. 10.1], we introduce the operation of wreath product of transformation semigroups in the following manner. Let $X=(P,S)$ and $Y=(Q,T)$ be transformation semigroups. The wreath product $X\circ Y$ of these transformation semigroups is the transformation semigroup having for its underlying set the cartesian product $P\times Q$ and having for its action semigroup the semidirect product $S^Q\ast T$ of the semigroup $S^Q$ of all functions of Q into S by the semigroup T determined by the left action of T on $S^Q$ given by the following formula. For every transformation $\tau \in T$ and for every function $f:Q\to S$, the function ${}^{\tau }f:Q\to S$ is defined by the rule $q({}^{\tau }f)=(q\tau )f$, for every $q\in Q$, where functions are written on the right of their arguments. In order to keep the promise that $X\circ Y$ so determined should indeed be a transformation semigroup, it remains to observe that the action semigroup $S^Q\ast T$ may be viewed as a subsemigroup of the monoid ${\mathcal{𝒯}}_{P\times Q}$ in the following way. For every function $f:Q\to S$ and for every transformation $\tau \in T$, the element $(f,\tau )$ of $S^Q\ast T$ determines a transformation ${\varrho }_{(f,\tau )}$ of the set $P\times Q$ sending every pair $(p,q)$ from $P\times Q$ to the pair $(p(qf),q\tau )$. Then the assignment $(f,\tau )\mapsto {\varrho }_{(f,\tau )}$ is an embedding of $S^Q\ast T$ into ${\mathcal{𝒯}}_{P\times Q}$. Therefore the semigroup $S^Q\ast T$ may indeed be treated as a subsemigroup of the monoid ${\mathcal{𝒯}}_{P\times Q}$. In this way, $X\circ Y$ becomes again a transformation semigroup.

However, the operation of wreath product $X\circ Y$ of transformation semigroups $X=(P,S)$ and $Y=(Q,T)$ so introduced has a certain defect. It appears when the semigroup T is a monoid, but the transformation representing the identity of T is not equal to the identity on the set Q. In such a case, the left action of T on $S^Q$ determined above need not be left unitary. And this is in conflict with our previous requirements regarding the underlying left action of the semigroup T on $S^Q$, if the semidirect product $S^Q\ast T$ has to be properly defined. Having this circumstance in view, we have introduced in [4] the concept of proper transformation semigroups. A transformation semigroup $X=(P,S)$ is said to be proper if either S is not a monoid, or S is a monoid and the identity of S acts as the identity on the set P. If we restrict the scope of the above definition of wreath products only to proper transformation semigroups, then the difficulty that we have encountered above disappears. And it is not too hard to verify that the wreath product $X\circ Y$ of two proper transformation semigroups X and Y is a proper transformation semigroup again.

Most frequent examples of proper transformation semigroups are the right regular representations of ordinary semigroups. For any semigroup S and for every element $s\in S$, we may consider the transformation ${\rho }_s:S^1\to S^1$ which maps every element $t\in S^1$ to the element $ts$. Then the mapping $S\to {\mathcal{𝒯}}_{S^1}$ given by the formula $s\mapsto {\rho }_s$ is an embedding of the semigroup S into ${\mathcal{𝒯}}_{S^1}$. In this way, a proper transformation semigroup $(S^1,S)$ arises, which is called the right regular representation of S. Thus, for any semigroups S and T, we may consider the wreath product $(S^1,S)\circ (T^1,T)$ of the right regular representations of these semigroups. This wreath product is again a proper transformation semigroup and its action semigroup $S^{T^1}\ast T$ is just the standard wreath product $S\circ T$ of the semigroups S and T. It is a familiar fact that, for any semigroups S and T and for every left action of T on S, where the custom regarding the left actions that has been introduced above is observed, the semidirect product $S\ast T$ determined by this left action can be embedded into the wreath product $S\circ T$.

As a consequence, we see that, for any two pseudovarieties of semigroups $V$ and $W$, the semidirect product $V\ast W$ of these pseudovarieties is equal to the pseudovariety generated by the class of all wreath products of the form $S\circ T$, where S is a semigroup in $V$ and T is a semigroup in $W$. In fact, this semidirect product $V\ast W$ can be obtained as the class of all divisors of the wreath products $S\circ T$ just described. Finally note that, on the other hand, the semidirect product $V\ast W$ contains all action semigroups $S^Q\ast T$ of the wreath products $X\circ Y$ of arbitrary proper transformation semigroups $X=(P,S)$ and $Y=(Q,T)$, where the semigroup S belongs to $V$ and the semigroup T belongs to $W$.

We close this section with a few remarks on power semigroups and power pseudovarieties. For any semigroup S, we denote by $\mathcal{𝒫}(S)$ the set of all subsets of S equipped with the usual multiplication. In this way, $\mathcal{𝒫}(S)$ becomes a semigroup, called the power semigroup of S. For any pseudovariety $V$ of semigroups, we let $PV$ be the pseudovariety generated by all semigroups of the form $\mathcal{𝒫}(S)$, where S stands for arbitrary semigroups from $V$. Note that, if $V$ contains a non-trivial monoid, then $PV$ can be actually obtained as the class of all semigroups T that divide some semigroup of the form $\mathcal{𝒫}(S)$, where S is any semigroup in $V$. The pseudovariety $PV$ arising in this way from $V$ is called the power pseudovariety of $V$.

3. Formal Language Theory

Let A be a finite set. Within the context of the theory of formal languages, we shall say that A is an alphabet. Elements of this set A will be called letters. By $A^{\ast }$ we shall denote the free monoid on the set A, and by $A^{+}$ we shall denote the free semigroup on the set A. Elements of $A^{\ast }$ will be called words in the alphabet A. By 1 we shall denote the empty word, that is, the identity of the monoid $A^{\ast }$. By a language over the alphabet A we shall mean any set of words in the alphabet A, that is, any subset L of the free monoid $A^{\ast }$. Later on, however, we shall have to deal with languages L that will be subsets of the free semigroup $A^{+}$, that is, such languages L will not contain the empty word 1.

By an automaton we shall mean any triplet $\mathcal{𝒜}=(Q,A,\cdot )$ where Q is a finite set of states, A is an alphabet and ⋅ is a function $Q\times A\to Q$. One can extend this function ⋅ to a function $Q\times A^{\ast }\to Q$, also denoted by ⋅, by putting successively $q\cdot 1=q$ and $q\cdot (wa)=(q\cdot w)\cdot a$, for all $q\in Q$, $w\in A^{\ast }$ and $a\in A$.

Let $L\subseteq A^{\ast }$ be a language and let $\mathcal{𝒜}=(Q,A,\cdot )$ be an automaton. We shall say that the language L is recognized by the automaton $\mathcal{𝒜}$ if there exist a state $q_0\in Q$, called the initial state and a subset $F\subseteq Q$ of states, called the set of terminal states, such that $L=\{w\in A^{\ast }:q_0\cdot w\in F\}$. Languages that are recognized by some automaton are called recognizable languages.

If we have to deal only with languages $L\subseteq A^{+}$, then a slightly different notion of recognizability of such languages by means of automata suggests itself. Let again $\mathcal{𝒜}=(Q,A,\cdot )$ be an automaton. Then we may say that the language L is recognized by the automaton $\mathcal{𝒜}$ if there exist an initial state $q_0\in Q$ and a subset $F\subseteq Q$ of terminal states such that $L=\{w\in A^{+}:q_0\cdot w\in F\}$. But if a language $L\subseteq A^{+}$ is recognized by an automaton $\mathcal{𝒜}$ in this latter sense, then it can also be recognized by an automaton $\overline{\mathcal{𝒜}}$ in the former sense, where the automaton $\overline{\mathcal{𝒜}}$ is only slightly adapted from $\mathcal{𝒜}$. For languages $L\subseteq A^{+}$, we shall usually have in view just this latter altered notion of recognizability.

One can consider quite a lot of operations on the languages over the given alphabet A. In the first place these are the standard Boolean operations, namely the union $K\cup L$ and the intersection $K\cap L$ of any two languages $K,L\subseteq A^{\ast }$, and the complement $A^{\ast }\backslash L$ of a language $L\subseteq A^{\ast }$. Further operations that one may consider are the product $KL$ of two languages $K,L\subseteq A^{\ast }$ and the star $L^{\ast }$ of a language $L\subseteq A^{\ast }$. The product $KL$ is defined to be the language $KL=\{uw\in A^{\ast }:u\in K,w\in L\}$. The star $L^{\ast }$ is defined to be the submonoid of $A^{\ast }$ generated by the language L.

We proceed to introduce another family of languages, namely the so-called rational languages. The class of all rational languages over the alphabet A is defined to be the smallest subclass of the class of all languages over the alphabet A which contains all finite languages and is closed under the formation of unions of pairs of languages, of products of pairs of languages and of stars of languages. Now the classical Kleene’s theorem asserts that a language over an alphabet A is recognizable if and only if it is rational. See [5, Sec. 6.3], for example.

Given an automaton $\mathcal{𝒜}=(Q,A,\cdot )$, every word $w\in A^{\ast }$ determines a transformation ${\zeta }_w$ of the set Q given by the rule $q\mapsto q\cdot w$, for every $q\in Q$. The transformations ${\zeta }_w$ of the set Q, for all words $w\in A^{\ast }$, form a submonoid of the monoid ${\mathcal{𝒯}}_Q$ of all transformations of the set Q. This submonoid, which we shall denote by $M(\mathcal{𝒜})$, is called the transition monoid of the automaton $\mathcal{𝒜}$. Note that this monoid $M(\mathcal{𝒜})$ is generated by the set of all transformations of the set Q of the form ${\zeta }_a$, for arbitrary elements $a\in A$. If we take in the above considerations only the transformations ${\zeta }_w$ of the set Q such that $w\in A^{+}$, then these transformations will form a subsemigroup of the monoid ${\mathcal{𝒯}}_Q$. This subsemigroup, which we shall denote by $S(\mathcal{𝒜})$, is called the transition semigroup of the automaton $\mathcal{𝒜}$. Note also that then the pair $(Q,S(\mathcal{𝒜}))$ forms a transformation semigroup. Later on, by the transition semigroup of the automaton $\mathcal{𝒜}$ we shall often mean just this transformation semigroup.

From now on, we shall confine ourselves to languages $L\subseteq A^{+}$. So let $L\subseteq A^{+}$ be such a language, let S be a finite semigroup, and let $\phi :A^{+}\to S$ be a homomorphism of semigroups. We shall say that the language L is recognized by the homomorphism $\phi$ if there exists a subset $P\subseteq S$ such that $L={\phi }^{-1}(P)$. If this is the case, then we shall also say that the language L is recognized by the semigroup S. It turns out that a language $L\subseteq A^{+}$ is recognized by a semigroup in this way if and only if L is recognized by an automaton, as described above. Indeed, if the language $L\subseteq A^{+}$ is recognized by a semigroup S and if $\phi :A^{+}\to S$ is the underlying homomorphism of semigroups, then L is recognized by the automaton ${\mathcal{𝒜}}_S=(S^1,A,\cdot )$, where the function ⋅ is determined, for any $s\in S^1$ and any $a\in A$, by the formula $s\cdot a=s\phi (a)$. On the other hand, if the language $L\subseteq A^{+}$ is recognized by an automaton $\mathcal{𝒜}=(Q,A,\cdot )$, then L is recognized by the transition semigroup $S(\mathcal{𝒜})$ of this automaton.

The possibility to treat in this manner the notion of recognizability of languages over an alphabet A in terms of homomorphisms of the free semigroup $A^{+}$ into finite semigroups makes it possible to verify easily the following statements. If $L\subseteq A^{+}$ is a recognizable language, then its complement $A^{+}\backslash L$ is also a recognizable language. If $K,L\subseteq A^{+}$ are recognizable languages, then their union $K\cup L$ and their intersection $K\cap L$ are also recognizable languages.

It is also worth noticing that if $L\subseteq A^{+}$ is a language that can be recognized by a semigroup S and if T is a semigroup such that S divides T, then L can also be recognized by T.

Let again $L\subseteq A^{+}$ be a language. We shall say that this language L is recognized by a transformation semigroup $X=(Q,S)$ if there exist a homomorphism of semigroups $\phi :A^{+}\to S$, a state $q_0\in Q$, called the initial state, and a subset $F\subseteq Q$ of states, called the set of terminal states, such that $L=\{w\in A^{+}:q_0\phi (w)\in F\}$. As before, it turns out that a language $L\subseteq A^{+}$ is recognized by a transformation semigroup in the way just specified if and only if L is recognized by an automaton in the way described above. Namely, if the language $L\subseteq A^{+}$ is recognized by a transformation semigroup $X=(Q,S)$ and if $\phi :A^{+}\to S$ is the underlying homomorphism of semigroups, then L is recognized by the automaton ${\mathcal{𝒜}}_X=(Q,A,\cdot )$, where the function ⋅ is determined, for any $q\in Q$ and any $a\in A$, by the formula $q\cdot a=q\phi (a)$. On the other hand, if the language $L\subseteq A^{+}$ is recognized by an automaton $\mathcal{𝒜}=(Q,A,\cdot )$, then L is recognized by the transition semigroup $(Q,S(\mathcal{𝒜}))$ of this automaton.

Also the following notes on the various notions of recognizability will come in handy. If a language $L\subseteq A^{+}$ is recognized by a transformation semigroup $X=(Q,S)$, then L is recognized by the transformation semigroup $(S^1,S)$. The latter semigroup, which is the right regular representation of the semigroup S, is itself a proper transformation semigroup. It is also easy to see that a language $L\subseteq A^{+}$ is recognized by a semigroup S if and only if L is recognized by its right regular representation $(S^1,S)$.

If $X=(Q,S)$ is a transformation semigroup and if $L\subseteq A^{+}$ is a language that can be recognized by the semigroup S, then L is a Boolean combination of languages over the alphabet A that can be recognized by X. Indeed, if $\phi :A^{+}\to S$ is a homomorphism and if $P\subseteq S$ is a subset such that $L={\phi }^{-1}(P)$, then it turns out that $L={\bigcup }_{\tau \in P}{\bigcap }_{q\in Q}\{w\in A^{+}:q\phi (w)=q\tau \}$. The latter languages are clearly recognized by X.

There are plenty of other operations on the languages over various alphabets A. For example, given a language $L\subseteq A^{+}$ and a word $u\in A^{+}$, one can define the left quotient $u^{-1}L$ and the right quotient $L{u}^{-1}$ of the language L relative to the word u as the languages $u^{-1}L=\{w\in A^{+}:uw\in L\}$ and $L{u}^{-1}=\{w\in A^{+}:wu\in L\}$. As previously, if $L\subseteq A^{+}$ is a recognizable language and $u\in A^{+}$ is any word, then the left quotient $u^{-1}L$ and the right quotient $L{u}^{-1}$ are recognizable languages, as well.

Another operation on languages over distinct alphabets A and B is that of taking inverse images of languages over B with respect to various homomorphisms of free semigroups $A^{+}\to B^{+}$. Thus let $L\subseteq B^{+}$ be a language and let $\psi :A^{+}\to B^{+}$ be a homomorphism of free semigroups. Then one may consider the inverse image ${\psi }^{-1}(L)$ of the language L with respect to $\psi$. Then, of course, ${\psi }^{-1}(L)\subseteq A^{+}$. And once again, if L is a recognizable language over B, then ${\psi }^{-1}(L)$ turns out to be a recognizable language over A.

Let $L\subseteq A^{+}$ be any language. We shall say that a congruence $\approx$ on the free semigroup $A^{+}$ saturates the language L if L is a union of certain classes of the partition $A^{+}/\approx$. There exists the coarsest congruence ${\sim }_L$ on $A^{+}$ which saturates the language L. We will call this congruence ${\sim }_L$ the syntactic congruence of the language L. It is given, for all words $u,v\in A^{+}$, by the formula

In this way, the quotient semigroup $A^{+}/{\sim }_L$ arises. This quotient semigroup $A^{+}/{\sim }_L$ will be called the syntactic semigroup of the language L. In general, this semigroup $A^{+}/{\sim }_L$ need not be finite. However, it turns out that the language $L\subseteq A^{+}$ is recognizable if and only if its syntactic semigroup $A^{+}/{\sim }_L$ is finite. If this is the case, then the language L is recognized by its syntactic semigroup $A^{+}/{\sim }_L$. Moreover, whenever S is any semigroup such that L is recognized by S, then the syntactic semigroup $A^{+}/{\sim }_L$ divides S.

Now we are ready to evoke the celebrated Eilenberg’s theorem relating to each other pseudovarieties of finite semigroups and varieties of recognizable languages. Recall once again that we confine ourselves here to recognizable languages $L\subseteq A^{+}$, for various alphabets A. Within this framework, this theorem has been presented already by Eilenberg in [3, Sec. VII.3]. Another exposition of this result has been provided by Pin in [6, Sec. 2.2]. The other version of this theorem involving pseudovarieties of finite monoids and recognizable languages $L\subseteq A^{\ast }$ has been furnished, aside from [3] and [6], also by Lallement in [5, Sec. 6.5].

We begin with yet another definition. By a class of recognizable languages we shall mean any mapping $\mathcal{𝒞}$ assigning to every alphabet A a set $A^{+}\mathcal{𝒞}$ of recognizable languages over A. (All of these languages are assumed to be subsets of $A^{+}$.) If $\mathcal{𝒞}$ and $\mathcal{𝒟}$ are two classes of recognizable languages, then we shall write $\mathcal{𝒞}\subseteq \mathcal{𝒟}$ if, for every alphabet A, we have the inclusion $A^{+}\mathcal{𝒞}\subseteq A^{+}\mathcal{𝒟}$. In this way, a partial order on the family of all classes of recognizable languages is introduced.

By a variety of languages we shall mean any class $\mathcal{𝒱}$ of recognizable languages such that the following conditions are satisfied:

(1)	For every alphabet A, the set $A^{+}\mathcal{𝒱}$ is a Boolean algebra, that is, $A^{+}\mathcal{𝒱}$ is closed with respect to the operation of set theoretical complement of languages (relative to the base set $A^{+}$) and with respect to the operations of set theoretical union and intersection of pairs of languages.
(2)	For every alphabet A, for every language L in $A^{+}\mathcal{𝒱}$ and for every element $a\in A$, also the languages $a^{-1}L$ and $L{a}^{-1}$ belong to $A^{+}\mathcal{𝒱}$.
(3)	Whenever A and B are alphabets and $\psi :A^{+}\to B^{+}$ is a homomorphism of free semigroups, then the preimage ${\psi }^{-1}(L)$ of any language L from $B^{+}\mathcal{𝒱}$ belongs to $A^{+}\mathcal{𝒱}$.

Let now $V$ be any pseudovariety of semigroups. We assign to $V$ a class of recognizable languages $\mathcal{𝒱}$ in the following way. For every alphabet A, we let $A^{+}\mathcal{𝒱}$ be the set of all languages $L\subseteq A^{+}$ having the property that the syntactic semigroup $A^{+}/{\sim }_L$ belongs to $V$. Then $\mathcal{𝒱}$ is a variety of languages.

We may also proceed the other way round. Let $\mathcal{𝒱}$ be any variety of languages. We assign to $\mathcal{𝒱}$ a pseudovariety $V$ of semigroups as follows. We let $V$ be the pseudovariety generated by all syntactic semigroups of the form $A^{+}/{\sim }_L$, where A is any alphabet and L is any language from $A^{+}\mathcal{𝒱}$.

Then we may formulate the announced Eilenberg’s theorem.

Theorem 3.1. The assignments $V\mapsto \mathcal{𝒱}$ and $\mathcal{𝒱}\mapsto V$ described above determine mutually inverse order preserving one-to-one correspondences between the lattice of all pseudovarieties of semigroups and the partially ordered family of all varieties of languages.

Of course, it hence ensues immediately that also the partially ordered family of all varieties of languages forms a lattice.

In the continuation of this section, we proceed to explain the aforementioned Straubing’s wreath product principle making it possible to handle languages recognized by semigroups that belong to the semidirect products of couples of pseudovarieties of semigroups. As the original source of these ideas, the paper [8] of Straubing is usually being quoted. But it is not straightforward to identify this principle in that paper. Our exposition in this paper will follow closely that of Pin and Weil in [7, Sec. 3], where they have drawn it up for ordered semigroups. The unordered version of these results hence follows as a special case. Besides, in the course of our exposition that we offer here, we shall try to fix some shortcomings that have appeared in [7].

By a sequential transducer we shall mean a machine which can be formally described as any sextuplet $\mathcal{𝒯}=(Q,A,B,q_0,\cdot ,\ast )$, where Q is a finite set of states, A is an alphabet called the input alphabet, B is another alphabet called the output alphabet, $q_0\in Q$ is the initial state, ⋅ is a function $Q\times A\to Q$ called the transition function, and ∗ is a function $Q\times A\to B^{\ast }$ called the output function. Thus the triplet $\mathcal{𝒜}=(Q,A,\cdot )$ is an automaton, and hence the transition function ⋅ can be extended to a function $Q\times A^{\ast }\to Q$, also denoted by ⋅, in the manner described previously. In addition, the output function ∗ can be extended to a function $Q\times A^{\ast }\to B^{\ast }$, also denoted by ∗, by putting successively $q\ast 1=1$ and $q\ast (wa)=(q\ast w)((q\cdot w)\ast a)$, for all $q\in Q$, $w\in A^{\ast }$ and $a\in A$. The function realized by the given sequential transducer $\mathcal{𝒯}$ is the function $\varsigma :A^{\ast }\to B^{\ast }$ defined by the formula $\varsigma (w)=q_0\ast w$, for all words $w\in A^{\ast }$. Finally, given two alphabets A and B, by a sequential function we shall mean any function $\sigma :A^{\ast }\to B^{\ast }$ which can be realized by a sequential transducer of the form $\mathcal{𝒯}=(Q,A,B,q_0,\cdot ,\ast )$. Having all that at hand, and arguing in quite the same way as in [7, Sec. 3.1], we arrive at the following result.

Theorem 3.2. Let A and B be any alphabets and let $\sigma :A^{\ast }\to B^{\ast }$ be a sequential function realized by a sequential transducer $\mathcal{𝒯}=(Q,A,B,q_0,\cdot ,\ast )$. Let $Y=(Q,T)$ be the transition semigroup of the underlying automaton $\mathcal{𝒜}=(Q,A,\cdot )$. Let $Z=(Q,U)$ be any proper transformation semigroup such that $T\subseteq U$. If $L\subseteq B^{+}$ is a language recognized by a proper transformation semigroup $X=(P,S),$ then the language ${\sigma }^{-1}(L)\subseteq A^{+}$ is recognized by the wreath product $X\circ Z$ of the transformation semigroups X and Z.

Let A be an alphabet, let T be a finite semigroup, and let $\phi :A^{+}\to T$ be a homomorphism of semigroups. We shall associate with this homomorphism $\phi$ a sequential transducer ${\mathcal{𝒯}}_{\phi }$ which we shall construct in the following way. We set $B_T=T^1\times A$. Then we put ${\mathcal{𝒯}}_{\phi }=(T^1,A,B_T,1,\cdot ,\ast )$, where the transition function $\cdot :T^1\times A\to T^1$ is given, for each $t\in T^1$ and $a\in A$, by the formula $t\cdot a=t\phi (a)$, and the output function $\ast :T^1\times A\to B_T^{\ast }$ is given, again for each $t\in T^1$ and $a\in A$, by the formula $t\ast a=(t,a)$. The sequential function ${\sigma }_{\phi }:A^{\ast }\to B_T^{\ast }$ realized by this sequential transducer ${\mathcal{𝒯}}_{\phi }$ will be called the sequential function associated with the homomorphism $\phi$. Then it is easy to verify that, for any positive integer h and for arbitrary elements $a_1,a_2,\dots ,a_h\in A$, the equality

holds.

Note that, when constructing the sequential transducer ${\mathcal{𝒯}}_{\phi }$, in comparison with the opening passage of [7, Sec. 3.2], we do not assume here the homomorphism $\phi :A^{+}\to T$ to be surjective. Therefore also the transition semigroup of the underlying automaton ${\mathcal{𝒜}}_{\phi }=(T^1,A,\cdot )$ need not be equal to the entire transformation semigroup $(T^1,T)$. But these properties are not exploited in the subsequent reasonings in [7, Sec. 3.2]. Thus we can manage without these properties.

Let now $X=(P,S)$ and $Y=(Q,T)$ be two proper transformation semigroups, let $X\circ Y=(P\times Q,S^Q\ast T)$ be the wreath product of these semigroups, and let $L\subseteq A^{+}$ be a language recognized by the transformation semigroup $X\circ Y$. This means that there exist a state $(p_0,q_0)\in P\times Q$, a subset $F\subseteq P\times Q$ and a homomorphism $\eta :A^{+}\to S^Q\ast T$ such that $L=\{w\in A^{+}:(p_0,q_0)\eta (w)\in F\}$. Let $\pi$ denote the natural projection from $S^Q\ast T$ onto T, which is given by $\pi (f,t)=t$, for all $f:Q\to S$ and all $t\in T$. Then put $\phi =\pi \circ \eta$. Thus $\phi$ is a homomorphism of $A^{+}$ into T. Now, as in the last paragraph but one, we may associate with $\phi$ the sequential transducer ${\mathcal{𝒯}}_{\phi }=(T^1,A,B_T,1,\cdot ,\ast )$ and the sequential function ${\sigma }_{\phi }:A^{\ast }\to B_T^{\ast }$ realized by this sequential transducer. In this situation, the arguments assembled in [7, Sec. 3.2] can be applied. It is, however, important to note in this connection that the identity of the monoid $T^1$ can be required to act as the identity on the set Q. The fact that this is a feasible requirement follows from our assumption that $Y=(Q,T)$ is a proper transformation semigroup. With this amendment, proceeding otherwise as in [7, Sec. 3.2], for the above language L we obtain the following statement.

Theorem 3.3. The language $L\subseteq A^{+}$ is a finite union of languages of the form $M\cap {\sigma }_{\phi }^{-1}(N),$ where $M\subseteq A^{+}$ is a language recognized by the homomorphism $\phi$ and $N\subseteq B_T^{+}$ is a language recognized by the transformation semigroup X.

From Theorems 3.2 and 3.3 it is easy to deduce the following consequence. This result, which will be of crucial importance in the following section, has also its counterpart in [7, Sec. 3.2]. However, since the respective arguments in [7] must be viewed as virtually flawed, we provide a full proof below.

Corollary 3.4. Let $V$ and $W$ be two pseudovarieties of semigroups, let $\mathcal{𝒱}$ and $\mathcal{𝒲}$ be the varieties of languages associated with the pseudovarieties $V$ and $W,$ respectively, and let $\mathcal{𝒵}$ be the variety of languages associated with the semidirect product $V\ast W$ of the pseudovarieties $V$ and $W$. Then, for every alphabet A, the collection of languages $A^{+}\mathcal{𝒵}$ is the smallest Boolean algebra containing all languages from $A^{+}\mathcal{𝒲}$ and all languages of the form ${\sigma }_{\phi }^{-1}(N),$ where $\phi :A^{+}\to T$ is a homomorphism of $A^{+}$ into a semigroup $T\in W,$${\sigma }_{\phi }$ is the sequential function associated with $\phi ,$ and N is any language from $B_T^{+}\mathcal{𝒱}$.

Proof. Clearly, the collection $A^{+}\mathcal{𝒵}$ is a Boolean algebra and it contains all languages from $A^{+}\mathcal{𝒲}$. We shall show that it also contains all languages of the above form ${\sigma }_{\phi }^{-1}(N)$. Let ${\mathcal{𝒯}}_{\phi }=(T^1,A,B_T,1,\cdot ,\ast )$ be the sequential transducer associated with $\phi$. Then ${\sigma }_{\phi }:A^{\ast }\to B_T^{\ast }$ is the sequential function realized by this sequential transducer. Let $Y=(T^1,R)$ be the transition semigroup of the underlying automaton ${\mathcal{𝒜}}_{\phi }=(T^1,A,\cdot )$. Then R is a subsemigroup of T, and the right regular representation $Z=(T^1,T)$ of the semigroup T is a proper transformation semigroup. Recall also that $T\in W$. The language N is recognized by a proper transformation semigroup $X=(P,S)$ such that $S\in V$. Now, applying Theorem 3.2, we come to the conclusion that the language ${\sigma }_{\phi }^{-1}(N)$ is recognized by the wreath product $X\circ Z$. Consequently, this language ${\sigma }_{\phi }^{-1}(N)$ is recognized by the action semigroup of the wreath product $X\circ Z$. But this action semigroup is equal to the semidirect product $S^{T^1}\ast T$, and so it belongs to the pseudovariety $V\ast W$. Therefore the language ${\sigma }_{\phi }^{-1}(N)$ indeed belongs to $A^{+}\mathcal{𝒵}$.

On the other hand, we have seen in the previous section (see the last paragraph but one in that section) that the semidirect product $V\ast W$ of the given pseudovarieties is obtained as the class of all divisors of the action semigroups $S^Q\ast T$ of the wreath products $X\circ Y$ of arbitrary proper transformation semigroups $X=(P,S)$ and $Y=(Q,T)$ such that $S\in V$ and $T\in W$. Furthermore, according to what we have seen previously in this section, every language over the alphabet A which is recognized by any divisor of such an action semigroup $S^Q\ast T$ must be recognized already by this action semigroup itself, and every language over the alphabet A which is recognized by such an action semigroup $S^Q\ast T$ is a Boolean combination of languages over the alphabet A that can be recognized by the initial wreath product $X\circ Y$. Thus it remains to show that every language over the alphabet A which can be recognized by any wreath product $X\circ Y$ of the mentioned form belongs to the Boolean algebra generated by the languages from $A^{+}\mathcal{𝒲}$ and by the languages of the above form ${\sigma }_{\phi }^{-1}(N)$. But this follows immediately from Theorem 3.3. □

Now we approach the characterization of languages which can be recognized by the semigroups in the power pseudovariety $PV$, for any given pseudovariety of semigroups $V$. The result that we are going to present here has been obtained by Straubing in [9].

Let A and B be two alphabets and let $𝜗:A^{+}\to B^{+}$ be a homomorphism of semigroups. We say that this homomorphism $𝜗$ is length preserving if the inclusion $𝜗(A)\subseteq B$ holds. Then, for every word $u\in A^{+}$, the length of the word $𝜗(u)$ is the same as that of u. Then the following statement holds.

Theorem 3.5. Let $V$ be any pseudovariety of semigroups, let $\mathcal{𝒱}$ be the variety of languages associated with $V,$ and let $\mathcal{𝒲}$ be the variety of languages associated with the power pseudovariety $PV$. Then, for every alphabet B, the collection of languages $B^{+}\mathcal{𝒲}$ is the smallest Boolean algebra containing all languages of the form $𝜗(M),$ where M is any language from $A^{+}\mathcal{𝒱}$ for some alphabet A, and $𝜗:A^{+}\to B^{+}$ is a length preserving homomorphism.

We conclude this section with a characterization of languages that are recognized by commutative semigroups. That is, we shall characterize the languages belonging to the variety of languages $\mathcal{𝒞}om$ that is associated to the pseudovariety $Com$ of all commutative semigroups. This result comes from [6, Sec. 2.3].

Let A be an alphabet, let $w\in A^{+}$ be a word and let $a\in A$ be a letter. We denote by $|w{|}_a$ the number of occurrences of the letter a in the word w. For every positive integer n and for every $k\in \{0,1,2,\dots ,n-1\}$, consider the language

Then $K(a,k,n)$ is a recognizable language. Indeed, let ${\mathbb{Z}}_n$ be the additive group of integers modulo n and let ${\phi }_a:A^{+}\to {\mathbb{Z}}_n$ be the homomorphism assigning to every word $w\in A^{+}$ the number $|w{|}_a$ taken modulo n. Then we have $K(a,k,n)={\phi }_a^{-1}(k)$. Since obviously ${\mathbb{Z}}_n\in Com$, we hence see that $K(a,k,n)\in A^{+}\mathcal{𝒞}om$.

Furthermore, for every non-negative integer r, consider the language

Then $L(a,r)$ is also a recognizable language. Indeed, let n be any positive integer greater than r and let ${\mathbb{Z}}_{1,n}$ be the cyclic monoid of order $n+1$ and period 1. This means that if g is the generator, then the elements of ${\mathbb{Z}}_{1,n}$ are $1,g,g^2,\dots ,g^n$ with the convention that $g^{n+1}=g^n$. Then let ${\psi }_a:A^{+}\to {\mathbb{Z}}_{1,n}$ be the homomorphism assigning to every word $w\in A^{+}$ the element $g^{|w{|}_a}$. Here $g^0$ is to be understood as 1. Then we have $L(a,r)={\psi }_a^{-1}(g^r)$. Since clearly ${\mathbb{Z}}_{1,n}\in Com$, we see that $L(a,r)\in A^{+}\mathcal{𝒞}om$.

From these notes and from the last corollary in [6, Sec. 2.3] we infer the following description of the recognizable languages forming the variety of languages $\mathcal{𝒞}om$ that is associated to the pseudovariety $Com$ of all commutative semigroups.

Proposition 3.6. For every alphabet A, the collection of languages $A^{+}\mathcal{𝒞}om$ is the smallest Boolean algebra containing all languages over A of the form K(a,k,n), where $a\in A,$ n is a positive integer, and $k\in \{0,1,2,\dots ,n-1\},$ and all languages over A of the form L(a,r), where $a\in A,$ and r is a non-negative integer.

4. The Equality of Pseudovarieties $PU=Com\ast D$

As we have already explained in the introduction, the purpose of this paper is to establish the equality of pseudovarieties given in the heading of this section. The inclusion $PU\subseteq Com\ast D$ has been verified already by Almeida in [1] and in [2, Sec. 11.9] using purely algebraic arguments. Thus it remains to establish also the opposite inclusion $Com\ast D\subseteq PU$. This once, we shall do so by means of language theoretical methods. We have recalled in Theorem 3.1 the celebrated result of Eilenberg, according to which there are mutually inverse order preserving one-to-one correspondences between the lattice of all pseudovarieties of semigroups and the lattice of all varieties of languages. As in the introduction, we shall let $\mathcal{𝒱}$ be the variety of languages corresponding to the pseudovariety $Com\ast D$, and we shall let $\mathcal{𝒲}$ be the variety of languages corresponding to the pseudovariety $PU$. Then, in order to establish the inclusion $Com\ast D\subseteq PU$, we shall struggle to verify that we have $\mathcal{𝒱}\subseteq \mathcal{𝒲}$. That is, we shall strive to show that, for every alphabet A, we have the inclusion $A^{+}\mathcal{𝒱}\subseteq A^{+}\mathcal{𝒲}$.

Once again, let $\mathcal{𝒞}om$ be the variety of languages corresponding to the pseudovariety $Com$. Let further $\mathcal{𝒟}$ be the variety of languages corresponding to the pseudovariety $D$, and let $\mathcal{𝒰}$ be the variety of languages corresponding to the pseudovariety $U$. Since clearly $U\subseteq PU$, we have $\mathcal{𝒰}\subseteq \mathcal{𝒲}$, which means that, for every alphabet A, we have the inclusion $A^{+}\mathcal{𝒰}\subseteq A^{+}\mathcal{𝒲}$. Next we turn to the pseudovariety $Com\ast D$ and to its corresponding variety of languages $\mathcal{𝒱}$.

According to Straubing’s wreath product principle captured in Corollary 3.4, for every alphabet A, the collection of languages $A^{+}\mathcal{𝒱}$ is the smallest Boolean algebra containing all languages from $A^{+}\mathcal{𝒟}$ and all languages of the form ${\sigma }_{\phi }^{-1}(J)$, where $\phi :A^{+}\to T$ is a homomorphism of $A^{+}$ into a semigroup $T\in D$, ${\sigma }_{\phi }$ is the sequential function associated with $\phi$, and J is any language from $B_T^{+}\mathcal{𝒞}om$. Since clearly $D\subseteq U$, we have $\mathcal{𝒟}\subseteq \mathcal{𝒰}$, which means that, for every alphabet A, we have the inclusion $A^{+}\mathcal{𝒟}\subseteq A^{+}\mathcal{𝒰}$. We have seen in the previous paragraph that we also have the inclusion $A^{+}\mathcal{𝒰}\subseteq A^{+}\mathcal{𝒲}$. Therefore, for every alphabet A, we get the inclusion $A^{+}\mathcal{𝒟}\subseteq A^{+}\mathcal{𝒲}$. Thus it remains to look after the languages of the form ${\sigma }_{\phi }^{-1}(J)$ specified above. We need to show that also these languages belong to the collection $A^{+}\mathcal{𝒲}$.

Thus let $\phi :A^{+}\to T$ be a homomorphism of $A^{+}$ into a semigroup $T\in D$, let ${\sigma }_{\phi }$ be the sequential function associated with $\phi$, and let J be any language from $B_T^{+}\mathcal{𝒞}om$. Since $T\in D$ and $D={\bigcup }_{m=1}^{\infty }{D}_m$, there exists a positive integer m such that $T\in D_m$. Therefore the semigroup T satisfies the pseudoidentity $x{y}_1{y}_2\cdots y_m\bumpeq y_1{y}_2\cdots y_m$. Recall that the sequential function ${\sigma }_{\phi }$ is given, for every positive integer h and for arbitrary elements $a_1,a_2,\dots ,a_h\in A$, by the formula

Consider any index $i\in \{1,2,\dots ,h\}$ such that $m<i$. Then we have This finding shows that, when computing the word ${\sigma }_{\phi }(a_1{a}_2\cdots a_h)$, apart from the initial m segments $a_1$, $a_1{a}_2,\dots ,a_1{a}_2\cdots a_m$ of the word $a_1{a}_2\cdots a_h$, they are only the segments of the word $a_1{a}_2\cdots a_h$ of length $m+1$ which do matter. Thus, in the word ${\sigma }_{\phi }(a_1{a}_2\cdots a_h)$, only the initial letters $(1,a_1)$, $(\phi (a_1),a_2)$, $(\phi (a_1{a}_2),a_3)$, …, $(\phi (a_1{a}_2\cdots a_{m-1}),a_m)$ of the alphabet $B_T$ will appear first, and then only the letters of the form $(\phi (a_j{a}_{j+1}\cdots a_{j+m-1}),a_{j+m})$, for all $j\in \{1,2,\dots ,h-m\}$, of the alphabet $B_T$ will appear subsequently.

According to Proposition 3.6, the language J from $B_T^{+}\mathcal{𝒞}om$ is a Boolean combination of languages over the alphabet $B_T=T^1\times A$ of the form $K((t,a),k,n)$, where $(t,a)$ is a letter in $B_T$, so that $t\in T^1$ and $a\in A$, n is a positive integer and $k\in \{0,1,2,\dots ,n-1\}$, and of languages of the form $L((t,a),r)$, where $(t,a)$ is again a letter in $B_T$, so that $t\in T^1$ and $a\in A$ and r is a non-negative integer. We have to show that then the language ${\sigma }_{\phi }^{-1}(J)$ belongs to the collection of languages $A^{+}\mathcal{𝒲}$. Since the operator ${\sigma }_{\phi }^{-1}$ commutes with the Boolean operations, we see that it will be enough if we show that the languages of the forms ${\sigma }_{\phi }^{-1}(K((t,a),k,n))$ and ${\sigma }_{\phi }^{-1}(L((t,a),r))$ belong to $A^{+}\mathcal{𝒲}$. We already know from Theorem 3.2 that these languages are recognizable languages over the alphabet A.

We start with the languages of the form ${\sigma }_{\phi }^{-1}(K((t,a),k,n))$, where $t\in T^1$, $a\in A$, n is a positive integer, and $k\in \{0,1,2,\dots ,n-1\}$. We shall see that, in this case, these languages actually belong already to the subset $A^{+}\mathcal{𝒰}$ of $A^{+}\mathcal{𝒲}$. For this purpose, we shall show that the syntactic semigroups of these languages belong to the pseudovariety $U$. We shall document this statement by verifying that these syntactic semigroups satisfy the pseudoidentities $exeye\bumpeq eyexe$ and ${(ef)}^{\omega }exf\bumpeq exf$.

Lemma 4.1. The syntactic semigroup of the language ${\sigma }_{\phi }^{-1}(K((t,a),k,n))$ satisfies the pseudoidentity $exeye\bumpeq eyexe$.

Proof. Let us denote briefly by ${\sim }_K$ the syntactic congruence of the language ${\sigma }_{\phi }^{-1}(K((t,a),k,n))$. Thus we wish to show that the syntactic semigroup $A^{+}/{\sim }_K$ satisfies the pseudoidentity $exeye\bumpeq eyexe$. So let $u,v\in A^{+}$ and $𝜀\in A^{+}$ be arbitrary words such that the class $[𝜀]{\sim }_K$ is an idempotent in $A^{+}/{\sim }_K$. We need to show that then we have $𝜀u𝜀v𝜀{\sim }_K𝜀v𝜀u𝜀$. By the definition of the syntactic congruence ${\sim }_K$, this means to check that, for arbitrary words $p,q\in A^{\ast }$, we have

Equivalently, this means to verify that, for any words $p,q\in A^{\ast }$, we have Since the class $[𝜀]{\sim }_K$ is an idempotent in $A^{+}/{\sim }_K$, we have $𝜀{\sim }_K{𝜀}^2$, which says that, for arbitrary words $c,d\in A^{\ast }$, we have $c𝜀d\in {\sigma }_{\phi }^{-1}(K((t,a),k,n))\iff c{𝜀}^{2}d\in {\sigma }_{\phi }^{-1}(K((t,a),k,n))$, or, which is the same, ${\sigma }_{\phi }(c𝜀d)\in K((t,a),k,n)\iff {\sigma }_{\phi }(c{𝜀}^{2}d)\in K((t,a),k,n)$. But this entails that, in the formulae displayed above, we could replace every occurrence of the word $𝜀$ with an arbitrarily large positive power of $𝜀$. Therefore we may assume, in addition, that the length $|𝜀|$ of the word $𝜀$ is greater than the value m drawn above.

Now we have to return to our previous considerations regarding the computation of the word ${\sigma }_{\phi }(a_1{a}_2\cdots a_h)$, for arbitrary elements $a_1,a_2,\dots ,a_h\in A$, and to apply them to the above words ${\sigma }_{\phi }(p𝜀u𝜀v𝜀q)$ and ${\sigma }_{\phi }(p𝜀v𝜀u𝜀q)$. Since $|𝜀|>m$, the first m letters of the alphabet $B_T$ in the words ${\sigma }_{\phi }(p𝜀u𝜀v𝜀q)$ and ${\sigma }_{\phi }(p𝜀v𝜀u𝜀q)$ occur within the initial segment ${\sigma }_{\phi }(p𝜀)$ of these words, and therefore they are the same. As far as the other letters of $B_T$ in the words ${\sigma }_{\phi }(p𝜀u𝜀v𝜀q)$ and ${\sigma }_{\phi }(p𝜀v𝜀u𝜀q)$ are concerned, we have seen that these letters arise from segments of the words $p𝜀u𝜀v𝜀q$ and $p𝜀v𝜀u𝜀q$ of length $m+1$. Once again, since $|𝜀|>m$, such segments must appear as segments in one of the words $p𝜀$, $𝜀u𝜀$, $𝜀v𝜀$ and $𝜀q$. In particular, if such a segment hits the word u in $p𝜀u𝜀v𝜀q$, then it must be a segment of the word $𝜀u𝜀$. But then it is also a segment of the same word $𝜀u𝜀$ in $p𝜀v𝜀u𝜀q$. The same holds true of the segments of length $m+1$ of the words $p𝜀u𝜀v𝜀q$ and $p𝜀v𝜀u𝜀q$ which hit the word v. This consideration reveals that the number of occurrences of each individual letter of $B_T$ in both words ${\sigma }_{\phi }(p𝜀u𝜀v𝜀q)$ and ${\sigma }_{\phi }(p𝜀v𝜀u𝜀q)$ is the same. Hence, by the definition of the language $K((t,a),k,n)$, we certainly have ${\sigma }_{\phi }(p𝜀u𝜀v𝜀q)\in K((t,a),k,n)\iff {\sigma }_{\phi }(p𝜀v𝜀u𝜀q)\in K((t,a),k,n)$, for arbitrary words $p,q\in A^{\ast }$, which yields that $𝜀u𝜀v𝜀{\sim }_K𝜀v𝜀u𝜀$, as required. □

Lemma 4.2. The syntactic semigroup of the language ${\sigma }_{\phi }^{-1}(K((t,a),k,n))$ satisfies the pseudoidentity ${(ef)}^{\omega }exf\bumpeq exf$.

Proof. As before, let us denote briefly by ${\sim }_K$ the syntactic congruence of the language ${\sigma }_{\phi }^{-1}(K((t,a),k,n))$. Thus we wish to show that the syntactic semigroup $A^{+}/{\sim }_K$ satisfies the pseudoidentity ${(ef)}^{\omega }exf\bumpeq exf$. So let $u\in A^{+}$ and $𝜀,\varkappa \in A^{+}$ be arbitrary words such that the classes $[𝜀]{\sim }_K$ and $[\varkappa ]{\sim }_K$ are idempotents in $A^{+}/{\sim }_K$. Let g be any positive integer such that the class $[{(𝜀\varkappa )}^g]{\sim }_K$ is an idempotent in $A^{+}/{\sim }_K$. We need to show that then we have ${(𝜀\varkappa )}^g𝜀u\varkappa {\sim }_K𝜀u\varkappa$. By the definition of the syntactic congruence ${\sim }_K$, this means to check that, for arbitrary words $p,q\in A^{\ast }$, we have

Equivalently, this means to verify that, for any words $p,q\in A^{\ast }$, we have The same arguments as previously show that, in the above formulae, we could replace every occurrence of any of the words $𝜀$ and ϰ with an arbitrarily large positive power of this word. Therefore we may assume, in addition, that the lengths $|𝜀|$ and $|\varkappa |$ of the words $𝜀$ and ϰ are both greater than the value m drawn above. Furthermore, virtually the same reasoning also reveals that, in the above formulae, we could replace the word ${(𝜀\varkappa )}^g$ with an arbitrary positive power of this word. Therefore we may assume, in addition, that the exponent g is divisible by the positive integer n.

Once again, we have to return to our previous considerations regarding the computation of the word ${\sigma }_{\phi }(a_1{a}_2\cdots a_h)$, for arbitrary elements $a_1,a_2,\dots ,a_h$$\in$ A, and to apply them to the above words ${\sigma }_{\phi }(p{(𝜀\varkappa )}^g𝜀u\varkappa q)$ and ${\sigma }_{\phi }(p𝜀u\varkappa q)$. Since $|𝜀|>m$, the first m letters of the alphabet $B_T$ appearing in these two words occur within the initial segment ${\sigma }_{\phi }(p𝜀)$ of these words, and therefore they are the same. Thus we have to look after the other appearances of the letters of the alphabet $B_T$ in these two words. We have seen that these letters arise from segments of the words $p{(𝜀\varkappa )}^g𝜀u\varkappa q$ and $p𝜀u\varkappa q$ of length $m+1$. Since $|𝜀|>m$ and $|\varkappa |>m$, the segments of length $m+1$ which may occur anywhere in the word $p{(𝜀\varkappa )}^g𝜀u\varkappa q$, beyond those occurrences of such segments which appear already in the word $p𝜀u\varkappa q$, must be segments of the word ${(𝜀\varkappa )}^g𝜀$, not counting the occurrences of these segments in the last factor $𝜀$ of this word. Moreover, every such segment in the word ${(𝜀\varkappa )}^g𝜀$ must be a segment of either of the words $𝜀\varkappa$ or $\varkappa 𝜀$. Hence, since the exponent g is divisible by n, the number of these occurrences of every such segment in the word ${(𝜀\varkappa )}^g𝜀$ must be divisible by n. These considerations reveal that the numbers of occurrences of each individual letter of $B_T$ in the words ${\sigma }_{\phi }(p{(𝜀\varkappa )}^g𝜀u\varkappa q)$ and ${\sigma }_{\phi }(p𝜀u\varkappa q)$ are congruent modulo n. Therefore, by the definition of the language $K((t,a),k,n)$, we have ${\sigma }_{\phi }(p{(𝜀\varkappa )}^g𝜀u\varkappa q)\in K((t,a),k,n)\iff {\sigma }_{\phi }(p𝜀u\varkappa q)\in K((t,a),k,n)$, for arbitrary words $p,q\in A^{\ast }$, which yields that ${(𝜀\varkappa )}^g𝜀u\varkappa {\sim }_K𝜀u\varkappa$, as required. □

We continue by verifying that the languages of the form ${\sigma }_{\phi }^{-1}(L((t,a),r))$, where $t\in T^1$, $a\in A$ and r is a non-negative integer, belong to $A^{+}\mathcal{𝒲}$. We begin with a few preliminary considerations. So let $w\in {\sigma }_{\phi }^{-1}(L((t,a),r))$ be an arbitrary word. This means that ${\sigma }_{\phi }(w)\in L((t,a),r)$. However, by the definition of the language $L((t,a),r)$, this is equivalent to the condition that the letter $(t,a)$ of the alphabet $B_T$ has exactly r appearances in the word ${\sigma }_{\phi }(w)$. Assume, for the time being, that the length $|w|$ of the word w is greater than m. Let $r_0$ be the number of appearances of the mentioned letter $(t,a)$ in the initial segment of the word ${\sigma }_{\phi }(w)$ of length m. Then we can write $r=r_0+\bar{r}$ for some non-negative integer $\bar{r}$. From our earlier considerations we know that the appearances of the letter $(t,a)$ in the word ${\sigma }_{\phi }(w)$ which do not occur in the initial segment of ${\sigma }_{\phi }(w)$ of length m arise from some segments of the word w of length $m+1$. There may be several such pairwise distinct segments in the word w. So let $\xi$ be any of these segments of the word w of length $m+1$ which give rise to the letter $(t,a)$. Let $\xi$ have s occurrences in the word w. Then $s\le \bar{r}$. (We permit also the possibility that $s=0$.) Consider now all s occurrences of this segment $\xi$ in the word w. Some of these occurrences of $\xi$ may overlap in w or they may touch each other. Let ${\varpi }_1,{\varpi }_2,\dots ,{\varpi }_{\ell }$ be all maximal segments of the word w which are covered completely by the mentioned occurrences of the segment $\xi$ in w. Then $\ell \le s$ and $w={\upsilon }_0{\varpi }_1{\upsilon }_1{\varpi }_2{\upsilon }_2\cdots {\upsilon }_{\ell -1}{\varpi }_{\ell }{\upsilon }_{\ell }$ for some words ${\upsilon }_0,{\upsilon }_{\ell }\in A^{\ast }$ and ${\upsilon }_1,{\upsilon }_2,\dots ,{\upsilon }_{\ell -1}\in A^{+}$. Let $\overline{A}$ be an alphabet disjoint with A whose letters are in a one-to-one correspondence with the letters of A. Consider next the language ${\overline{A}}^{\ast }{\varpi }_1{\overline{A}}^{+}{\varpi }_2{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_{\ell }{\overline{A}}^{\ast }$. (If $s=0$, and so $\ell =0$, then take the language ${\overline{A}}^{+}$ instead.) This language is a rational language over the alphabet $A\cup \overline{A}$, and therefore, by Kleene’s theorem, it is a recognizable language.

We shall have to deal with all possible languages over the alphabet $A\cup \overline{A}$ of the form just mentioned. Every such language is completely determined by the given $\ell$-tuple of words $({\varpi }_1,{\varpi }_2,\dots ,{\varpi }_{\ell })$. Recall that such $\ell$-tuples are characterized by the following properties. First of all, there is a word $\xi$ over the alphabet A of length $m+1$ which gives rise to the letter $(t,a)$ of the alphabet $B_T$. According to what we have already specified above, this means that, if $\xi =c_0{c}_1{c}_2\cdots c_m$ where $c_0,c_1,c_2,\dots ,c_m\in A$, then $\phi (c_0{c}_1\cdots c_{m-1})=t$ and $c_m=a$. Thereafter, the mentioned $\ell$-tuple $({\varpi }_1,{\varpi }_2,\dots ,{\varpi }_{\ell })$ consists of non-empty words over the alphabet A such that the total number of occurrences of the segment $\xi$ in any of the words ${\varpi }_1,{\varpi }_2,\dots ,{\varpi }_{\ell }$ is equal to s and, at the same time, every letter of any of the words ${\varpi }_1,{\varpi }_2,\dots ,{\varpi }_{\ell }$ is covered by some occurrence of the segment $\xi$ in this word. Then certainly $\ell \le s$ and there are evidently only finitely many possibilities how such $\ell$-tuples $({\varpi }_1,{\varpi }_2,\dots ,{\varpi }_{\ell })$ may look like. Therefore there are only finitely many languages of the form ${\overline{A}}^{\ast }{\varpi }_1{\overline{A}}^{+}{\varpi }_2{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_{\ell }{\overline{A}}^{\ast }$ which may arise in this way. (If $s=0$, and so $\ell =0$, then there is only the language ${\overline{A}}^{+}$ which may so arise.) Let now $L_{\xi }^{(s)}$ be the finite union of all of these languages so determined. Then $L_{\xi }^{(s)}$ is again a recognizable language over the alphabet $A\cup \overline{A}$.

We are going to show that the recognizable language $L_{\xi }^{(s)}$ just designated belongs to the collection of languages which the variety of languages $\mathcal{𝒰}$ assigns to the alphabet $A\cup \overline{A}$. We intend to attain this goal by checking that the syntactic semigroup of this language $L_{\xi }^{(s)}$ belongs to the pseudovariety $U$. We shall achieve this aim by verifying that this syntactic semigroup satisfies the pseudoidentities $exeye\bumpeq eyexe$ and ${(ef)}^{\omega }exf\bumpeq exf$.

For the sake of notational ease, let us denote briefly by ${\sim }_L$ the syntactic congruence of the language $L_{\xi }^{(s)}$. Then the syntactic semigroup of the language $L_{\xi }^{(s)}$ is of the form ${(A\cup \overline{A})}^{+}/{\sim }_L$. Recall that the language $L_{\xi }^{(s)}$ is a finite union of recognizable languages of the form ${\overline{A}}^{\ast }{\varpi }_1{\overline{A}}^{+}{\varpi }_2{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_{\ell }{\overline{A}}^{\ast }$. Let $L_1,L_2,\dots ,L_z$ be those finitely many languages of the form just mentioned whose union constitutes the language $L_{\xi }^{(s)}$. Let ${\sim }_{L_1},{\sim }_{L_2},\dots ,{\sim }_{L_z}$ be the syntactic congruences of these languages. Then the syntactic semigroups of these languages are of the forms ${(A\cup \overline{A})}^{+}/{\sim }_{L_1}$, ${(A\cup \overline{A})}^{+}/{\sim }_{L_2},\dots ,{(A\cup \overline{A})}^{+}/{\sim }_{L_z}$. Consider the subdirect product of these syntactic semigroups consisting of all z-tuples of the form $([w]{\sim }_{L_1},[w]{\sim }_{L_2},\dots ,[w]{\sim }_{L_z})$, where $w\in {(A\cup \overline{A})}^{+}$. Then this subdirect product recognizes the language $L_{\xi }^{(s)}$, and so the syntactic semigroup ${(A\cup \overline{A})}^{+}/{\sim }_L$ of this language $L_{\xi }^{(s)}$ is a canonical homomorphic image of the mentioned subdirect product of syntactic semigroups of the languages $L_1,L_2,\dots ,L_z$. This canonical homomorphism maps every z-tuple of the form $([w]{\sim }_{L_1},[w]{\sim }_{L_2},\dots ,[w]{\sim }_{L_z})$ to the element $[w]{\sim }_L$.

Lemma 4.3. The syntactic semigroup ${(A\cup \overline{A})}^{+}/{\sim }_L$ of the language $L_{\xi }^{(s)}$ satisfies the pseudoidentity $exeye\bumpeq eyexe$.

Proof. So let $𝜀\in {(A\cup \overline{A})}^{+}$ and $u,v\in {(A\cup \overline{A})}^{+}$ be any words such that the class $[𝜀]{\sim }_L$ is an idempotent in the semigroup ${(A\cup \overline{A})}^{+}/{\sim }_L$. We need to show that then we have $𝜀u𝜀v𝜀{\sim }_L𝜀v𝜀u𝜀$. The element $[𝜀]{\sim }_L$ is the image under the above canonical homomorphism of the z-tuple $([𝜀]{\sim }_{L_1},[𝜀]{\sim }_{L_2},\dots ,[𝜀]{\sim }_{L_z})$. Since our syntactic semigroups are finite semigroups, there exists a positive integer $\eta$ such that the z-tuple $([{𝜀}^{\eta }]{\sim }_{L_1},[{𝜀}^{\eta }]{\sim }_{L_2},\dots ,[{𝜀}^{\eta }]{\sim }_{L_z})$ is an idempotent. Thus, for every $i\in \{1,2,\dots ,z\}$, the element $[{𝜀}^{\eta }]{\sim }_{L_i}$ is an idempotent, and so we have ${𝜀}^{\eta }{\sim }_{L_i}{𝜀}^{2\eta }$. By the definition of the syntactic congruence ${\sim }_{L_i}$, for every words $c,d\in {(A\cup \overline{A})}^{\ast }$, we get $c{𝜀}^{\eta }d\in L_i\iff c{𝜀}^{2\eta }d\in L_i$. However, having in view that the language $L_i$ is of the form ${\overline{A}}^{\ast }{\varpi }_1{\overline{A}}^{+}{\varpi }_2{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_{\ell }{\overline{A}}^{\ast }$, we come to the following conclusion. If the word $𝜀$ contained some elements from the alphabet A and if, for some words $c,d\in {(A\cup \overline{A})}^{\ast }$, we had $c{𝜀}^{\eta }d\in L_i$, then we would certainly have $c{𝜀}^{2\eta }d\notin L_i$. However, this means that the above condition $c{𝜀}^{\eta }d\in L_i\iff c{𝜀}^{2\eta }d\in L_i$ would be violated. Thus, whenever $𝜀\notin {\overline{A}}^{+}$, then, for any words $c,d\in {(A\cup \overline{A})}^{\ast }$, we must have $c{𝜀}^{\eta }d\notin L_i$. Therefore, in particular, in such a case, for any words $p,q\in {(A\cup \overline{A})}^{\ast }$, we must have $p{𝜀}^{\eta }u{𝜀}^{\eta }v{𝜀}^{\eta }q\notin L_i$ and $p{𝜀}^{\eta }v{𝜀}^{\eta }u{𝜀}^{\eta }q\notin L_i$. However, by the definition of the syntactic congruence ${\sim }_{L_i}$, this means that ${𝜀}^{\eta }u{𝜀}^{\eta }v{𝜀}^{\eta }{\sim }_{L_i}{𝜀}^{\eta }v{𝜀}^{\eta }u{𝜀}^{\eta }$. This relation must hold for all $i\in \{1,2,\dots ,z\}$. By the reasonings preceding this lemma, it hence eventually ensues that ${𝜀}^{\eta }u{𝜀}^{\eta }v{𝜀}^{\eta }{\sim }_L{𝜀}^{\eta }v{𝜀}^{\eta }u{𝜀}^{\eta }$. Since here the element $[𝜀]{\sim }_L$ is an idempotent, and so it is equal to the element $[{𝜀}^{\eta }]{\sim }_L$, we hence lastly infer that $𝜀u𝜀v𝜀{\sim }_L𝜀v𝜀u𝜀$, as desired. Thus it remains to treat the case when $𝜀\in {\overline{A}}^{+}$.

We have to verify that, in this case, we also have $𝜀u𝜀v𝜀{\sim }_L𝜀v𝜀u𝜀$. By the definition of the syntactic congruence ${\sim }_L$, this means to check that, for any words $p,q\in {(A\cup \overline{A})}^{\ast }$, we have $p𝜀u𝜀v𝜀q\in L_{\xi }^{(s)}\iff p𝜀v𝜀u𝜀q\in L_{\xi }^{(s)}$. Thus assume that $p𝜀u𝜀v𝜀q\in L_{\xi }^{(s)}$. Since $L_{\xi }^{(s)}$ is a finite union of languages of the form ${\overline{A}}^{\ast }{\varpi }_1{\overline{A}}^{+}{\varpi }_2{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_{\ell }{\overline{A}}^{\ast }$, it hence ensues that we must have $p𝜀u𝜀v𝜀q\in {\overline{A}}^{\ast }{\varpi }_1{\overline{A}}^{+}{\varpi }_2{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_{\ell }{\overline{A}}^{\ast }$ for some $\ell$-tuple $({\varpi }_1,{\varpi }_2,\dots ,{\varpi }_{\ell })$. Since we now have $𝜀\in {\overline{A}}^{+}$, the three appearances of the segment $𝜀$ in the word $p𝜀u𝜀v𝜀q$ must fall into some of the factors of the form ${\overline{A}}^{\ast }$ or ${\overline{A}}^{+}$ in the language ${\overline{A}}^{\ast }{\varpi }_1{\overline{A}}^{+}{\varpi }_2{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_{\ell }{\overline{A}}^{\ast }$. If $u\in {\overline{A}}^{+}$, then the whole segment $𝜀u𝜀$ must fall into the same factor of the form ${\overline{A}}^{\ast }$ or ${\overline{A}}^{+}$. But then, clearly, we get that $p𝜀v𝜀u𝜀q\in {\overline{A}}^{\ast }{\varpi }_1{\overline{A}}^{+}{\varpi }_2{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_{\ell }{\overline{A}}^{\ast }$, and so $p𝜀v𝜀u𝜀q\in L_{\xi }^{(s)}$. The same conclusion follows if $v\in {\overline{A}}^{+}$. Thus we may further assume that $u\notin {\overline{A}}^{+}$ and $v\notin {\overline{A}}^{+}$. Then there exist indices $i,j,k\in \{1,2,\dots ,\ell \}$ satisfying $i\le j<k$ such that the segment $𝜀u𝜀$ comes from the language ${\overline{A}}^{+}{\varpi }_i{\overline{A}}^{+}{\varpi }_{i+1}{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_j{\overline{A}}^{+}$ and the segment $𝜀v𝜀$ comes from the language ${\overline{A}}^{+}{\varpi }_{j+1}{\overline{A}}^{+}{\varpi }_{j+2}{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_k{\overline{A}}^{+}$, and they are the leftmost and the rightmost positions of the factors of the form ${\overline{A}}^{+}$ in these two languages that the appearances of the segment $𝜀$ in the words $𝜀u𝜀$ and $𝜀v𝜀$ come from. But then, clearly, the word $p𝜀v𝜀u𝜀q$ is an element of the language

However, this language is also one of the constituents of the language $L_{\xi }^{(s)}$. Therefore we see that we again have $p𝜀v𝜀u𝜀q\in L_{\xi }^{(s)}$. Similarly we can show that if $p𝜀v𝜀u𝜀q\in L_{\xi }^{(s)}$, then also $p𝜀u𝜀v𝜀q\in L_{\xi }^{(s)}$. This finding verifies that we indeed have $𝜀u𝜀v𝜀{\sim }_L𝜀v𝜀u𝜀$, again as desired. □

Lemma 4.4. The syntactic semigroup ${(A\cup \overline{A})}^{+}/{\sim }_L$ of the language $L_{\xi }^{(s)}$ satisfies the pseudoidentity ${(ef)}^{\omega }exf\bumpeq exf$.

Proof. To start with, let us to recall the considerations performed in the paragraph preceding Lemma 4.3 and the notations introduced in that paragraph. Thus let now $𝜀,\varkappa \in {(A\cup \overline{A})}^{+}$ and $u\in {(A\cup \overline{A})}^{+}$ be any words such that the classes $[𝜀]{\sim }_L$ and $[\varkappa ]{\sim }_L$ are idempotents in ${(A\cup \overline{A})}^{+}/{\sim }_L$. Let g be any positive integer such that the class $[{(𝜀\varkappa )}^g]{\sim }_L$ is an idempotent in ${(A\cup \overline{A})}^{+}/{\sim }_L$. We need to show that then we have ${(𝜀\varkappa )}^g𝜀u\varkappa {\sim }_L𝜀u\varkappa$. The element $[𝜀]{\sim }_L$ is the image of the z-tuple $([𝜀]{\sim }_{L_1},[𝜀]{\sim }_{L_2},\dots ,[𝜀]{\sim }_{L_z})$, and the element $[\varkappa ]{\sim }_L$ is the image of the z-tuple $([\varkappa ]{\sim }_{L_1},[\varkappa ]{\sim }_{L_2},\dots ,[\varkappa ]{\sim }_{L_z})$. Then there exists a positive integer $\eta$ such that the z-tuple $([{𝜀}^{\eta }]{\sim }_{L_1},[{𝜀}^{\eta }]{\sim }_{L_2},\dots ,[{𝜀}^{\eta }]{\sim }_{L_z})$ is an idempotent, and the z-tuple $([{\varkappa }^{\eta }]{\sim }_{L_1},[{\varkappa }^{\eta }]{\sim }_{L_2},\dots ,[{\varkappa }^{\eta }]{\sim }_{L_z})$ is an idempotent. Thus, for every $i\in \{1,2,\dots ,z\}$, the element $[{𝜀}^{\eta }]{\sim }_{L_i}$ is an idempotent, which means that we have ${𝜀}^{\eta }{\sim }_{L_i}{𝜀}^{2\eta }$. By the definition of the syntactic congruence ${\sim }_{L_i}$, for every words $c,d\in {(A\cup \overline{A})}^{\ast }$, we get $c{𝜀}^{\eta }d\in L_i\iff c{𝜀}^{2\eta }d\in L_i$. However, since the language $L_i$ is of the form ${\overline{A}}^{\ast }{\varpi }_1{\overline{A}}^{+}{\varpi }_2{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_{\ell }{\overline{A}}^{\ast }$, we can infer the following conclusion. If the word $𝜀$ contained some elements from the alphabet A and if, for some words $c,d\in {(A\cup \overline{A})}^{\ast }$, we had $c{𝜀}^{\eta }d\in L_i$, then we would certainly have $c{𝜀}^{2\eta }d\notin L_i$. But this would contradict the above condition $c{𝜀}^{\eta }d\in L_i\iff c{𝜀}^{2\eta }d\in L_i$. Thus, whenever $𝜀\notin {\overline{A}}^{+}$, then, for any words $c,d\in {(A\cup \overline{A})}^{\ast }$, we must have $c{𝜀}^{\eta }d\notin L_i$. Therefore, in particular, in such a case, for any words $p,q\in {(A\cup \overline{A})}^{\ast }$, we must have $p{({𝜀}^{\eta }{\varkappa }^{\eta })}^g{𝜀}^{\eta }u{\varkappa }^{\eta }q\notin L_i$ and $p{𝜀}^{\eta }u{\varkappa }^{\eta }q\notin L_i$. But, by the definition of the syntactic congruence ${\sim }_{L_i}$, this means that ${({𝜀}^{\eta }{\varkappa }^{\eta })}^g{𝜀}^{\eta }u{\varkappa }^{\eta }{\sim }_{L_i}{𝜀}^{\eta }u{\varkappa }^{\eta }$. This relation must hold for all $i\in \{1,2,\dots ,z\}$. By the reasonings performed in the paragraph preceding Lemma 4.3, it hence eventually ensues that ${({𝜀}^{\eta }{\varkappa }^{\eta })}^g{𝜀}^{\eta }u{\varkappa }^{\eta }{\sim }_L{𝜀}^{\eta }u{\varkappa }^{\eta }$. Since here the elements $[𝜀]{\sim }_L$ and $[\varkappa ]{\sim }_L$ are idempotents, and so they are equal to the elements $[{𝜀}^{\eta }]{\sim }_L$ and $[{\varkappa }^{\eta }]{\sim }_L$, respectively, we hence deduce, in the end, that ${(𝜀\varkappa )}^g𝜀u\varkappa {\sim }_L𝜀u\varkappa$, as desired. We have arrived at this conclusion under the assumption that $𝜀\notin {\overline{A}}^{+}$. Likewise, we could come to the same conclusion if we went from the assumption that $\varkappa \notin {\overline{A}}^{+}$. Thus it remains to deal with the case when $𝜀\in {\overline{A}}^{+}$ and $\varkappa \in {\overline{A}}^{+}$.

We have to verify that, in this case, we also have ${(𝜀\varkappa )}^g𝜀u\varkappa {\sim }_L𝜀u\varkappa$. By the definition of the syntactic congruence ${\sim }_L$, this means to check that, for any words $p,q\in {(A\cup \overline{A})}^{\ast }$, we have $p{(𝜀\varkappa )}^g𝜀u\varkappa q\in L_{\xi }^{(s)}\iff p𝜀u\varkappa q\in L_{\xi }^{(s)}$. Thus assume that $p{(𝜀\varkappa )}^g𝜀u\varkappa q\in L_{\xi }^{(s)}$. Since $L_{\xi }^{(s)}$ is a finite union of languages of the form ${\overline{A}}^{\ast }{\varpi }_1{\overline{A}}^{+}{\varpi }_2{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_{\ell }{\overline{A}}^{\ast }$, it hence ensues that we must have $p{(𝜀\varkappa )}^g𝜀u\varkappa q\in {\overline{A}}^{\ast }{\varpi }_1{\overline{A}}^{+}{\varpi }_2{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_{\ell }{\overline{A}}^{\ast }$ for some $\ell$-tuple $({\varpi }_1,{\varpi }_2,\dots ,{\varpi }_{\ell })$. Since we now have $𝜀\in {\overline{A}}^{+}$ and $\varkappa \in {\overline{A}}^{+}$, we see that the whole segment ${(𝜀\varkappa )}^g𝜀$ in the word $p{(𝜀\varkappa )}^g𝜀u\varkappa q$ must fall into a single factor of the form ${\overline{A}}^{\ast }$ or ${\overline{A}}^{+}$ in the language ${\overline{A}}^{\ast }{\varpi }_1{\overline{A}}^{+}{\varpi }_2{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_{\ell }{\overline{A}}^{\ast }$. However, then it is evident that we also get $p𝜀u\varkappa q\in {\overline{A}}^{\ast }{\varpi }_1{\overline{A}}^{+}{\varpi }_2{\overline{A}}^{+}\cdots {\overline{A}}^{+}{\varpi }_{\ell }{\overline{A}}^{\ast }$, and so we obtain $p𝜀u\varkappa q\in L_{\xi }^{(s)}$. In a similar manner, it is possible to show that if $p𝜀u\varkappa q\in L_{\xi }^{(s)}$, then also $p{(𝜀\varkappa )}^g𝜀u\varkappa q\in L_{\xi }^{(s)}$. These findings assure that we indeed have ${(𝜀\varkappa )}^g𝜀u\varkappa {\sim }_L𝜀u\varkappa$, again as desired. □

Let further ${\widehat{L}}_{\xi }^{(s)}$ be the language over the alphabet A consisting of all words which one may obtain from the words of the language $L_{\xi }^{(s)}$ by replacing in them every occurrence of any letter from $\overline{A}$ by its respective letter form A. It is clear that then the language ${\widehat{L}}_{\xi }^{(s)}$ comprises exactly those words over the alphabet A which contain at least s occurrences of the segment $\xi$. Now we wish to sort out of these words those ones which contain exactly s occurrences of the segment $\xi$. That is, we intend to remove from ${\widehat{L}}_{\xi }^{(s)}$ those words which contain more than s occurrences of $\xi$. For this purpose, we must be aware that, up to now, we have performed all our considerations with an arbitrary non-negative integer s. Thus we may replace everywhere in the foregoing reasonings this integer s with the integer $s+1$. In this way, we come up with the languages $L_{\xi }^{(s+1)}$ and ${\widehat{L}}_{\xi }^{(s+1)}$. Then, of course, the language ${\widehat{L}}_{\xi }^{(s+1)}$ comprises exactly those words over the alphabet A which contain at least $s+1$ occurrences of the segment $\xi$. And then the language ${\widehat{L}}_{\xi }^{(s)}\backslash {\widehat{L}}_{\xi }^{(s+1)}$ consists precisely of those words over the alphabet A which contain exactly s occurrences of the segment $\xi$.

We have shown in Lemmas 4.3 and 4.4 that the syntactic semigroups of the languages $L_{\xi }^{(s)}$ over the alphabet $A\cup \overline{A}$, for whichever non-negative integers s, belong to the pseudovariety $U$. We have considered subsequently the languages ${\widehat{L}}_{\xi }^{(s)}$, again for any non-negative integers s, over the alphabet A, whose creation from the languages $L_{\xi }^{(s)}$ can also be expressed in the following terms. Let us consider the homomorphism $\lambda :{(A\cup \overline{A})}^{+}\to A^{+}$ of free semigroups determined by the requirements that $\lambda$ should map every element of A to itself and $\lambda$ should map every element of the disjoint copy $\overline{A}$ of A to its respective counterpart in A. Then $\lambda$ is a length preserving homomorphism. Then we have ${\widehat{L}}_{\xi }^{(s)}=\lambda (L_{\xi }^{(s)})$. By Theorem 3.5, we know that then ${\widehat{L}}_{\xi }^{(s)}$ are again recognizable languages which are recognized by suitable semigroups from the power pseudovariety $PU$. Therefore these languages belong to the collection of languages $A^{+}\mathcal{𝒲}$. Of course, then also the language ${\widehat{L}}_{\xi }^{(s)}\backslash {\widehat{L}}_{\xi }^{(s+1)}$ belongs to this collection $A^{+}\mathcal{𝒲}$. We have next seen above that the language ${\widehat{L}}_{\xi }^{(s)}\backslash {\widehat{L}}_{\xi }^{(s+1)}$ consists precisely of those words over the alphabet A which contain exactly s occurrences of the segment $\xi$. Recall that $\xi$ has been a word in the alphabet A of length $m+1$ giving rise to the letter $(t,a)$ of the alphabet $B_T$. There may be several such distinct words $\xi$ which give rise to the same letter $(t,a)$ in this way. So let ${\xi }_1,{\xi }_2,\dots ,{\xi }_{\mu }$ be all words enjoying this property. Let further $s_1,s_2,\dots ,s_{\mu }$ be any non-negative integers. Then for every $i\in \{1,2,\dots ,\mu \}$, we may consider the language ${\widehat{L}}_{{\xi }_i}^{(s_i)}\backslash {\widehat{L}}_{{\xi }_i}^{(s_i+1)}$. Then the language ${\bigcap }_{i=1}^{\mu }({\widehat{L}}_{{\xi }_i}^{(s_i)}\backslash {\widehat{L}}_{{\xi }_i}^{(s_i+1)})$ consists of those words which, for every $i\in \{1,2,\dots ,\mu \}$, contain exactly $s_i$ occurrences of the segment ${\xi }_i$. Denote this last language by ${\overline{L}}_{{\xi }_1,\dots ,{\xi }_{\mu }}^{s_1,\dots ,s_{\mu }}$. This language then again belongs to the collection $A^{+}\mathcal{𝒲}$. Let finally $\bar{r}$ be any non-negative integer. Consider all $\mu$-tuples $(s_1,s_2,\dots ,s_{\mu })$ of non-negative integers such that $s_1+s_2+\cdots +s_{\mu }=\bar{r}$. Then we may form the language ${\bigcup }_{s_1+\cdots +s_{\mu }=\bar{r}}{\overline{L}}_{{\xi }_1,\dots ,{\xi }_{\mu }}^{s_1,\dots ,s_{\mu }}$. This language, which we shall denote briefly by ${\overline{L}}^{(\bar{r})}$, then also belongs to the collection $A^{+}\mathcal{𝒲}$.

It should now be clear that the language ${\overline{L}}^{(\bar{r})}$ consists precisely of those words $w\in A^{+}$ which enjoy the following property. We focus first on the words $w\in A^{+}$ whose length $|w|$ is greater than m. Then such a word w belongs to the language ${\overline{L}}^{(\bar{r})}$ if and only if the number of those appearances of the letter $(t,a)$ in the word ${\sigma }_{\phi }(w)$ which do not occur in the initial segment of ${\sigma }_{\phi }(w)$ of length m is equal to $\bar{r}$. As far as the words $w\in A^{+}$ whose length $|w|$ does not exceed m are concerned, the following holds true. If $\bar{r}=0$, then all such words w belong to the language ${\overline{L}}^{(\bar{r})}$. If, on the contrary, $\bar{r}>0$, then the language ${\overline{L}}^{(\bar{r})}$ contains no words w of this kind.

Let $r_0$ be a non-negative integer such that $r_0\le m$. There are only finitely many words u in the alphabet A of length $|u|$ equal to m. Let $M^{(r_0)}$ be the set of all words u of this kind having the property that the number of appearances of the letter $(t,a)$ in the word ${\sigma }_{\phi }(u)$ is equal to $r_0$. Then $M^{(r_0)}$ is a finite language over the alphabet A. Consider next the language ${\overline{M}}^{(r_0)}=M^{(r_0)}{A}^{+}$. Then ${\overline{M}}^{(r_0)}$ is a recognizable language. It is a familiar fact— see [6, Sec. 2.3]— that this language ${\overline{M}}^{(r_0)}$ can be recognized by a semigroup from the pseudovariety $K$. Since clearly $K\subseteq U$, and as $U\subseteq PU$, we see that this language ${\overline{M}}^{(r_0)}$ can be recognized by a semigroup from the pseudovariety $PU$, and hence it belongs to the collection of languages $A^{+}\mathcal{𝒲}$. Note that this language contains no words w whose length $|w|$ does not exceed m. Take next any non-negative integer $\bar{r}$ and consider the language ${\overline{M}}^{(r_0)}\cap {\overline{L}}^{(\bar{r})}$. This language then also belongs to the collection $A^{+}\mathcal{𝒲}$ and it consists of all those words w in the alphabet A of length $|w|$ greater that m that have the property that, in the word ${\sigma }_{\phi }(w)$, there are $r_0$ appearances of the letter $(t,a)$ in the initial segment of this word of length m and there are $\bar{r}$ appearances of the letter $(t,a)$ in the rest of this word. Finally, for every non-negative integer r, consider all pairs $(r_0,\bar{r})$ of non-negative integers such that $r_0+\bar{r}=r$. Then we may consider the language ${\bigcup }_{r_0+\bar{r}=r}({\overline{M}}^{(r_0)}\cap {\overline{L}}^{(\bar{r})})$. This last language then again belongs to the collection $A^{+}\mathcal{𝒲}$ and it consists of those words w in the alphabet A whose length $|w|$ is greater than m and which possess the property that, in the word ${\sigma }_{\phi }(w)$, there are exactly r appearances of the letter $(t,a)$.

At last, given a non-negative integer r, we may consider the set ${\overline{N}}^{(r)}$ of all words v in the alphabet A of length $|v|$ not exceeding m and having the property that, in the word ${\sigma }_{\phi }(v)$, there are exactly r appearances of the letter $(t,a)$. Then ${\overline{N}}^{(r)}$ is a finite language over the alphabet A, which can therefore be recognized by a nilpotent semigroup, and so it can be certainly recognized by a semigroup from the pseudovariety $PU$. Hence this language belongs to the collection of languages $A^{+}\mathcal{𝒲}$. Finally we may consider the language ${\overline{N}}^{(r)}\cup {\bigcup }_{r_0+\bar{r}=r}({\overline{M}}^{(r_0)}\cap {\overline{L}}^{(\bar{r})})$. This last language then again belongs to the collection $A^{+}\mathcal{𝒲}$ and it consists of all those words w in the alphabet A which possess the property that, in the word ${\sigma }_{\phi }(w)$, there are exactly r appearances of the letter $(t,a)$. But this property means that ${\sigma }_{\phi }(w)\in L((t,a),r)$. Consequently, the last-mentioned language is precisely our language ${\sigma }_{\phi }^{-1}(L((t,a),r))$. Therefore this language belongs to the collection $A^{+}\mathcal{𝒲}$, as desired.