# On the Syntactic Monoids Associated with a Class of Synchronized Codes

Authors: Shou-feng Wang
Journal: The Scientific World Journal
 (2013)

---

## Abstract

A complete codeC over an alphabet A is called synchronized if there exist x,y∈C* such that xA*∩A*y⊆C*. In this paper we describe the syntactic monoid 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 PC+. In particular, we prove that, for such a code C, either C=A or Syn(C+) is isomorphic to a special submonoid of 𝒯l(I)×𝒯r(Λ), where 𝒯l(I) and 𝒯r(Λ) are the full transformation semigroups on the nonempty sets I and Λ, respectively.


---

## Body

## 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 Syn(C+) of C+, the semigroup generated by a maximal prefix code C for which C+ is a single class of the syntactic congruence PC+.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 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 PC+.


## 2. Preliminaries

A semigroupS is a left zero semigroup if ab=a for any a,b∈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]).
LetS be a rectangular band. Then axa=a for any a,x∈S. As a consequence, aSa={a} for any a∈S. In particular, if S has an identity e, then S={e}.Anideal 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 ofS. For the kernel of a semigroup, we have the following.Lemma 2 (see [6]).
If the kernel of a semigroupS only consists of idempotents, then this kernel is a rectangular band.LetS be a semigroup. A function λ (resp., ρ) on S is a left translation (resp., right translation) of S if λ(xy)=(λx)y (resp., (xy)ρ=x(yρ)) for all x,y∈S. A left translation λ and a right translation ρ are linked if x(λy)=(xρ)y in which case the pair (λ,ρ) is a bitranslation of S. Denote the set of left translations and that of right translations on S by Λ(S) and P(S), respectively. Clearly, Λ(S) forms a monoid under the usual composition of functions: (λλ′)x=λ(λ′x) for all x∈S. Dually, P(S) forms a monoid under the usual composition of functions: x(ρρ′)=(xρ)ρ′ for all x∈S. The set of all bitranslations of S forms a submonoid of the direct product Λ(S)×P(S), which is called the translation hull of S, to be denoted by Ω(S).Lets be an element of a semigroup S. Then the function λs defined by λsx=sx for all x∈S is the inner left translation induced bys. Dually, we have inner right translationρsinduced bys. Finally, the pair πs=(λs,ρs) is the inner bitranslation induced bys. The set Π(S) of all inner bitranslations is the inner part ofΩ(S). From Corollary III.1.7 in Petrich [7], Π(S) is an ideal of Ω(S).In the sequel, the set of all transformations on a setQ 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 ιQ. If q∈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 𝒯0l(Q)={〈q〉∣q∈Q} (as left operators) and 𝒯0r(Q)={〈q〉∣q∈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]).
LetI×Λ be a rectangular band.(1)
Ω(I×Λ)≅𝒯l(I)×𝒯r(Λ).(2)
I×Λ≅Π(I×Λ)≅𝒯0l(I)×𝒯0r(Λ).(3)
𝒯0l(I)×𝒯0r(Λ) is the kernel of 𝒯l(I)×𝒯r(Λ).LetS 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 ρ on S, the fact that the restriction of ρ to J is the equality relation on J implies that ρ 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.
IfS is a dense extension of a rectangular band J, then the following semigroup homomorphism
(1)τ:S⟶Ω(J),s↦sτ=(λs,ρs)
is injective, where for each s∈S,
(2)λs:J⟶J,j↦sj,ρs:J⟶J,j↦js.
Clearly in this case, S is isomorphic to Sτ which contains Π(J) as an ideal.
LetS be a semigroup and let S1 be the semigroup obtained from S by adjoining an identity if necessary. The syntactic congruence PL determined by a subset L of S is the following relation on S: {(x,y)∈S×S∣uxv∈L if and only if uyv∈L for all u,v∈S1}. In particular, if L={x}, we call  P{x}  the syntactic congruence determined byx and denote it by Px. Moreover, x is called disjunctive in S if Px is the equality relation on S. It is easy to see that the relation  PL  saturates  L for every subset L of S; that is, L is a union of some PL-classes for every subset L of S.LetA be an alphabet, let A* be the free monoid generated by A, and let 1 be the identity of A*. For any L⊆A*, the quotient monoid A*/PL is called the syntactic monoid ofL, to be denoted by Syn(L). A nonempty set C of A+=A*∖{1} is called a code over A if the fact that
(3)x1x2⋯xm=y1y2⋯yn,xi,yj∈C,i=1,2,…,m,222222222222222222222222222222222j=1,2,…,n,
implies that m=n and xi=yi, i=1,2,…,n.A submonoidS of a monoid M is called stable in M if the fact that u,wu,uw∈S implies that w∈S for all u,v,w∈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 codeC over A is called complete if, for any w∈A*, there exist u,v∈A* such that uwv∈C*, where C* is the monoid generated by C. Recall that a complete code C over A is said to be synchronized if xA*∩A*y⊆C* for some x,y∈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 codeC over A is synchronized if and only if the kernel of 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 monoidSyn(C+) of C+, the semigroup generated by a code C over A. To this aim, we need several lemmas.Lemma 6.
LetC be a code over A.(1)
For anyx,y∈A+, xPC+y if and only if xPC*y.(2)
ThePC+-class containing 1 is {1}.(3)
Syn(C+)∖{1PC+} is a subsemigroup of Syn(C+).Proof.
(1) This follows from the fact thatuxv∈C+ if and only if uxv∈C* for any x∈A+ and u,v∈A*.
(2) Letw∈A* and wPC+1. Since 1∉C+ and C+ is a union of some PC+-classes, it follows that w∉C+. On the other hand, for any c∈C, we have cwPC+c and wcPC+c, whence cw,wc,c∈C+ by the fact that C+ is a union of some PC+-classes. Since C is a code over A, C* is stable. Therefore, w∈C*. This implies that w=1. Thus, the PC+-class containing 1 is {1}.
(3) This follows from (2).Lemma 7.
LetC be a code over A. If the PC*-class containing 1 is {1}, then Syn(C*)≅Syn(C+). Otherwise, Syn(C*)≅Syn(C+)∖{1PC+}.Proof.
If thePC*-class containing 1 is {1}, by items (1) and (2) in Lemma 6, PC+=PC* in this case, and so Syn(C*) is isomorphic to Syn(C+).
If thePC*-class containing 1 is not {1}, then there exists α∈A+ such that 1PC*α. Moreover, Syn(C+)∖{1PC+} is a subsemigroup of Syn(C+) by item (3) of Lemma 6. In the sequel, we show that the following
(4)ψ:Syn(C*)⟶Syn(C+)∖{1PC+},(xPC*)ψ={αPC+,ifx=1,xPC+,ifx≠1,
is a semigroup isomorphism. We first show that ψ is well defined. In fact, let x,y∈A* and xPC*=yPC*. We divide the discussion into the following four cases.(i)
x=y=1. In this case, (xPC*)ψ=(yPC*)ψ=αPC+.(ii)
x=1, y≠1. In this case, (xPC*)ψ=αPC+ and (yPC*)ψ=yPC+. Observe that αPC*1=xPC*y; it follows that αPC*y whence αPC+y from item (1) in Lemma 6. This implies that (xPC*)ψ=(yPC*)ψ.(iii)
x≠1, y=1. This is the dual of case (ii).(iv)
x≠1, y≠1. This follows from item (1) in Lemma 6.
By similar methods, we can show thatψ is injective, and the surjectivity of ψ is obvious.
On the other hand, for anyxPC*,yPC*∈Syn(C*), we assert that
(5)[(xPC*)(yPC*)]ψ=(xPC*)ψ(yPC*)ψ
and so ψ is a semigroup morphism. In fact, we have the following cases.(a)
x=y=1. In this case,
(6)[(xPC*)(yPC*)]ψ=(1PC*)ψ=αPC+,(xPC*)ψ(yPC*)ψ=(αPC+)(αPC+)=α2PC+.
Observe that 1PC*α, α2PC*α. This implies that α2PC+α by item (1) in Lemma 6 whence [(xPC*)(yPC*)]ψ=(xPC*)ψ(yPC*)ψ.(b)
x=1, y≠1. In this case,
(7)[(xPC*)(yPC*)]ψ=(yPC*)ψ=yPC+,(xPC*)ψ(yPC*)ψ=(αPC+)(yPC+)=(αy)PC+.
Observe that 1PC*α, yPC*αy. This implies that yPC+αy by item (1) in Lemma 6 again whence [(xPC*)(yPC*)]ψ=(xPC*)ψ(yPC*)ψ.(c)
x≠1, y=1. This is the dual of case (b).(d)
x≠1, y≠1. This is obvious.Lemma 8.
IfM is a monoid with identity 1 and M∖{1} is a subsemigroup of M, then M has a kernel if and only if M∖{1} has a kernel. If this is the case, the two kernels are equal.Proof.
Observe that(8){N⊆M∣NisanidealofM}={N⊆M∖{1}∣NisanidealofM∖{1}}∪{M};
the result follows.Combining Lemmas5, 6, 7, and 8, we have the following result.Theorem 9.
A complete codeC over A is a synchronized code if and only if the kernel of Syn(C+) is a rectangular band.


## 4. Main Results

LetI and Λ be two nonempty sets and ∅≠K⊆𝒯l(I)×𝒯r(Λ). Assume that p1 and p2 are the projections onto the first and second components of 𝒯l(I)×𝒯r(Λ), respectively. For (i,λ),(i0,λ0)∈I×Λ, we denote
(9)Ω(i0,λ0)(i,λ)={(F,Φ)∈p1(K)×p2(K)∣(Fi,λΦ)=(i0,λ0)}.Theorem 10.
LetC be a complete synchronized code over an alphabet A such that C≠A and C+ is a PC+-class. Then Syn(C+) is isomorphic to a submonoid K of 𝒯l(I)×𝒯r(Λ) for some nonempty sets I and Λ with (|I|,|Λ|)≠(1,1), and the following conditions hold:(1)
𝒯0r(I)×𝒯0r(Λ)⊆K,(2)
K∖{(ιI,ιΛ)} is a subsemigroup of K,(3)
there exists(i0,λ0)∈I×Λ such that the identity Ω(i0,λ0)(i,λ)=Ω(i0,λ0)(j,μ) implies that (i,λ)=(j,μ) for all (i,λ),(j,μ)∈I×Λ and the identity (Fi0,λ0Φ)=(i0,λ0) implies that (F,Φ)∈{(ιI,ιΛ),(〈i0〉,〈λ0〉)} for all (F,Φ)∈K.
The above submonoidK will be called (i0,λ0)-submonoid of 𝒯l(I)×𝒯r(Λ).Proof.
LetM=Syn(C+) and denote the set of PC+-classes with representatives from T by T¯ for T⊆A*. Since C+ is a PC+-class, we can also let e=C+¯. Obviously, e is an idempotent in M.
We first assert that{e,1¯} is stable and e is disjunctive in M. Let w∈A* and c∈C. Then e=c-. If w¯1¯,1¯w¯∈{e,1¯}, then w¯∈{e,1¯} obviously. Moreover, let w¯e,ew¯∈{e,1¯}. Since the PC+-class containing 1 is {1} by Lemma 6, we have e=w¯e=ew¯. This implies that c¯=wc¯=cw¯. Since C+ is a single PC+-class, we have wc,cw,c∈C+. Because C* is stable, it follows that w∈C*. This implies that w¯∈{e,1¯}. On the other hand, let p,q∈A* and p¯Peq¯ in M. Then for all s,t∈A*, spt¯=e=C+¯ if and only if sqt¯=e=C+¯. Since C+ is a single PC+-class, it follows that spt∈C+ if and only if sqt∈C+, and so pPC+q. Thus p¯=q¯.
Now, letJ=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∈A* such that uwv∈C+ for all w∈A*. Therefore, there exist m,n∈M such that mxn=e for all x∈M. Now, let I be an ideal of M and x∈I. Then uxv=e for some u,v∈M whence J=MeM=MuxvM⊆I. Thus, J is the least ideal of M and so is the kernel of M. By Theorem 9, J is a rectangular band.
IfJ={e}, then we have em=me=e for any m∈M. This implies that c-w-=w-c-=c- for all c∈C and w∈A*. Since C+ is a single PC+-class, it follows that wc,cw,c∈C+. Because C* is stable, we have w∈C*. Therefore, C*=A* and hence C=A. A contradiction. Thus, J≠{e}. Now let ρ be a congruence on M whose restriction to J is the identity relation on J. Assume that x∈M and xρe. Then xeρeρex, where e,xe,ex∈J and thus e=xe=ex. Since {e,1¯} is stable in M, it follows that x∈{e,1¯}. If x=1¯, then 1¯ρe and for any y∈J, we obtain yρye, yρey, and ye,y,ey∈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 ρ-class in M. Now, let x,y∈M and xρy. Then for any u,v∈M, we have uxvρuyv. Observe that {e} is a ρ-class, it follows that uxv=e if and only if uyv=e. Therefore, xPey in M. By the disjunctiveness of e in M, we have x=y. We conclude that ρ is the equality relation on M. Thus, M is a dense extension of J.
By Lemma4, M is isomorphic to a subsemigroup of Ω(J) containing the inner part Π(J) as an ideal. Since J is a rectangular band, J is isomorphic to the product I×Λ of a left zero semigroup I and a right zero semigroup Λ. Observe that J≠{e}, |J|=|I×Λ|>1, whence (|I|,|Λ|)≠(1,1). By Lemma 3, Ω(I×Λ)≅𝒯l(I)×𝒯r(Λ), and in this isomorphism Π(I×Λ)≅𝒯0l(I)×𝒯0r(Λ). Therefore, M is isomorphic to a subsemigroup K of 𝒯l(I)×𝒯r(Λ) and K contains 𝒯0l(I)×𝒯0r(Λ) as an ideal. Furthermore, since M is a monoid, K has an identity. Let (F,Φ) be the identity of K. Then for any (〈i〉,〈λ〉)∈𝒯0l(I)×𝒯0r(Λ),
(10)(F,Φ)(〈i〉,〈λ〉)=(〈i〉,〈λ〉)(F,Φ)=(〈i〉,〈λ〉),
whence (Fi,λΦ)=(i,λ). This implies that (F,Φ)=(ιI,ιΛ). Thus, K is a submonoid of 𝒯l(I)×𝒯r(Λ). Since M∖{1} is a subsemigroup of M, it follows that K∖{(ιI,ιΛ)} is a subsemigroup of K. Thus, Conditions (1) and (2) hold.
SinceJ 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=(〈i0〉,〈λ0〉) for some i0∈I and λ0∈Λ. Since e is disjunctive in M, a is disjunctive in K. Let (i,λ),(j,μ)∈I×Λ and Ω(i0,λ0)(i,λ)=Ω(i0,λ0)(j,μ). Then,
(11)(Fi,λΦ)=(i0,λ0)iff(Fj,μΦ)=(i0,λ0)
for any (F,Φ)∈p1(M)×p2(M). This implies that
(12)(〈Fi〉,〈λΦ〉)=aiff(〈Fj〉,〈μΦ〉)=a,
for any (F,Φ)∈p1(M)×p2(M). Thus,
(13)(F,Ψ)(〈i〉,〈λ〉)(G,Φ)=aiff(F,Ψ)(〈j〉,〈μ〉)(G,Φ)=a,
for any (F,Ψ),(G,Φ)∈K. This shows that (〈i〉,〈λ〉)Pa(〈j〉,〈μ〉) and so (〈i〉,〈λ〉)=(〈j〉,〈μ〉) since a is disjunctive in K. Thus (i,λ)=(j,μ).
Finally, let(F,Φ)∈K and (Fi0,λ0Φ)=(i0,λ0). Then,
(14)(F,Φ)(〈i0〉,〈λ0〉)=(〈Fi0〉,〈λ0〉)=(〈i0〉,〈λ0〉).
Dually, we have (〈i0〉,〈λ0〉)(F,Φ)=(〈i0〉,〈λ0〉). Since e is stable in M, it follows that a is stable in K. Hence, (F,Φ)∈{(〈i0〉,〈λ0〉),(ιI,ιΛ)}. Therefore, Condition (3) is also satisfied.We end our paper by giving an example to illustrate our result.Example 11.
LetA={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 PL-class. Moreover, we can also check that Syn(C+)={A*ab¯,A*bb¯,A*a¯,b¯,1¯}.
On the other hand, letI={1} and Λ={1,2,3}. Denote
(15)M1={(〈1〉,〈1〉),(〈1〉,〈2〉),(〈1〉,〈3〉),(〈1〉,α),(ιI,ιΛ)},
where
(16)α:Λ⟶Λ,1↦2,2↦2,3↦1.
Then M1 is a (1,1)-submonoid of 𝒯l(I)×𝒯r(Λ). In fact, observe that α2=〈2〉, M1 is submonoid of 𝒯l(I)×𝒯r(Λ), and M1∖{(ιI,ιΛ)} is a subsemigroup of M1. Let λ,μ∈Λ. If λ=1, μ=2 or λ=1, μ=3, then there exists Φ=ιΛ∈p2(M1) such that λΦ=1, μΦ=μ. If λ=2, μ=3, then there exists Φ=α∈p2(M1) such that λΦ=2, μΦ=1. Furthermore, if (F,Φ)∈M1 with F1=1, 1Φ=1, then F=〈1〉=ιI and Φ=〈1〉 or Φ=ιΛ. Thus, M1 is a (1,1)-submonoid of 𝒯l(I)×𝒯r(Λ). It is easy to see that
(17)ψ:Syn(C+)⟶M1,A*ab¯↦(〈1〉,〈1〉),A*bb¯↦(〈1〉,〈2〉),A*a¯↦(〈1〉,〈3〉),b¯↦(〈1〉,α),1¯↦(ιI,ιΛ)
is an isomorphism from Syn(C+) onto M1.



---

*Source: 691439-2013-12-24.xml*