On the Syntactic Monoids Associated with a Class of Synchronized Codes

Abstract

A complete code $C$ over an alphabet $A$ is called synchronized if there exist $x,y\in C^{\mathrm{*}}$ such that $x{A}^{\mathrm{*}}\cap A^{\mathrm{*}}y\subseteq C^{\mathrm{*}}$ . In this paper we describe the syntactic monoid $\text{Syn}(C^{+})$ of $C^{+}$ for a complete synchronized code $C$ over $A$ such that $C^{+}$ , the semigroup generated by $C$ , is a single class of its syntactic congruence $P_{C^{+}}$ . In particular, we prove that, for such a code $C$ , either $C=A$ or $\text{Syn}(C^{+})$ is isomorphic to a special submonoid of ${�}^l(I)\times {�}^r(\mathrm{\Lambda })$ , where ${�}^l(I)$ and ${�}^r(\mathrm{\Lambda })$ are the full transformation semigroups on the nonempty sets $I$ and $\mathrm{\Lambda }$ , respectively.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Theory of codes is an important branch in the field of information science. Many methods, including combinatorics methods, analysis methods, and algebraic methods, are applied to study codes. As a kind of algebraic methods, it is effective to study some kinds of codes by considering syntactic monoids of the semigroups and monoids generated by these codes.

As we have known, prefix codes have fundamental importance in theory of codes. Many authors are devoted to the investigation of prefix codes by using several methods (cf. [1–4]). In particular, Petrich et al. [4] investigated maximal prefix codes by considering the syntactic monoids of the semigroups generated by them in 1996. They described the semigroup structure of the syntactic monoid $\text{Syn}(C^{+})$ of $C^{+}$ , the semigroup generated by a maximal prefix code $C$ for which $C^{+}$ is a single class of the syntactic congruence $P_{C^{+}}$ .

On the other hand, synchronized codes are also important both in theory and in applications. Many interesting results are obtained on this class of codes in the text of Berstel et al. [1]. Recently, Liu [3] investigated synchronized codes by algebraic methods and obtained an algebraic characterization of complete synchronized codes (see Lemma 5 in this paper). Furthermore, Liu [3, 5] also studied some generalizations of synchronized codes.

In this paper, by using the algebraic characterization of complete synchronized codes obtained in Liu [3] and some techniques developed in Petrich et al. [4], we give a description of the syntactic monoid $\text{Syn}(C^{+})$ of $C^{+}$ for a complete synchronized code $C$ over an alphabet $A$ such that $C^{+}$ is a single class of its syntactic congruence $P_{C^{+}}$ .

2. Preliminaries

A semigroup $S$ is a left zero semigroup if $ab=a$ for any $a,b\in S$ . Dually, we have right zero semigroups. A rectangular band is a semigroup which is isomorphic to a direct product of a left zero semigroup and a right zero semigroup. For rectangular bands, we have the following obvious result.

Lemma 1 (see [6]).

Let $S$ be a rectangular band. Then $axa=a$ for any $a,x\in S$ . As a consequence, $aSa=\{a\}$ for any $a\in S$ . In particular, if $S$ has an identity $e$ , then $S=\{e\}$ .

An ideal of a semigroup $S$ is a nonempty subset $I$ of $S$ satisfying that the union of $IS$ and $SI$ is contained in $I$ . Recall that the unique minimum ideal (with respect to set inclusion) of a semigroup $S$ (if exists) is called the kernel of $S$ . For the kernel of a semigroup, we have the following.

Lemma 2 (see [6]).

If the kernel of a semigroup $S$ only consists of idempotents, then this kernel is a rectangular band.

Let $S$ be a semigroup. A function $\lambda$ (resp., $\rho$ ) on $S$ is a left translation (resp., right translation) of $S$ if $\lambda (xy)=(\lambda x)y$ (resp., $(xy)\rho =x(y\rho )$ ) for all $x,y\in S$ . A left translation $\lambda$ and a right translation $\rho$ are linked if $x(\lambda y)=(x\rho )y$ in which case the pair $(\lambda ,\rho )$ is a bitranslation of $S$ . Denote the set of left translations and that of right translations on $S$ by $\mathrm{\Lambda }(S)$ and $P(S)$ , respectively. Clearly, $\mathrm{\Lambda }(S)$ forms a monoid under the usual composition of functions: $(\lambda {\lambda }^{\prime })x=\lambda ({\lambda }^{\prime }x)$ for all $x\in S$ . Dually, $P(S)$ forms a monoid under the usual composition of functions: $x(\rho {\rho }^{\prime })=(x\rho ){\rho }^{\prime }$ for all $x\in S$ . The set of all bitranslations of $S$ forms a submonoid of the direct product $\mathrm{\Lambda }(S)\times P(S)$ , which is called the translation hull of $S$ , to be denoted by $\Omega (S)$ .

Let $s$ be an element of a semigroup $S$ . Then the function ${\lambda }_s$ defined by ${\lambda }_{s}x=sx$ for all $x\in S$ is the inner left translation induced by $s$ . Dually, we have inner right translation ${\rho }_s$ induced by $s$ . Finally, the pair ${\pi }_s=({\lambda }_s,{\rho }_s)$ is the inner bitranslation induced by $s$ . The set $\Pi (S)$ of all inner bitranslations is the inner part of $\Omega (S)$ . From Corollary III.1.7 in Petrich [7], $\Pi (S)$ is an ideal of $\Omega (S)$ .

In the sequel, the set of all transformations on a set $Q$ written and composed as right (resp., left) operators is denoted by ${�}^r(Q)$ (resp., ${�}^l(Q)$ ). The identity mapping on a set $Q$ is denoted by ${\iota }_Q$ . If $q\in Q$ , then $⟨q⟩$ denotes the constant function on $Q$ whose value is $q$ . Clearly, ${�}^l(Q)$ and ${�}^r(Q)$ are semigroups with their own compositions and ${�}_{\mathrm{0}}^l(Q)=\{⟨q⟩\mid q\in Q\}$ (as left operators) and ${�}_{\mathrm{0}}^r(Q)=\{⟨q⟩\mid q\in Q\}$ (as right operators) are subsemigroups of ${�}^l(Q)$ and ${�}^r(Q)$ , respectively.

On the translation hull of a rectangular band, we have the following results which can be found in Section III.7 in Petrich and Reilly [6].

Lemma 3 (see [6]).

Let $I\times \mathrm{\Lambda }$ be a rectangular band.

(1)

$\Omega (I\times \mathrm{\Lambda })\cong {�}^l(I)\times {�}^r(\mathrm{\Lambda })$ .

(2)

$I\times \mathrm{\Lambda }\cong \Pi (I\times \mathrm{\Lambda })\cong {�}_{\mathrm{0}}^l(I)\times {�}_{\mathrm{0}}^r(\mathrm{\Lambda })$ .

(3)

${�}_{\mathrm{0}}^l(I)\times {�}_{\mathrm{0}}^r(\mathrm{\Lambda })$ is the kernel of ${�}^l(I)\times {�}^r(\mathrm{\Lambda })$ .

Let $S$ be a semigroup and $J$ an ideal of $S$ . Then $S$ is called an extension of $J$ . From Definition III.5.4 in Petrich [7], an extension $S$ of $J$ is called dense if for each congruence $\rho$ on $S$ , the fact that the restriction of $\rho$ to $J$ is the equality relation on $J$ implies that $\rho$ is the equality relation on $S$ .

On dense extensions of rectangular bands, the following results can be obtained as a special case from Theorem III.1.12 and Corollary III.5.5 in [7] and can also be proved easily.

Lemma 4.

If $S$ is a dense extension of a rectangular band $J$ , then the following semigroup homomorphism $$\begin{array}{}\text{(1)}& \tau :S⟶\Omega \left(J\right),\hspace{1em}s\mapsto s\tau =\left({\lambda }^s,{\rho }^s\right)\end{array}$$ is injective, where for each $s\in S$ , $$\begin{array}{}\text{(2)}& {\lambda }^s:J⟶J,\hspace{1em}j\mapsto sj,\hspace{1em}\hspace{1em}{\rho }^s:J⟶J,\hspace{1em}j\mapsto js.\end{array}$$ Clearly in this case, $S$ is isomorphic to $S\tau$ which contains $\Pi (J)$ as an ideal.

Let $S$ be a semigroup and let $S^{\mathrm{1}}$ be the semigroup obtained from $S$ by adjoining an identity if necessary. The syntactic congruence $P_L$ determined by a subset $L$ of $S$ is the following relation on $S$ : $\{(x,y)\in S\times S\mid uxv\in L$ if and only if $uyv\in L$ for all $u,v\in S^{\mathrm{1}}\}$ . In particular, if $L=\{x\}$ , we call   $P_{\{x\}}$   the syntactic congruence determined by $x$ and denote it by $P_x$ . Moreover, $x$ is called disjunctive in $S$ if $P_x$ is the equality relation on $S$ . It is easy to see that the relation   $P_L$   saturates   $L$ for every subset $L$ of $S$ ; that is, $L$ is a union of some $P_L$ -classes for every subset $L$ of $S$ .

Let $A$ be an alphabet, let $A^{*}$ be the free monoid generated by $A$ , and let 1 be the identity of $A^{*}$ . For any $L\subseteq A^{*}$ , the quotient monoid $A^{*}/P_L$ is called the syntactic monoid of $L$ , to be denoted by $\text{Syn}(L)$ . A nonempty set $C$ of $A^{+}=A^{*}\setminus \{\mathrm{1}\}$ is called a code over $A$ if the fact that $$\begin{array}{}\text{(3)}& x_{\mathrm{1}}{x}_{\mathrm{2}}\cdots x_m=y_{\mathrm{1}}{y}_{\mathrm{2}}\cdots y_n,\hspace{1em}{x}_i,\hspace{0.17em}{y}_j\in C,\hspace{0.17em}\hspace{0.17em}i=\mathrm{1,2},\dots ,m,\phantom{222222222222222222222222222222222}j=\mathrm{1,2},\dots ,n,\end{array}$$ implies that $m=n$ and $x_i=y_i$ , $i=\mathrm{1,2},\dots ,n$ .

A submonoid $S$ of a monoid $M$ is called stable in $M$ if the fact that $u,wu,uw\in S$ implies that $w\in S$ for all $u,v,w\in M$ . It is well known that the monoid $C^{*}$ generated by a code $C$ over $A$ is stable in $A^{*}$ (see Proposition 2.2.5 in [1]).

A code $C$ over $A$ is called complete if, for any $w\in A^{*}$ , there exist $u,v\in A^{*}$ such that $uwv\in C^{*}$ , where $C^{*}$ is the monoid generated by $C$ . Recall that a complete code $C$ over $A$ is said to be synchronized if $x{A}^{*}\cap A^{*}y\subseteq C^{*}$ for some $x,y\in C^{*}$ (see details in Proposition 10.1.14 of [1]). On complete synchronized codes, Liu [3] obtained the following algebraic characterizations recently.

Lemma 5 (see [3]).

A complete code $C$ over $A$ is synchronized if and only if the kernel of $\text{Syn}(C^{*})$ is a rectangular band.

3. A Characterization of Complete Synchronized Codes

This section gives a characterization of complete synchronized codes by using the syntactic monoid $\text{Syn}(C^{+})$ of $C^{+}$ , the semigroup generated by a code $C$ over $A$ . To this aim, we need several lemmas.

Lemma 6.

Let $C$ be a code over $A$ .

(1)

For any $x,y\in A^{+}$ , $x{P}_{C^{+}}y$ if and only if $x{P}_{C^{*}}y$ .

(2)

The $P_{C^{+}}$ -class containing 1 is $\{\mathrm{1}\}$ .

(3)

$\text{Syn}(C^{+})\setminus \{\mathrm{1}{P}_{C^{+}}\}$ is a subsemigroup of $\text{Syn}(C^{+})$ .

Proof.

(1) This follows from the fact that $uxv\in C^{+}$ if and only if $uxv\in C^{*}$ for any $x\in A^{+}$ and $u,v\in A^{*}$ .

(2) Let $w\in A^{*}$ and $w{P}_{C^{+}}\mathrm{1}$ . Since $\mathrm{1}\notin C^{+}$ and $C^{+}$ is a union of some $P_{C^{+}}$ -classes, it follows that $w\notin C^{+}$ . On the other hand, for any $c\in C$ , we have $cw{P}_{C^{+}}c$ and $wc{P}_{C^{+}}c$ , whence $cw,wc,c\in C^{+}$ by the fact that $C^{+}$ is a union of some $P_{C^{+}}$ -classes. Since $C$ is a code over $A$ , $C^{*}$ is stable. Therefore, $w\in C^{*}$ . This implies that $w=\mathrm{1}$ . Thus, the $P_{C^{+}}$ -class containing 1 is $\{\mathrm{1}\}$ .

(3) This follows from (2).

Lemma 7.

Let $C$ be a code over $A$ . If the $P_{C^{*}}$ -class containing 1 is $\{\mathrm{1}\}$ , then $\text{Syn}(C^{*})\cong \text{Syn}(C^{+})$ . Otherwise, $\text{Syn}(C^{*})\cong \text{Syn}(C^{+})\setminus \{\mathrm{1}{P}_{C^{+}}\}$ .

Proof.

If the $P_{C^{*}}$ -class containing 1 is $\{\mathrm{1}\}$ , by items (1) and (2) in Lemma 6, $P_{C^{+}}=P_{C^{*}}$ in this case, and so $\text{Syn}(C^{*})$ is isomorphic to $\text{Syn}(C^{+})$ .

If the $P_{C^{*}}$ -class containing 1 is not $\{\mathrm{1}\}$ , then there exists $\alpha \in A^{+}$ such that $\mathrm{1}{P}_{C^{*}}\alpha$ . Moreover, $\text{Syn}(C^{+})\setminus \{\mathrm{1}{P}_{C^{+}}\}$ is a subsemigroup of $\text{Syn}(C^{+})$ by item (3) of Lemma 6. In the sequel, we show that the following $$\begin{array}{c}\text{(4)}& \psi :\text{Syn}\left(C^{*}\right)⟶\text{Syn}\left(C^{+}\right)\setminus \left\{\mathrm{1}{P}_{C^{+}}\right\},\left(x{P}_{C^{*}}\right)\psi =\{\begin{array}{cc}\alpha P_{C^{+}},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}x=\mathrm{1},\hfill \\ x{P}_{C^{+}},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}x\ne \mathrm{1},\hfill \end{array}\end{array}$$ is a semigroup isomorphism. We first show that $\psi$ is well defined. In fact, let $x,y\in A^{*}$ and $x{P}_{C^{*}}=y{P}_{C^{*}}$ . We divide the discussion into the following four cases.

(i)

$x=y=\mathrm{1}$ . In this case, $(x{P}_{C^{*}})\psi =(y{P}_{C^{*}})\psi =\alpha P_{C^{+}}$ .

(ii)

$x=\mathrm{1}$ , $y\ne \mathrm{1}$ . In this case, $(x{P}_{C^{*}})\psi =\alpha P_{C^{+}}$ and $(y{P}_{C^{*}})\psi =y{P}_{C^{+}}$ . Observe that $\alpha P_{C^{*}}\mathrm{1}=x{P}_{C^{*}}y$ ; it follows that $\alpha P_{C^{*}}y$ whence $\alpha P_{C^{+}}y$ from item (1) in Lemma 6. This implies that $(x{P}_{C^{*}})\psi =(y{P}_{C^{*}})\psi$ .

(iii)

$x\ne \mathrm{1}$ , $y=\mathrm{1}$ . This is the dual of case (ii).

(iv)

$x\ne \mathrm{1}$ , $y\ne \mathrm{1}$ . This follows from item (1) in Lemma 6.

By similar methods, we can show that $\psi$ is injective, and the surjectivity of $\psi$ is obvious.

On the other hand, for any $x{P}_{C^{*}},y{P}_{C^{*}}\in \text{Syn}(C^{*})$ , we assert that $$\begin{array}{}\text{(5)}& \left[\left(x{P}_{C^{*}}\right)\left(y{P}_{C^{*}}\right)\right]\psi =\left(x{P}_{C^{*}}\right)\psi \left(y{P}_{C^{*}}\right)\psi \end{array}$$ and so $\psi$ is a semigroup morphism. In fact, we have the following cases.

(a)

$x=y=\mathrm{1}$ . In this case, $$\begin{array}{c}\text{(6)}& \left[\left(x{P}_{C^{*}}\right)\left(y{P}_{C^{*}}\right)\right]\psi =\left(\mathrm{1}{P}_{C*}\right)\psi =\alpha P_{C^{+}},\left(x{P}_{C^{*}}\right)\psi \left(y{P}_{C^{*}}\right)\psi =\left(\alpha P_{C^{+}}\right)\left(\alpha P_{C^{+}}\right)={\alpha }^{\mathrm{2}}{P}_{C^{+}}.\end{array}$$ Observe that $\mathrm{1}{P}_{C^{*}}\alpha$ , ${\alpha }^{\mathrm{2}}{P}_{C^{*}}\alpha$ . This implies that ${\alpha }^{\mathrm{2}}{P}_{C^{+}}\alpha$ by item (1) in Lemma 6 whence $[(x{P}_{C^{*}})(y{P}_{C^{*}})]\psi =(x{P}_{C^{*}})\psi (y{P}_{C^{*}})\psi$ .

(b)

$x=\mathrm{1}$ , $y\ne \mathrm{1}$ . In this case, $$\begin{array}{c}\text{(7)}& \left[\left(x{P}_{C^{*}}\right)\left(y{P}_{C^{*}}\right)\right]\psi =\left(y{P}_{C^{*}}\right)\psi =y{P}_{C^{+}},\left(x{P}_{C^{*}}\right)\psi \left(y{P}_{C^{*}}\right)\psi =\left(\alpha P_{C^{+}}\right)\left(y{P}_{C^{+}}\right)=\left(\alpha y\right)P_{C^{+}}.\end{array}$$ Observe that $\mathrm{1}{P}_{C^{*}}\alpha$ , $y{P}_{C^{*}}\alpha y$ . This implies that $y{P}_{C^{+}}\alpha y$ by item (1) in Lemma 6 again whence $[(x{P}_{C^{*}})(y{P}_{C^{*}})]\psi =(x{P}_{C^{*}})\psi (y{P}_{C^{*}})\psi$ .

(c)

$x\ne \mathrm{1}$ , $y=\mathrm{1}$ . This is the dual of case (b).

(d)

$x\ne \mathrm{1}$ , $y\ne \mathrm{1}$ . This is obvious.

Lemma 8.

If $M$ is a monoid with identity 1 and $M\setminus \{\mathrm{1}\}$ is a subsemigroup of $M$ , then $M$ has a kernel if and only if $M\setminus \{\mathrm{1}\}$ has a kernel. If this is the case, the two kernels are equal.

Proof.

Observe that $$\begin{array}{}\text{(8)}& \left\{N\subseteq M\mid N\hspace{0.17em}\hspace{0.17em}\text{is}\hspace{0.17em}\hspace{0.17em}\text{an}\hspace{0.17em}\hspace{0.17em}\text{ideal}\hspace{0.17em}\hspace{0.17em}\text{of}\hspace{0.17em}\hspace{0.17em}M\right\}\hspace{1em}\hspace{1em}=\left\{N\subseteq M\setminus \left\{\mathrm{1}\right\}\mid N\hspace{0.17em}\hspace{0.17em}\text{is}\hspace{0.17em}\hspace{0.17em}\text{an}\hspace{0.17em}\hspace{0.17em}\text{ideal}\hspace{0.17em}\hspace{0.17em}\text{of}\hspace{0.17em}\hspace{0.17em}M\setminus \left\{\mathrm{1}\right\}\right\}\cup \left\{M\right\};\end{array}$$ the result follows.

Combining Lemmas 5, 6, 7, and 8, we have the following result.

Theorem 9.

A complete code $C$ over $A$ is a synchronized code if and only if the kernel of $\text{Syn}(C^{+})$ is a rectangular band.

4. Main Results

Let $I$ and $\mathrm{\Lambda }$ be two nonempty sets and $\varnothing \ne K\subseteq {�}^l(I)\hspace{0.17em}\times \hspace{0.17em}{�}^r(\mathrm{\Lambda })$ . Assume that $p_{\mathrm{1}}$ and $p_{\mathrm{2}}$ are the projections onto the first and second components of ${�}^l(I)\times {�}^r(\mathrm{\Lambda })$ , respectively. For $(i,\lambda ),(i_{\mathrm{0}},{\lambda }_{\mathrm{0}})\in I\times \mathrm{\Lambda }$ , we denote $$\begin{array}{}\text{(9)}& {\Omega }_{\left(i_{\mathrm{0}},{\lambda }_{\mathrm{0}}\right)}^{\left(i,\lambda \right)}=\left\{\left(F,\mathrm{\Phi }\right)\in p_{\mathrm{1}}\left(K\right)\times p_{\mathrm{2}}\left(K\right)\mid \left(Fi,\lambda \mathrm{\Phi }\right)=\left(i_{\mathrm{0}},{\lambda }_{\mathrm{0}}\right)\right\}.\end{array}$$

Theorem 10.

Let $C$ be a complete synchronized code over an alphabet $A$ such that $C\ne A$ and $C^{+}$ is a $P_{C^{+}}$ -class. Then $\text{Syn}(C^{+})$ is isomorphic to a submonoid $K$ of ${�}^l(I)\times {�}^r(\mathrm{\Lambda })$ for some nonempty sets $I$ and $\mathrm{\Lambda }$ with $(|I|,|\mathrm{\Lambda }|)\ne (\mathrm{1,1})$ , and the following conditions hold:

(1)

${�}_{\mathrm{0}}^r(I)\times {�}_{\mathrm{0}}^r(\mathrm{\Lambda })\subseteq K$ ,

(2)

$K\setminus \{({\iota }_I,{\iota }_{\mathrm{\Lambda }})\}$ is a subsemigroup of $K$ ,

(3)

there exists $(i_{\mathrm{0}},{\lambda }_{\mathrm{0}})\in I\times \mathrm{\Lambda }$ such that the identity ${\Omega }_{(i_{\mathrm{0}},{\lambda }_{\mathrm{0}})}^{(i,\lambda )}={\Omega }_{(i_{\mathrm{0}},{\lambda }_{\mathrm{0}})}^{(j,\mu )}$ implies that $(i,\lambda )=(j,\mu )$ for all $(i,\lambda ),(j,\mu )\in I\times \mathrm{\Lambda }$ and the identity $(F{i}_{\mathrm{0}},{\lambda }_{\mathrm{0}}\mathrm{\Phi })=(i_{\mathrm{0}},{\lambda }_{\mathrm{0}})$ implies that $(F,\mathrm{\Phi })\in \{({\iota }_I,{\iota }_{\mathrm{\Lambda }}),(⟨i_{\mathrm{0}}⟩,⟨{\lambda }_{\mathrm{0}}⟩)\}$ for all $(F,\mathrm{\Phi })\in K$ .

The above submonoid $K$ will be called $(i_{\mathrm{0}},{\lambda }_{\mathrm{0}})$ -submonoid of ${�}^l(I)\times {�}^r(\mathrm{\Lambda })$ .

Proof.

Let $M=\text{Syn}(C^{+})$ and denote the set of $P_{C^{+}}$ -classes with representatives from $T$ by $\overline{T}$ for $T\subseteq A^{*}$ . Since $C^{+}$ is a $P_{C^{+}}$ -class, we can also let $e=\overline{C^{+}}$ . Obviously, $e$ is an idempotent in $M$ .

We first assert that $\{e,\overline{\mathrm{1}}\}$ is stable and $e$ is disjunctive in $M$ . Let $w\in A^{*}$ and $c\in C$ . Then $e=\stackrel{-}{c}$ . If $\overline{w}\overline{\mathrm{1}},\overline{\mathrm{1}}\overline{w}\in \{e,\overline{\mathrm{1}}\}$ , then $\overline{w}\in \{e,\overline{\mathrm{1}}\}$ obviously. Moreover, let $\overline{w}e,e\overline{w}\in \{e,\overline{\mathrm{1}}\}$ . Since the $P_{C^{+}}$ -class containing 1 is $\{\mathrm{1}\}$ by Lemma 6, we have $e=\overline{w}e=e\overline{w}$ . This implies that $\overline{c}=\overline{wc}=\overline{cw}$ . Since $C^{+}$ is a single $P_{C^{+}}$ -class, we have $wc,cw,c\in C^{+}$ . Because $C^{*}$ is stable, it follows that $w\in C^{*}$ . This implies that $\overline{w}\in \{e,\overline{\mathrm{1}}\}$ . On the other hand, let $p,q\in A^{*}$ and $\overline{p}{P}_e\overline{q}$ in $M$ . Then for all $s,t\in A^{*}$ , $\overline{spt}=e=\overline{C^{+}}$ if and only if $\overline{sqt}=e=\overline{C^{+}}$ . Since $C^{+}$ is a single $P_{C^{+}}$ -class, it follows that $spt\in C^{+}$ if and only if $sqt\in C^{+}$ , and so $p{P}_{C^{+}}q$ . Thus $\overline{p}=\overline{q}$ .

Now, let $J=MeM$ . We assert that $J$ is the kernel of $M$ . In fact, $J$ is an ideal of $M$ clearly. Moreover, since $C$ is complete, there exist $u,v\in A^{*}$ such that $uwv\in C^{+}$ for all $w\in A^{*}$ . Therefore, there exist $m,n\in M$ such that $mxn=e$ for all $x\in M$ . Now, let $I$ be an ideal of $M$ and $x\in I$ . Then $uxv=e$ for some $u,v\in M$ whence $J=MeM=MuxvM\subseteq I$ . Thus, $J$ is the least ideal of $M$ and so is the kernel of $M$ . By Theorem 9, $J$ is a rectangular band.

If $J=\{e\}$ , then we have $em=me=e$ for any $m\in M$ . This implies that $\stackrel{-}{c}\hspace{0.17em}\stackrel{-}{w}=\stackrel{-}{w}\hspace{0.17em}\hspace{0.17em}\stackrel{-}{c}=\stackrel{-}{c}$ for all $c\in C$ and $w\in A^{*}$ . Since $C^{+}$ is a single $P_{C^{+}}$ -class, it follows that $wc,cw,c\in C^{+}$ . Because $C^{*}$ is stable, we have $w\in C^{*}$ . Therefore, $C^{*}=A^{*}$ and hence $C=A$ . A contradiction. Thus, $J\ne \{e\}$ . Now let $\rho$ be a congruence on $M$ whose restriction to $J$ is the identity relation on $J$ . Assume that $x\in M$ and $x\rho e$ . Then $xe\rho e\rho ex$ , where $e,xe,ex\in J$ and thus $e=xe=ex$ . Since $\{e,\overline{\mathrm{1}}\}$ is stable in $M$ , it follows that $x\in \{e,\overline{\mathrm{1}}\}$ . If $x=\overline{\mathrm{1}}$ , then $\overline{\mathrm{1}}\rho e$ and for any $y\in J$ , we obtain $y\rho ye$ , $y\rho ey$ , and $ye,y,ey\in J$ , whence $y=ye=ey$ . Thus, $J$ is a rectangular band with the identity $e$ . And hence, $J=\{e\}$ by Lemma 1. A contradiction. It follows that $x=e$ and $\{e\}$ is a $\rho$ -class in $M$ . Now, let $x,y\in M$ and $x\rho y$ . Then for any $u,v\in M$ , we have $uxv\rho uyv$ . Observe that $\{e\}$ is a $\rho$ -class, it follows that $uxv=e$ if and only if $uyv=e$ . Therefore, $x{P}_{e}y$ in $M$ . By the disjunctiveness of $e$ in $M$ , we have $x=y$ . We conclude that $\rho$ is the equality relation on $M$ . Thus, $M$ is a dense extension of $J$ .

By Lemma 4, $M$ is isomorphic to a subsemigroup of $\Omega (J)$ containing the inner part $\Pi (J)$ as an ideal. Since $J$ is a rectangular band, $J$ is isomorphic to the product $I\times \mathrm{\Lambda }$ of a left zero semigroup $I$ and a right zero semigroup $\mathrm{\Lambda }$ . Observe that $J\ne \{e\}$ , $|J|=|I\times \mathrm{\Lambda }|>\mathrm{1}$ , whence $(|I|,|\mathrm{\Lambda }|)\ne (\mathrm{1,1})$ . By Lemma 3, $\Omega (I\times \mathrm{\Lambda })\cong {�}^l(I)\times {�}^r(\mathrm{\Lambda })$ , and in this isomorphism $\Pi (I\times \mathrm{\Lambda })\cong {�}_{\mathrm{0}}^l(I)\times {�}_{\mathrm{0}}^r(\mathrm{\Lambda })$ . Therefore, $M$ is isomorphic to a subsemigroup $K$ of ${�}^l(I)\times {�}^r(\mathrm{\Lambda })$ and $K$ contains ${�}_{\mathrm{0}}^l(I)\times {�}_{\mathrm{0}}^r(\mathrm{\Lambda })$ as an ideal. Furthermore, since $M$ is a monoid, $K$ has an identity. Let $(F,\mathrm{\Phi })$ be the identity of $K$ . Then for any $(⟨i⟩,⟨\lambda ⟩)\in {�}_{\mathrm{0}}^l(I)\times {�}_{\mathrm{0}}^r(\mathrm{\Lambda })$ , $$\begin{array}{}\text{(10)}& \left(F,\mathrm{\Phi }\right)\left(⟨i⟩,⟨\lambda ⟩\right)=\left(⟨i⟩,⟨\lambda ⟩\right)\left(F,\mathrm{\Phi }\right)=\left(⟨i⟩,⟨\lambda ⟩\right),\end{array}$$ whence $(Fi,\lambda \mathrm{\Phi })=(i,\lambda )$ . This implies that $(F,\mathrm{\Phi })=({\iota }_I,{\iota }_{\mathrm{\Lambda }})$ . Thus, $K$ is a submonoid of ${�}^l(I)\times {�}^r(\mathrm{\Lambda })$ . Since $M\setminus \{\mathrm{1}\}$ is a subsemigroup of $M$ , it follows that $K\setminus \{({\iota }_I,{\iota }_{\mathrm{\Lambda }})\}$ is a subsemigroup of $K$ . Thus, Conditions (1) and (2) hold.

Since $J$ is the kernel of $M$ and $e$ is an idempotent in $J$ , it follows that the image of $e$ in $K$ is the form $a=(⟨i_{\mathrm{0}}⟩,⟨{\lambda }_{\mathrm{0}}⟩)$ for some $i_{\mathrm{0}}\in I$ and ${\lambda }_{\mathrm{0}}\in \mathrm{\Lambda }$ . Since $e$ is disjunctive in $M$ , $a$ is disjunctive in $K$ . Let $(i,\lambda ),(j,\mu )\in I\times \mathrm{\Lambda }$ and ${\Omega }_{(i_{\mathrm{0}},{\lambda }_{\mathrm{0}})}^{(i,\lambda )}={\Omega }_{(i_{\mathrm{0}},{\lambda }_{\mathrm{0}})}^{(j,\mu )}$ . Then, $$\begin{array}{}\text{(11)}& \left(Fi,\lambda \mathrm{\Phi }\right)=\left(i_{\mathrm{0}},{\lambda }_{\mathrm{0}}\right)\hspace{1em}\text{iff}\hspace{0.17em}\hspace{0.17em}\left(Fj,\mu \mathrm{\Phi }\right)=\left(i_{\mathrm{0}},{\lambda }_{\mathrm{0}}\right)\end{array}$$ for any $(F,\mathrm{\Phi })\in p_{\mathrm{1}}(M)\times p_{\mathrm{2}}(M)$ . This implies that $$\begin{array}{}\text{(12)}& \left(⟨Fi⟩,⟨\lambda \mathrm{\Phi }⟩\right)=a\hspace{1em}\text{iff}\hspace{0.17em}\hspace{0.17em}\left(⟨Fj⟩,⟨\mu \mathrm{\Phi }⟩\right)=a,\end{array}$$ for any $(F,\mathrm{\Phi })\in p_{\mathrm{1}}(M)\times p_{\mathrm{2}}(M)$ . Thus, $$\begin{array}{}\text{(13)}& \left(F,\mathrm{\Psi }\right)\left(⟨i⟩,⟨\lambda ⟩\right)\left(G,\mathrm{\Phi }\right)=a\hspace{1em}\text{iff}\hspace{0.17em}\hspace{0.17em}\left(F,\mathrm{\Psi }\right)\left(⟨j⟩,⟨\mu ⟩\right)\left(G,\mathrm{\Phi }\right)=a,\end{array}$$ for any $(F,\mathrm{\Psi }),(G,\mathrm{\Phi })\in K$ . This shows that $(⟨i⟩,⟨\lambda ⟩)P_a(⟨j⟩,⟨\mu ⟩)$ and so $(⟨i⟩,⟨\lambda ⟩)=(⟨j⟩,⟨\mu ⟩)$ since $a$ is disjunctive in $K$ . Thus $(i,\lambda )=(j,\mu )$ .

Finally, let $(F,\mathrm{\Phi })\in K$ and $(F{i}_{\mathrm{0}},{\lambda }_{\mathrm{0}}\mathrm{\Phi })=(i_{\mathrm{0}},{\lambda }_{\mathrm{0}})$ . Then, $$\begin{array}{}\text{(14)}& \left(F,\mathrm{\Phi }\right)\left(⟨i_{\mathrm{0}}⟩,⟨{\lambda }_{\mathrm{0}}⟩\right)=\left(⟨F{i}_{\mathrm{0}}⟩,⟨{\lambda }_{\mathrm{0}}⟩\right)=\left(⟨i_{\mathrm{0}}⟩,⟨{\lambda }_{\mathrm{0}}⟩\right).\end{array}$$ Dually, we have $(⟨i_{\mathrm{0}}⟩,⟨{\lambda }_{\mathrm{0}}⟩)(F,\mathrm{\Phi })=(⟨i_{\mathrm{0}}⟩,⟨{\lambda }_{\mathrm{0}}⟩)$ . Since $e$ is stable in $M$ , it follows that $a$ is stable in $K$ . Hence, $(F,\mathrm{\Phi })\in \{(⟨i_{\mathrm{0}}⟩,⟨{\lambda }_{\mathrm{0}}⟩),({\iota }_I,{\iota }_{\mathrm{\Lambda }})\}$ . Therefore, Condition (3) is also satisfied.

We end our paper by giving an example to illustrate our result.

Example 11.

Let $A=\{a,b\}$ and $C=b^{*}{a}^{+}b$ . Then $C^{+}=A^{*}ab$ . It is routine to check that $C$ is a synchronized code and $C^{+}$ is a single $P_L$ -class. Moreover, we can also check that $\text{Syn}(C^{+})=\{\overline{A^{*}ab},\overline{A^{*}bb},\overline{A^{*}a},\overline{b},\overline{\mathrm{1}}\}$ .

On the other hand, let $I=\{\mathrm{1}\}$ and $\mathrm{\Lambda }=\{\mathrm{1,2},\mathrm{3}\}$ . Denote $$\begin{array}{}\text{(15)}& M_{\mathrm{1}}=\left\{\left(⟨\mathrm{1}⟩,⟨\mathrm{1}⟩\right),\left(⟨\mathrm{1}⟩,⟨\mathrm{2}⟩\right),\left(⟨\mathrm{1}⟩,⟨\mathrm{3}⟩\right),\left(⟨\mathrm{1}⟩,\alpha \right),\left({\iota }_I,{\iota }_{\mathrm{\Lambda }}\right)\right\},\end{array}$$ where $$\begin{array}{}\text{(16)}& \alpha :\mathrm{\Lambda }⟶\mathrm{\Lambda },\mathrm{1}\mapsto \mathrm{2,2}\mapsto \mathrm{2,3}\mapsto \mathrm{1}.\end{array}$$ Then $M_{\mathrm{1}}$ is a $(\mathrm{1,1})$ -submonoid of ${�}^l(I)\times {�}^r(\mathrm{\Lambda })$ . In fact, observe that ${\alpha }^{\mathrm{2}}=⟨\mathrm{2}⟩$ , $M_{\mathrm{1}}$ is submonoid of ${�}^l(I)\times {�}^r(\mathrm{\Lambda })$ , and $M_{\mathrm{1}}\setminus \{({\iota }_I,{\iota }_{\mathrm{\Lambda }})\}$ is a subsemigroup of $M_{\mathrm{1}}$ . Let $\lambda ,\mu \in \mathrm{\Lambda }$ . If $\lambda =\mathrm{1}$ , $\mu =\mathrm{2}$ or $\lambda =\mathrm{1}$ , $\mu =\mathrm{3}$ , then there exists $\mathrm{\Phi }={\iota }_{\mathrm{\Lambda }}\in p_{\mathrm{2}}(M_{\mathrm{1}})$ such that $\lambda \mathrm{\Phi }=\mathrm{1}$ , $\mu \mathrm{\Phi }=\mu$ . If $\lambda =\mathrm{2}$ , $\mu =\mathrm{3}$ , then there exists $\mathrm{\Phi }=\alpha \in p_{\mathrm{2}}(M_{\mathrm{1}})$ such that $\lambda \mathrm{\Phi }=\mathrm{2}$ , $\mu \mathrm{\Phi }=\mathrm{1}$ . Furthermore, if $(F,\mathrm{\Phi })\in M_{\mathrm{1}}$ with $F\mathrm{1}=\mathrm{1}$ , $\mathrm{1}\mathrm{\Phi }=\mathrm{1}$ , then $F=⟨\mathrm{1}⟩={\iota }_I$ and $\mathrm{\Phi }=⟨\mathrm{1}⟩$ or $\mathrm{\Phi }={\iota }_{\mathrm{\Lambda }}$ . Thus, $M_{\mathrm{1}}$ is a $(\mathrm{1,1})$ -submonoid of ${�}^l(I)\times {�}^r(\mathrm{\Lambda })$ . It is easy to see that $$\begin{array}{}\text{(17)}& \psi :\text{Syn}\left(C^{+}\right)⟶M_{\mathrm{1}},\hspace{0.17em}\hspace{0.17em}\overline{A^{*}ab}\mapsto \left(⟨\mathrm{1}⟩,⟨\mathrm{1}⟩\right),\overline{A^{*}bb}\mapsto \left(⟨\mathrm{1}⟩,⟨\mathrm{2}⟩\right),\hspace{0.17em}\hspace{0.17em}\overline{A^{*}a}\mapsto \left(⟨\mathrm{1}⟩,⟨\mathrm{3}⟩\right),\overline{b}\mapsto \left(⟨\mathrm{1}⟩,\alpha \right),\hspace{0.17em}\hspace{0.17em}\overline{\mathrm{1}}\mapsto \left({\iota }_I,{\iota }_{\mathrm{\Lambda }}\right)\end{array}$$ is an isomorphism from $\text{Syn}(C^{+})$ onto $M_{\mathrm{1}}$ .

Acknowledgments

The author expresses his profound gratitude to Professor Liu Yun for his helpful suggestions in preparing this paper. This research work is supported by the NSF Grants of China (11226049, 11301470) and the NSF Grant of Yunnan Province of China (2012FB139).

References

[1] J. Berstel, D. Perrin, C. Reutenauer, Codes and Automata, 2010.

[2] D. Long, "On group codes," Theoretical Computer Science, vol. 163 no. 1-2, pp. 259-267, 1996.

[3] Y. Liu, "Completely simple codes," Semigroup Forum, vol. 85, pp. 417-438, DOI: 10.1007/s00233-011-9351-5, 2012.

[4] M. Petrich, C. M. Reis, G. Thierrin, "The syntactic monoid of the semigroup generated by a maximal prefix code," Proceedings of the American Mathematical Society, vol. 124 no. 3, pp. 655-663, 1996.

[5] Y. Liu, "Compositions of maximal codes," Theoretical Computer Science, vol. 411 no. 1, pp. 228-238, DOI: 10.1016/j.tcs.2009.09.031, 2010.

[6] M. Petrich, N. R. Reilly, Completely Regular Semigroups, 1999.

[7] M. Petrich, Introduction to Semigroups, 1973.