B-Codes and their relationship with alternative codes

Journal of Computer Science and Cybernetics, V.33, N.3 (2017), 263–271 DOI 10.15625/1813-9663/33/3/10919 B-CODES AND THEIR RELATIONSHIP WITH ALTERNATIVE CODES NGO THI HIEN Ha Noi University of Science and Technology; hien.ngothi@hust.edu.vn
Abstract. Codes of bounded words (b-codes, ♦-codes), an extension of the notion of ordinary codes, have been first introduced and considered by P. T. Huy et al. in 2009. In this note, we consider some new subclasses of b-codes. In particular, characteristic properties of such codes are established. Also, relationships between b-codes, alternative codes and their subclasses are considered. Keywords. Alternative code, b-code, norm b-code, two-side b-code, left b-code, strict b-code. Mathematics Subject Classification (2010): 94A45, 68Q45. 1. INTRODUCTION The theory of length-variable codes has been initiated by M. P. Schu¨tzenberger in the 1950s and then developed by many others. A direction in this theory concentrates studying codes defined by control parameters or related with multi-value [1, 2, 4, 10, 13, 14, 16]. A code is a language such that every text encoded by words of the language can be decoded in a unique way. Codes are useful in many areas of application such as information processing, data compression, cryptography, information transmission and so on. For background of the theory of codes we refer to [3, 11, 15]. As mentioned above, the definition of codes is essentially based on unambiguity of the (catenation) product of words. Different modifications of such a product may lead to different extensions of the notion of codes. Such an approach has been proposed by P. T. Huy et al. which deals with the so-called even alternative codes and codes of bounded words (or ♦-codes, for short) [5, 6, 7, 10, 17, 18, 19, 20]. They demonstrated the importance characterizations as well as algorithms to test for these classes. For simplicity, ♦-codes, weak left ♦-codes, weak right ♦-codes and strict ♦-codes in [17, 18] are called simply respectively b-codes, left b-codes, right b-codes and strict b-codes instead. Recently, in [8, 9, 19, 20], the authors proposed some classes of codes which concern alternative codes and b-codes. Several interesting characteristic properties and algorithms to test for such codes were established. In this note, some new subclasses of b-codes are introduced and considered. In Section 2 necessary definitions are recalled, and several facts useful in the sequel are shown. Section 3 introduces four new classes of codes which are subclasses of b-codes. Also some characteristic properties and relationships of these classes are considered. The section ends with relations on b-codes, alternative codes and their subclasses. The final section discusses the problem investigations and presents a summary of the results obtained. Our work is motivated by the idea to define b-codes by equivalent factorizations on a b-language, and the way to solve the problem for b-codes as well as their well-known subclasses [6, 17, 18, 19]. c© 2017 Viet Nam Academy of Science & Technology 264 NGO THI HIEN 2. PRELIMINARIES Let A throughout be a finite alphabet, i.e. a non-empty finite set of symbols, which are called letters. Let A∗ be the set of all finite words over A. The empty word is denoted by ε and A+ stands for A∗ \ {ε}. The number of all the occurrences of letters in a word u is the length of u, denoted by |u|. Any subset of A∗ is a language over A. A language X is a code if for any n,m ≥ 1 and any x1, . . . , xn, y1, . . . , ym ∈ X, the condition x1x2 . . . xn = y1y2 . . . ym implies n = m and xi = yi for i = 1, . . . , n. Since ε.ε = ε, a code never contains the empty word ε. The reversal of a word w = a1a2 . . . an, where a1, a2, . . . , an are letters, is the word w˜ = anan−1 . . . a1. Similarly, for X ⊆ A∗, we denote X˜ = {x˜ | x ∈ X}. Let X and Y be non-empty subsets of A+. We say that u1u2 . . . un, n ≥ 2, is an alternative factorization on (X,Y ) if ui ∈ X implies ui+1 ∈ Y and ui ∈ Y implies ui+1 ∈ X for all i = 1, 2, . . . , n−1. Two alternative factorizations u1u2 . . . un and v1v2 . . . vm on (X,Y ) are said to be left similar (right similar) if they begin (resp. end) with words in the same set X or Y , namely u1, v1 ∈ X or u1, v1 ∈ Y (resp. un, vm ∈ X or un, vm ∈ Y ); u1u2 . . . un and v1v2 . . . vm are called dissimilar if they both begin and end with words in different sets, namely both u1 ∈ X, v1 ∈ Y or u1 ∈ Y, v1 ∈ X and un ∈ X, vm ∈ Y or un ∈ Y, vm ∈ X. Two alternative factorizations on (X,Y ) are called similar if they are both left similar and right similar. A pair (X,Y ) is said to be norm form if no word in A+ admits two different dissimilar alternative factorizations on (X,Y ). Definition 1. Let X and Y be non-empty subsets of A+. (i) (X,Y ) is called an alternative code (a left alternative code, a right alternative code) over A if no word in A+ admits two different similar (resp. left similar, right similar) alternative factorizations on (X,Y ); (ii) (X,Y ) is called a two-sided alternative code over A if it is both a left alternative code and a right alternative code; (iii) (X,Y ) is called a norm alternative code (left norm alternative code, right norm alter- native code) over A if it is an alternative code (resp. a left alternative code, a right alternative code) which has norm form; (iv) (X,Y ) is a strict alternative code over A if every word in A+ admits at most one alternative factorization on (X,Y ). The classes of alternative codes, left alternative codes, right alternative codes, two-side alternative codes, left norm alternative codes, right norm alternative codes, norm alternative codes and strict alternative codes are denoted respectively by CA, ClA, CrA, CtA, ClnA, CrnA, CnA and CsA. B-CODES AND THEIR RELATIONSHIP WITH ALTERNATIVE CODES 265 Next, let B = {0, 1}, we define the sets of bounded words (b-words) on A as follows: A♦ = {(l, a, r) | a ∈ A ∪ {ε}, l, r ∈ B}, ε♦ = {(l, ε, r) | l, r ∈ B}; A∗♦ = {(l, w, r) | w ∈ A∗, l, r ∈ B} ∪ {θ, e}, A+♦ = A∗♦ \ {θ, e}; A∗< = {(0, w, 1) | w ∈ A∗} ∪ {θ, e}, A+< = A∗< \ {θ, e}; A∗> = {(1, w, 0) | w ∈ A∗} ∪ {θ, e}, A+> = A∗> \ {θ, e}; A∗∧ = {(0, w, 0) | w ∈ A∗} ∪ {θ, e}, A+∧ = A∗∧ \ {θ, e}; A∗∨ = {(1, w, 1) | w ∈ A∗} ∪ {θ, e}, A+∨ = A∗∨ \ {θ, e}. Each element (l, w, r), w ∈ A∗ is called a b-word (or a bounded word with borders l, r) extended from w. And e, θ are two new elements as the unit, the zero of the monoid A∗♦ of all b-words respectively, where A∗♦ is a monoid (it is easily seen this) by a product defined as follows: z1z2 = { (l1, w1w2, r2), if r1 = l2; θ, otherwise; z1θ = θz1 = θ; z1e = ez1 = z1. where z1, z2 ∈ A∗♦, z1 = (l1, w1, r1) and z2 = (l2, w2, r2). The reversal of a b-word z = (l, a1a2 . . . an, r), where a1, a2, . . . , an are letters, l, r ∈ B, is the word z˜ = (r, anan−1 . . . a1, l). This notation is extended as usual to set by, Z˜ = {z˜ | z ∈ Z}. A subset of A∗♦ is called an extended language (b-language) on A. For each z = (l, w, r) ∈ A∗♦, we denote by pL(z) = l the left border of z and pR(z) = r the right border of z. Whenever none of mistakes are made, we also use notation |z| as the length of z, |z| = { 0, if z ∈ ε♦; |w|, otherwise. By convention, |θ| = +∞ and |e| = 0. We define a projection function Proj : A∗♦ → A∗ ∪ {0}, where 0 /∈ A∗ as the new zero of the monoid A∗ ∪ {0}, by Proj(e) = ε,Proj(θ) = 0 and Proj(l, w, r) = w. Two b-words s and t are said to be strict equivalent (left equivalent, right equivalent, equivalent), denoted by s ≈S t (resp. s ≈L t, s ≈R t, s ≈ t), if Proj(s) = Proj(t) (resp. Proj(s) = Proj(t) and pL(s) = pL(t), Proj(s) = Proj(t) and pR(s) = pR(t), s ≈L t and s ≈R t). Two factorizations s = s1s2 . . . sn and t = t1t2 . . . tm on Z are called strict equivalent (left equivalent, right equivalent, equivalent) if s ≈S t (resp. s ≈L t, s ≈R t, s ≈R t), where si, tj ∈ Z, i = 1, . . . , n, j = 1, . . . ,m. Definition 2. A b-language Z is called a b-codes over A if any word in A+♦ has at most one factorization in words in Z, and Z is a strict b-codes (left b-codes, right b-codes) over A if no word in A+♦ admits two different strict (resp. left, right) equivalent factorizations on Z. 266 NGO THI HIEN The classes of b-codes, left b-codes, right b-codes and strict b-codes are denoted respec- tively by CB, ClB, CrB and CsB. Over any alphabet consisting of at least two letters, the following holds true CsB ⊂ ClB ∩ CrB, ClB ∪ CrB ⊂ CB. For more details of alternative codes, b-codes and their subclasses we refer to [5, 6, 7, 8, 9, 10, 17, 18, 19, 20]. Now we formulate, in the form of lemmas, several facts which will be useful in the sequel. Lemma 1 ([12]; see also [3], page 49). Let X = {x1, x2}. Then, X is not a code if and only if x1 and x2 are powers of the same word, x1 = y p, x2 = y q for some y ∈ A+, p, q ≥ 0. The following result which resumes relative positions of alternative codes and their sub- classes. Lemma 2 ([7]). Over any alphabet consisting of at least two letters, the followings hold true (i) CsA ⊂ ClnA, CsA ⊂ CrnA, CsA ⊂ CtA, CsA = CnA ∩ CtA = ClnA ∩ CrA = CrnA ∩ ClA = ClA ∩ CnA ∩ CrA = ClnA ∩ CtA = CtA ∩ CrnA = CrnA ∩ ClnA = ClnA ∩ CrnA ∩ CtA; (ii) ClnA ⊂ ClA, ClnA ⊂ CnA, CrnA ⊂ CrA, CrnA ⊂ CnA, CtA ⊂ ClA, CtA ⊂ CrA, ClnA = ClA ∩ CnA, CrnA = CrA ∩ CnA, CtA = ClA ∩ CrA; (iii) ClA ⊂ CA, CnA ⊂ CA, CrA ⊂ CA. The following result claims relationships between b-codes and alternative codes. Lemma 3 ([17]). Let X,Y be non-empty subsets of A+, and Z = X where X< ⊆ A+< and Y> ⊆ A+>. (i) Z is a b-code if and only if X = Y and X is a code; (ii) Z is a b-code (left b-code, right b-code, strict b-code) if and only if (X,Y ) is an alter- native code (resp. a left alternative code, a right alternative code, a strict alternative code). 3. RESULTS We introduce in this section four new subclasses of b-codes and the b-codes with two elements. Several characterizations for b-codes and their subclasses are established. Firstly, we introduce four new subclasses of b-codes. Let us begin with a new class of codes which is a subclass of left b-codes and right b-codes. Definition 3. A b-language Z is called a two-side b-code over A if it is both a left b-code and a right b-code. Let us take an example. B-CODES AND THEIR RELATIONSHIP WITH ALTERNATIVE CODES 267 Example 1. Consider the set Z = {(0, aab, 1), (0, baa, 1), (1, aa, 0)} over A = {a, b}. It is easy to check that Z is both a left b-code and a right b-code, and hence it is a two-side b-code. However, Z is not a strict b-code because the word (0, aabaa, 1) has two distinct strict equivalent factorizations, (0, aabaa, 1) ≈S (0, aab, 1)(1, aa, 0) ≈S (1, aa, 0)(0, baa, 1). As an immediate consequence of Definition 3 and Lemma 3(ii), we obtain the following relationship between two-side b-codes and two-side alternative codes. Theorem 1. Let X,Y be non-empty subsets of A+, and Z = X where X< ⊆ A+< and Y> ⊆ A+>. Then, Z is a two-side b-code if and only if (X,Y ) is a two-side alternative code. Let Z be a non-empty subset ofA+♦. Two b-words s and t are said to be opposite equivalent, denoted by s ≈O t, if Proj(s) = Proj(t), pL(s) 6= pL(t) and pR(s) 6= pR(t). Two factoriza- tions s = s1s2 . . . sn and t = t1t2 . . . tm on Z are called opposite equivalent if s ≈O t, where si, tj ∈ Z, i = 1, . . . , n, j = 1, . . .m. A b-language Z is said to be norm form if no word in A+♦ which admits two different opposite equivalent factorizations on Z. Definition 4. A b-language Z is called a norm b-code (left norm b-code, right norm b-code) over A if it is a b-code (resp. left b-code, right b-code) which has norm form. The classes of two-side b-codes, left norm b-codes, right norm b-codes and norm b-codes are denoted respectively by CtB, ClnB, CrnB and CnB. Example 2. Consider the sets Z1 = {(1, a, 0), (1, aba, 0), (0, bna, 1) | n ≥ 1} and Z2 = {(0, a, 1), (1, b, 0), (1, ab, 0), (0, ba, 1)} over A = {a, b}. Then, it is not difficult to check that no word in A+♦ admits two different equivalent factorizations and two different opposite equivalent factorizations on Z1. Thus, Z1 is a norm b-code. However, Z1 is not a left norm b-code because the word (0, baaba, 0) has two different left equivalent factorizations on Z1, (0, baaba, 0) ≈L (0, ba, 1)(1, a, 0)(0, ba, 1) ≈L (0, ba, 1)(1, aba, 0). Next, it is easy to verify that no word in A+ admits two different left equivalent and two different opposite equivalent factorizations on Z2. Hence, Z2 is a left norm b-code. However, Z2 is not a right norm b-code because the word (0, baab, 0) has two different right equivalent factorizations on Z2, (0, baab, 0) ≈R (0, ba, 1)(1, ab, 0) ≈R (1, b, 0)(0, a, 1)(1, ab, 0). In an entirely symmetric manner, we also obtain Z˜1 is a norm b-code but it is not a right norm b-code, and Z˜2 is a right norm b-code not being a left norm b-code. Remark 1. For two different factorizations on Z, there are only separately possible cases as the following: [00, 00] (1) [11, 11] (2) [01, 01] (3) [10, 10] (4) [00, 01] (5) [11, 10] (6) [00, 10] (7) [01, 11] (8) [01, 10] (9) [00, 11] (10) where [01, 10] denotes that the first factorization has the form (0, w, 1), and the second factorization has the form (1, w, 0). By Definitions 2-4, the following holds true: 268 NGO THI HIEN The class of codes (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) CB − − − − + + + + + + ClB − − − − − − + + + + CrB − − − − + + − − + + CtB − − − − − − − − + + CnB − − − − + + + + − − ClnB − − − − − − + + − − CrnB − − − − + + − − − − CsB − − − − − − − − − − where + and − denote that these classes accept and reject factorizations which have forms like (1), (2), . . . , (10) respectively. As an immediate consequence of Definitions 2-4 and Remark 1, we can now formulate the following result which resumes relative positions of the classes of codes under consideration. Theorem 2. Over any alphabet consisting of at least two letters, the followings hold true (i) CsB ⊂ ClnB, CsB ⊂ CrnB, CsB ⊂ CtB, CsB = CnB ∩ CtB = ClnB ∩ CrB = CrnB ∩ ClB = ClB ∩ CnB ∩ CrB = ClnB ∩ CtB = CtB ∩ CrnB = CrnB ∩ ClnB = ClnB ∩ CrnB ∩ CtB; (ii) ClnB ⊂ ClB, ClnB ⊂ CnB, CrnB ⊂ CrB, CrnB ⊂ CnB, CtB ⊂ ClB, CtB ⊂ CrB, ClnB = ClB ∩ CnB, CrnB = CrB ∩ CnB, CtB = ClB ∩ CrB; (iii) ClB ⊂ CB, CnB ⊂ CB, CrB ⊂ CB. Remark 2. By Theorem 2, CsB = CnB ∩CtB. However, CnB and CtB are not comparable by inclusion. Indeed, the two-side b-code Z in Example 1 is not a norm b-code because the word (0, aabaa, 0) has two different opposite equivalent factorizations on Z, (0, aab, 1)(1, aa, 0) ≈O (1, aa, 0)(0, baa, 1). On the other hand, the norm b-code Z1 in Example 2 is easily verified to be not a two-side b-code. By virtue of Lemma 2, Theorem 2 and Remark 2, the relative positions of the classes of codes under consideration can be illustrated in the Figure 1, where the arrow → stands for a strict inclusion, and ↔ stands for a one-to-one correspondence (we only consider b- codes and their subclasses in A+). It is worthy to note that if we restrict ourselves to considering only one-letter alphabets then we have CsA = ClnA = CrnA = CnA = ∅, whereas the remaining classes represented in the Figure 1 coincide. Theorem 3. Let X,Y be non-empty subsets of A+, and Z = X where X< ⊆ A+< and Y> ⊆ A+>. Then, Z is a norm (left norm, right norm) b-code if and only if (X,Y ) is a norm (resp. left norm, right norm) alternative code. Proof. We treat only the case of norm b-codes. For the other cases the arguments are similar. Let Z be a norm b-code. If (X,Y ) is not a norm alternative code, then there exists w ∈ A+ such that w = u1u2 . . . un = v1v2 . . . vm, where both u1 ∈ X, v1 ∈ Y or u1 ∈ Y, v1 ∈ X and un ∈ X, vm ∈ Y or un ∈ Y, vm ∈ X. We consider separately two possible cases. B-CODES AND THEIR RELATIONSHIP WITH ALTERNATIVE CODES 269 Figure 1. Relations on b-codes, alternative codes and their subclasses Case 1: u1, vm ∈ X, v1, un ∈ Y or u1, vm ∈ Y, v1, un ∈ X. Then, we have (0, u, 0) ≈O (1, v, 1) or (1, u, 1) ≈O (0, v, 0), with u = u1u2 . . . un, v = v1v2 . . . vm. Case 2: u1, un ∈ X, v1, vm ∈ Y or u1, un ∈ Y, v1, vm ∈ X. Then, we have (0, u, 1) ≈O (1, v, 0) or (1, u, 0) ≈O (0, v, 1), with u = u1u2 . . . un, v = v1v2 . . . vm. Thus, in all the cases we have proved that whenever the word (l, w, r), with l, r ∈ B, admits two different opposite equivalent factorizations on Z, a contradiction. So, (X,Y ) is a norm alternative code. Conversely, suppose the contrary that Z is not a norm b-code. Then, if Z is not a b-code then, by Lemma 3(ii), (X,Y ) is not a alternative code, which contradicts the hypothesis that (X,Y ) is a norm alternative code. Otherwise, there exists a word z in A+♦ admits two different opposite equivalent factorizations on Z, s1s2 . . . sn ≈O t1t2 . . . tm where si, tj ∈ Z, 1 ≤ i ≤ n, 1 ≤ j ≤ m, and s1s2 . . . sn and t1t2 . . . tm are two alternative factorizations on (X). We consider separately two possible cases. Case 1: pL(s1 . . . sn) = pR(s1 . . . sn) = 0 or pL(s1 . . . sn) = pR(s1 . . . sn) = 1. Then, by defi- nition of ≈O, pL(t1 . . . tm) = pR(t1 . . . tm) = 1 or pL(t1 . . . tm) = pR(t1 . . . tm) = 0. Therefore, s1, tm ∈ X or s1, tm ∈ Y>, t1, sn ∈ X<. Hence, Proj(z) = u1u2 . . . un = v1v2 . . . vm, where ui = Proj(si), vj = Proj(tj), 1 ≤ i ≤ n, 1 ≤ j ≤ m, and u1, vm ∈ X, v1, un ∈ Y or u1, vm ∈ Y, v1, un ∈ X. Case 2: pL(s1 . . . sn) = 0, pR(s1 . . . sn) = 1 or pL(s1 . . . sn) = 1, pR(s1 . . . sn) = 0. Then, pL(t1 . . . tm) = 1, pR(t1 . . . tm) = 0 or pL(t1 . . . tm) = 0, pR(t1 . . . tm) = 1. Therefore, s1, sn ∈ X or s1, sn ∈ Y>, t1, tm ∈ X<. Hence, Proj(z) = u1u2 . . . un = v1v2 . . . vm, where ui = Proj(si), vj = Proj(tj), 1 ≤ i ≤ n, 1 ≤ j ≤ m, and u1, un ∈ X, v1, vm ∈ Y or u1, un ∈ Y, v1, vm ∈ X. Thus, in all the cases we have proved that whenever the word Proj(z) admits two different dissimilar alternative factorizations on (X,Y ), a contradiction. So, Z is a norm b-code.  In the rest of this section, we describe the b-codes with two elements. The case of sets with three words is much more complicated. 270 NGO THI HIEN Theorem 4. Let Z = {z1, z2} ⊆ A+♦. Then, Z is not a b-code if and only if z1 and z2 have the form (1) or (2) in Remark 1, and they are powers of the same b-word, z1 = t p, z2 = t q for some t ∈ A+♦, p, q ≥ 0. Proof. Suppose Z is not a b-code but the assertion is not true. Then, we consider separately two possible cases. Case 1: z1 and z2 have not the form (1) and (2) in Remark 1. Then, z1 and z2 belong to one of the forms (3), (4), . . . , (10). It is not difficult to verify that no word in A+♦ admits two different equivalent factorizations on Z. Thus, Z is a b-code, a contradiction. Case 2: z1 and z2 have the form (1) or (2) in Remark 1 but they are not powers of the same b-word. Then, from Lemma 1 implies Proj(Z) is a code. Therefore, because Z ⊆ A+∧ or Z ⊆ A+∨ , it follows that Z is a b-code, a contradiction. Conversely, since z1 and z2 are powers of the same b-word, by Lemma 1, Proj(Z) is not a code. Therefore, because Z ⊆ A+∧ or Z ⊆ A+∨ , by Lemma 3(i), Z is not a b-code.  4. CONCLUSIONS The purpose of this note was to deal with the development of the classes of b-codes and alternative codes. Four new classes of codes, which are subclasses of b-codes, were introduced and considered. Several characteristics and relationships of these classes were proposed (Theorems 3-4). One of them provided us with a tool to describe the b-codes with two elements. In future works, we hope we can find algorithms to test for subclasses of b-codes and many interesting problems for b-codes as well as their subclasses. ACKNOWLEDGMENT The author would like to thank the colleagues in Seminar Mathematical Foundation of Computer Science at Institute of Mathematics, Vietnam Academy of Science and Technology for attention to the work. Especially, the author expresses her sincere thanks to Prof. Do Long Van and Dr. Kieu Van Hung for their useful discussions. REFERENCES [1] M. K. Ahmad and X. Augros, “Some results on codes for generalized factorizations,” Journal of Automaton, Languages and Combinatorics, vol. 6, no. 3, pp. 239–251, 2001. [2] M. Anselmo, “Automates et codes zigzag,” RAIRO Theoretical Informatics and Applications, vol. 25, no. 1, pp. 49–66, 1991. [3] J. Berstel and D. Perrin, Theory of Codes. Academic Press, New York, 1985. [4] C. Caˆmpeanu, K. Salomaa, and S. Va´gvo¨lgyi, “Shuffle Quotient and Decompositions,” Lecture Notes in Computer Science, vol. 2295, pp. 186–196, 2002. [5] N. D. Han and P. T. Huy, “On unambiguity of languages related to codes,” in Future Information Technology, Application, and Service, J. P. James, C. M. L. Victor, L. W. Cho, and S. Taeshik, Ed. Springer Netherlands, pp. 32–38, 2012. B-CODES AND THEIR RELATIONSHIP WITH ALTERNATIVE CODES 271 [6] N. D. Han, H. N. Vinh, D. Q. Thang, and P. T. Huy, “Quadratic algorithms for testing of codes and ♦-codes,” Fundamenta Informaticae, vol. 130, no. 2, pp. 163-177, 2014. [7] N. T. Hien, “Characterizations for several classes of alternative codes,” Journal of Computer Science and Cybernetics, vol. 32, pp. 273–283, 2016. [8] N. T. Hien, “On strong alt-induced codes,” Applied Mathematical Sciences, vol. 12, no. 7, pp. 327 – 336, 2018, https://doi.org/10.12988/ams.2018.8113. [9] N. T. Hien and D. L. Van, “Codes induced by alternative codes,” Acta Mathematica Vietnam- mica, pp. 1–15, 2018, https://doi.org/10.1007/s40306-018-0247-2. [10] P. T. Huy and V. T. Nam, “Alternative codes and pre-context codes,” in Proceedings of the 7th National Conference: Selected problems about IT and Telecommunication, 2004, pp. 188–197 (in Vietnamese). [11] H. Ju¨rgensen and S. Konstantinidis, “Codes,” in Handbook of Formal Languages, G. Rozenberg and A. Salomaa, Ed. Springer, Berlin, pp. 511–607, 1997. [12] A. Lentin, “Equations dans les Mono¨ıdes Libres,” Paris: Gauthier-Villars, 1972. [13] M. Madonia, S. Salemi, and T. Sportelli, “On z-submonoids and z-codes,” Theoretical Informatics and Applications, vol. 25, pp. 305–322, 1991. [14] M. Madonia, S. Salemi, and T. Sportelli, “Covering submonoids and covering codes,” Journal of Automaton, Languages and Combinatorics, vol. 4, no. 4, pp 333–350, 1999. [15] H. J. Shyr, Free Monoids and Languages. Hon Min Book Company, Taichung, 1991. [16] D. L. Van, B. L. Saec, and I. Litovsky, “On coding morphisms for zigzag codes,” Theoretical Informatics and Applications, vol. 26, no. 6, pp. 565–580, 1992. [17] H. N. Vinh and P. T. Huy, “Codes of bounded words,” in Proceedings of the 3rd International Conference on Computer and Electrical Engineering, vol. 2, pp. 89–95, 2010. [18] H. N. Vinh, P. T. Huy, and D. L. Van, “Regular ♦-languages and codes,” in Proceedings of the 4th Fundamental and Applied IT Research, 2009, pp. 13–22 (in Vietnamese). [19] H. N. Vinh, P. T. Huy, and D. L. Van, “Extension of codes and algorithms for alternative codes and codes of bounded words,” Journal of Computer Science and Cybernetics, vol. 26, no. 4, pp. 301–311, 2010 (in Vietnamese). [20] H. N. Vinh, V. T. Nam, and P. T. Huy, “Codes based on unambiguous products,” Lecture Notes in Computer Science, vol. 6423, pp. 252–262, 2010. Received on November 28, 2017 Revised on January 29, 2018