Set decipherable languages and generators

Nội dung text: Set decipherable languages and generators

1. Journal of Computer Science and Cybernetics, V.36, N.4 (2020), 381–392 DOI 10.15625/1813-9663/36/4/15317 SET DECIPHERABLE LANGUAGES AND GENERATORS TRAN VINH DUC School of Information and Communication Technology, Hanoi University of Science and Technology Abstract. We investigate the problem to characterize whether the infinite product of a given language L is generated by an ω-code. Up to now, this problem is open even if language L is a finite language. In this work, we consider a class of languages named ω-set decipherable languages which are very close to the ω-codes. We solve the problem in the restricted case where L is ω-set decipherable and L∗ is the greatest generator of Lω. Keywords. Codes; ω-codes; Dominoes; Formal languages; Generators; Infinite words. 1. INTRODUCTION The languages of infinite words (or ω-languages), see [15], are an extension of formal languages where the finite sequences (or finite words) are replaced by infinite sequences (or infinite words). The infinite sequences allow us to model the behavior of systems which are supposed to work indefinitely, for example Web servers and operating systems. The most important class of the ω-languages is the ω-rational languages. This class is exactly finite unions of ω-languages of the form XY ω, where X, Y are rational languages and the operation ω is the infinite product. In this paper, we study the ω-powers, i.e. the ω-languages of the form Lω where L is a language of finite words. The ω-power Lω and the language L are closely linked through the infinite product ω. Thus, two languages X and Y such that Xω = Y ω are, in some sense, equivalent. Naturally, we define the family [Lω] that consists of the languages X such that Xω = Lω. Such language X is called a generator of Lω. The generators give us a way to explore the ω-languages by using the languages of finite words. In the family [Lω], there are some generators that seem to be more interesting. The minimal generators or finite generators are interesting by their sizes. Among minimal gene- rators, the codes or the ω-codes (if exist) are valuable. These generators attract attention from the point of view of easy decoding. Intuitively, a code (respectively an ω-code) is a set of finite words such that any product (respectively any infinite product) of these words can be decoded in unique fashion. Any ω-code is a code. Codes play important roles in many domains such as data compression and informa- tion transmission. The origin of code notations is as follows. Let β be a bijection from an alphabet B into a code C which extends to a morphism from B∗ into C∗. The coding procedure associates a word b1b2 . . . bn which is the source text with an encoded message β(b1)β(b2) ··· β(bn) over the channel alphabet by the use of the coding morphism β. The Corresponding author. ductv@soict.hust.edu.vn c 2020 Vietnam Academy of Science & Technology
2. 382 TRAN VINH DUC concepts of code formalize whether the encoded message can be unambiguously decoded. In data compression, the codes (e.g. Huffman codes) are designed for minimizing encoded mes- sage length. In information transmission, the codes are designed for detecting and correcting errors. This paper is motivated by the open question (see [14, p. 229]): Deciding whether a rational ω-power Lω is equal to Cω with C an ω-code. The question is natural and classic; and it is open even if language L is a finite language. Apparently, the above question is similar to the one in free monoids: Deciding whether a rational submonoid M of free monoid is equal to C∗ with C a code. In fact, the structure of submonoids and ω-powers is very different. For any submonoid M of a free monoid, we know [2, p. 60] that M has the greatest generator (with respect to inclusion) which is M itself, and M has the smallest generator Root(M) = (M \ ε) \ (M \ ε)2. Then M is generated by a code if and only if Root(M) is a code. For any ω-power Lω, the situation is more complicated. We know in [13] that Lω never has the smallest generator, and Lω does not always have the greatest generator. In case where the greatest generator M exists, for example when Lω is generated by a finite language, it may happen that Root(M) is not an ω-code while Lω is generated by an ω-code. Our starting point is a result proved in [9] stating that if L is a code such that L∗ is the greatest generator of Lω, then there exists an ω-code C such that Cω = Lω if and only if L itself is an ω-code. We try to extend this result by defining a class of languages that is as simple as possible after the codes, and we prove the similar result for this class. Here we consider a superset of codes named set decipherable languages [6, 1]. Intuitively, a set decipherable language is a set of words such that any product of these words can be uniquely deciphered up to both commutativity of elements and the number of occurrences of elements. Based on this idea, we define ω-set decipherable languages where any product of words is replaced by any infinite product of words. This class is a superset of ω-codes, and it is very close to the ω-codes. Our result. In this work, we solve the question in the restricted case where L is an ω-set decipherable language and L∗ is the greatest generator of Lω. We prove that Lω = Cω for some ω-code C if and only if L is itself an ω-code (see Theorem 27). Our technique. Our approach is different from [9]. Instead of manipulating directly the language L, we look at the minimal relations satisfied by L. These relations capture the structure of the double L-factorizations of words or infinite words, and they are easy to compute by using a variation of domino graph [6]. Thus, the existence of ω-code generators can be shown by analyzing the system of minimal relations (see Proposition 23). In a broader view, see [17, 16], this approach makes some notations of linear algebra appear on the set of words or infinite words when linear combinations are replaced by relations. Related work. The generators of rational ω-languages was first studied by Latteux and Timmerman [10]. They gave an algorithm to decide whether a rational ω-power Lω is finitely generated, that is Lω = F ω for some finite language F . The structure of the family of generators has been considered in [13]. Generally, the family of generators has no greatest element but has a finite number of maximal generators, and every generator is included in a maximal generator. These maximal generators are rational monoids and can be computed. The existence of ω-code generators was first investigated by Litovsky [12]. He showed a
3. SET DECIPHERABLE LANGUAGES AND GENERATORS 383 method to decide whether a rational ω-power Lω is generated by a prefix code. Devolder [4] extended this result for the languages with bounded deciphering delay (i.e. languages allo- wing to perform the decoding of infinite words after some bounded delay, without waiting the whole message). Julia et al. [9] solved the problem for an interesting case: Lω has the greatest generator that is generated by a code. Notice that the condition of having the greatest generator is only a technical assumption; we can remove it by considering all maxi- mal generators instead of the greatest one. More recently, Tran and Litovsky [19] unraveled the problem when L is a one-relation language (i.e. language satisfied by only one basic relation). 2. PRELIMINARIES Let A be an alphabet and A∗ (resp. Aω) is the set of all finite (resp. infinite or ω) words. The empty word is denoted by ε and A+ denotes A∗ \{ε}. Let x ∈ A∗, we denote by |x| the length of x. The subsets of A∗ (resp. Aω) are called languages (resp. ω-languages). We denote by A∞ = A∗ ∪ Aω the set of finite or infinite words. The product of a finite ∗ ω word x = a0a1 ··· an from A with an infinite word y = b0b1 ··· of A is the infinite word xy = a0a1 ··· anb0b1 ··· . A word y ∈ A∗ is called a prefix of a word x ∈ A∞ if x = yv with v ∈ A∞. A word y is a proper prefix of a word x if y is prefix of x and x 6= y. The language Pref(x) is the set of ∞ all prefixes of x. Let X ⊆ A , we define Pref(X) = x∈X Pref(x). Let L ⊆ A∗ be a language. The language L∗ is the set of finite words built with words S in L, that is ∗ L = {x1x2 ··· xn | n ≥ 0 and x1, . . . , xn ∈ L}. In the same way, the ω-language Lω is the set of infinite words: ω L = {x0x1 · · · | for all i ≥ 0, xi ∈ L \{ε}}. Thus, Lω is the set of infinite words obtained by concatenating an infinite sequence of nonempty words of L. We denote by L+ = LL∗ = L∗L and by L∞ = L∗ ∪ L∞. An ω-language of the form Lω is said to be an ω-power. A language of finite words G ⊆ A∗ is called a generator of Lω if Gω = Lω. ∗ An L-factorization of a word x ∈ A is a finite sequence (x1, . . . , xn) of words of L such ω that x = x1 . . . xn. An L-factorization of an infinite word w ∈ A is an infinite sequence (x1, x2, ) of words of L such that w = x1x2 Definition 1. Let C ⊆ A∗ be a language. • C is a code if any word in A∗ has at most one C-factorization. • C is a ω-code if any infinite word in Aω has at most one C-factorization. Note that the code is called unique decipherable code in [6] and ω-code is called infinitary finite length code in [18]. Despite their name, ω-codes are finite word languages. It is effectively decidable whether a regular language is a code or an ω-code (see [3, 20]). Although the definition of codes is on finite words, the codes can be characterized by their way of acting on infinite words. We present a characterization of codes based on the factorizations of infinite periodic words.
4. 384 TRAN VINH DUC Proposition 2 (see [5]). Let C ⊆ A∗ be a language. Then C is a code if and only if for every u ∈ C+, uω has a single C-factorization. By this proposition, an ω-code is a code. The following example exhibits a code that is not an ω-code. Example 3. The code C = {a, ab, b2} is not an ω-code because the infinite word abω has two C-factorizations: (ab, bb, bb, . . . ) and (a, bb, bb, . . . ). A variation of codes named set decipherable codes was introduced by Guzm´an[6]. Definition 4. A language C ⊆ A∗ is a set decipherable (SD) if any two C-factorizations of a word of A∗ use the same set of elements. More precisely, C is a SD language if, whenever x1x2 ··· xn = y1y2 ··· ym with xi, yj ∈ C holds, then necessarily we have {x1, x2, ··· , xn} = {y1, y2, ··· , ym}. Thus, if C is SD, then every word in C∗ has unique factorization in words in C up to both commutativity of elements and the number of occurences of elements. A motivating example here, given in [6], is that two rival parties, willing to reveal to each other the presence or absence of certain items without revealing the exact count. In order to extend the set decipherability for infinite words, we define a new class of languages, called ω-set decipherable languages. Definition 5. A language C ⊆ A∗ is a ω-set decipherable (ω-SD) if any two C-factorizations of an infinite word of Aω use the same set of elements. By definition, a language C is ω-SD if for all x ∈ C, we have (C \{x})ω ∩ C∗xCω = ∅. (1) Note that if C is finite, then the equation (1) can be verified efficiently. Thus we can decide if a given finite language is ω-SD. ω ω Remark 6. As the equality x1 ··· xn = y1 ··· ym implies (x1 . . . xn) = (y1 . . . ym) , the ω- SD languages are SD. But the inversion is not true. The following example exhibits a SD language that is neither a code nor an ω-SD language. Example 7. Consider the SD language S = {s0, s1, s2, s3}, where s0 = ab, s1 = ba, s2 = 2 2 2 2 a baba and s3 = ba ba b. The SD language S is not a code because the following finite word has two S-factorizations s1s0s2s1s3 = ba · ab · aababaa · ba · baabaab = baabaab · ab · aababaa · ba · ab = s3s0s2s1s0. Moreover, the SD language S is not an ω-SD because the following infinite word has two S-factorizations that yield two distinct sets of elements ω ω (s3s0s2) = (baabaab · ab · aababaa) = ba · ab (aababaa · ba · baabaab)ω ω = s1s0(s2s1s3) .
5. SET DECIPHERABLE LANGUAGES AND GENERATORS 385 Table 1. Examples in brief Example ω-code Code ω-SD language SD language 3 No Yes No Yes 7 No No No Yes 8 No No Yes Yes ω-codes ω-SD languages Codes SD languages Figure 1. Proper containments of Codes, ω-codes, SD languages and ω-SD languages. The codes and ω-SD languages are incomparable The following example exhibits a ω-SD language that is not a code. Example 8. Let S = {x0, x1, x2, x3} where x0 = bba, x1 = bab, x2 = bbabb and x3 = abbbabab. This language is ω-SD (see Example 16). But S is not a code because the following finite word has two factorization on S: x0x2x1x3 = bba · bbabb · bab · abbbabab = bbabb · abbbabab · bba · bab = x2x3x0x1. We summarize the examples in Table 2 The relationship of containment between the codes, ω-code, SD languages and ω-SD languages is shown in Figure 2. We reiterate the problem which is the motivation for this work. Problem 9. Given a finite language L, find an algorithm to decide whether Lω = Cω for some ω-code C. Example 10. Let language L = {a2, a3, b}. L is not a code, then L is not an ω-code. However, the language W = {a2, a3b, b} is an ω-code generator of Lω. The following theorem is the starting point to this work. Theorem 11 (see [9]). Let C be a rational code such that C∗ is the greatest generator (with respect to inclusion). Then the ω-power Cω has an ω-code generator if and only if C is an ω-code.
6. 386 TRAN VINH DUC 3. RELATIONS AND DOMINO GRAPH Given a language L ⊆ A∗, we consider a bijection˜: Σ → L between an alphabet Σ and the language L. This mapping is extended to Σ∗ as a morphism˜: Σ∗ → L∗. This morphism is said to be a coding morphism for L. This mapping also is extended to ˜ : Σω → Lω by setting x^0x1 =x ˜0x˜1 Thus each L-factorization of a word in A∞ is represented by a word in Σ∞. By abuse of language, the subsets of Σ∞ are called languages of factorizations. For a language C ⊆ Σ∞, we denote C˜ = {x˜ | x ∈ C}. Let x and y be two words in Σ∞ such thatx ˜ =y ˜, we write x =∼ y that is called a relation in Σ∞. A relation x =∼ y is called nontrivial if x 6= y. It is obvious that if x =∼ y and x0 =∼ y0, then xx0 =∼ yy0. Naturally, we consider the minimal length relations. A nontrivial relation x =∼ y is called minimal if for all nonempty proper prefix p of x and for ∼ all nonempty proper prefix q of y, we have p =6 q. We denote by R(L) and Rmin(L) the set of nontrivial relations and minimal relations of L, respectively. Example 12. Consider the language L = {a, ab, bc, c}, the alphabet Σ = {0, 1, 2, 3} and the bijection 0 7→ a, 1 7→ ab, 2 7→ bc, 3 7→ c. This language has only one minimal relation 02 =∼ 13. The language L is not SD. In order to compute the minimal relations satisfied by a finite language, we look at a variation of domino graph that is suggested by Guzm´an(see [6]). These graphs have been used for deciding efficiently the multiset decipherability (see [7]) on finite words. We adapt these graphs to finite or infinite words. Let G = (V, E) be the directed graph with vertex set u ε V = {open, close} ∪ | u ∈ Pref(L) \{ε} ∪ | u ∈ Pref(L) \{ε} ε u       and with edge set E = E1 ∪ E2 ∪ E3 ∪ E4 where ε E = open, | u ∈ L , 1 u     u E = , close | u ∈ L , 2 ε     u uv ε ε E = , | v ∈ L ∪ , | v ∈ L , 3 ε ε u uv           u ε ε v E = , | uv ∈ L ∪ , | uv ∈ L . 4 ε v u ε           A finite path in G is successful if its starting vertex is open and its arrival vertex is close. An infinite path in G is successful if its starting vertex is open. The domino graph associated with L, denote by G(L), is the directed graph (V 0,E0) where V 0 consists of the vertices open, close and the vertices v ∈ V such that there exists a (finite or infinite) successful path that goes through v; and E0 consists of the edges e ∈ E such that there exists a successful (finite or infinite) path that goes through e.
7. SET DECIPHERABLE LANGUAGES AND GENERATORS 387 We denote by ˆ: L → Σ the bijection defined byu ˆ = x if u =x. ˜ The domino function u ε associated with L is the mapping d from E to , | u ∈ L defined on ε u      ε u • E by d open, = , 1 u ε      b u u • E by d , close = , 2 ε ε      b u uv ε ε ε v • E by d , = and d , = , 3 ε ε v u uv ε             b u ε uv ε v ε • E by d , = b and d , = . 4 ε v ε u ε uv             c The domino function is extended by morphism on the finitec or infinite paths by setting, for each finite path p consisting of edges (e1, e2, . . . , em), ∗ ∗ d(p) = d(e1)d(e2) . . . d(en) ∈ Σ × Σ and for each infinite path p consisting of edges (e1, e2, ), ω ω d(p) = d(e1)d(e2) · · · ∈ Σ × Σ . The pair d(p) is called domino associated with the path p in G. The first and second components of d(p) are respectively denoted by d1(p) and d2(p). A successful path p of G(L) is trying to find two factorizations of the same word in L∗ ∪Lω beginning with distinct words. The factorizations obtained so far are d1(p) and d2(p). Thus ∼ d1(p) = d2(p) is a nontrivial relation of L. The following proposition (see [6]) shows that these relations are minimal. Proposition 13. Let x, y ∈ Σ∞, x =∼ y is a minimal relation of L if and only if there is x y a finite or infinite successful path p in G(L) such as d(p) = y or d(p) = x . We denote by D(L) = {d(p) | p is a successful path of G(L)}.   Example 14. Let L = {a, ab, ba} and let Σ = {0, 1, 2} be the alphabet of relations of L. The domino graph G(L) is shown in the Figure 14. We have ∗ ω 0 ε 2 ε ε 2 0 ε 2 D(L) = ∪ ε 1 ε 1 0 ε ε 1 ε      ∗        ω     0 2 2 0 2 = ∪ . 1 10 1         Thus the set of minimal relations of L is exactly the system 02n =∼ 1n0 for all n > 0 ω ∼ ω (02 = 1 .
8. 388 TRAN VINH DUC ε 1 0 [ ] ε 2 ε 0 ε ε open [ ] b [ ] ba [ ] close a ε ε 2 ε [ ] Figure 2. The domino graph of language L = {a, ab, ba} 0 ε 2 ε 2 ε open [ ] ε [ ] bb [ ] ε 1 bba ε abb ε [ ] ε abbbab ε close abbbabab abbba ab 3 3 ε ε ε ε ε [ ] ε 1 0 [ ] [ ] [ ] Figure 3. The domino graph of language S = {bba, bab, bbabb, abbbabab} The following proposition states that the codes, ω-codes, SD codes, ω-SD codes can be characterized in terms of its domino graph G(L) and the function d1 and d2. Proposition 15. Let L be a finite language. (i) L is a code if and only if no finite successful path exists in G(L). (ii) L is an ω-code if and only if no finite or infinite successful path exists in G(L). (iii) L is SD if and only if all finite successful paths p in G(C) are such that d1(p) and d2(p) have the same set of letters. (iv) L is ω-SD if and only if all finite or infinite successful paths p in G(L) are such that d1(p) and d2(p) have the same set of letters. Example 16. Let S = {bba, bab, bbabb, abbbabab} and let Σ = {0, 1, 2, 3} be the alphabet of relations of S. The domino graph G(S) is shown in Figure 16. Thus, the language S has only one minimal relation 0213 =∼ 2301. The language S is ω-SD but non code. 4. ω-SET DECIPHERABLE LANGUAGES AND GENERATORS In this section, we assume that L is a language such that L∗ is the greatest generator (with respect to inclusion) of Lω and L is in one-to-one mapping with the alphabet Σ. Note that this assumption is satisfied by some interesting cases, for example the case where Lω is an ω-power of a finite language (see [11] and [13]).
9. SET DECIPHERABLE LANGUAGES AND GENERATORS 389 ω We denote by AmbΣ(L) the set of infinite words in Σ such that the images of these infinite words in Aω have at least two L-factorizations. That is, ω AmbΣ(L) = {x ∈ Σ | x˜ has at least two L-factorizations} = {x ∈ Σω | ∃y ∈ Σω, x =∼ y and x 6= y}. According to Proposition 2, the language L is a code if and only if the set AmbΣ(L) has no infinite periodic words. + ω ω Lemma 17. Let C ⊆ Σ such that C is a generator of L and let w ∈ Σ . If w∈ / AmbΣ(L), then w ∈ Cω. e Proof. Since C is a generator of Lω, it follows that for each w ∈ Σω there is an infinite word 0 ω ∼ 0 0 ω w ∈ C such that w = w . If w∈ / AmbΣ(L) then w = w . So w ∈ C .  We recalle that a language P ⊆ Σ+ is a prefix code if no word in P is a proper prefix of another word in P . Lemma 18. Let C ⊆ Σ+ such that the language C is a code generator of Lω. Then the language C is a prefix code over Σ. e Proof. Assume on the contrary that there exist two nonempty words u, v ∈ Σ+ such that {u, uv} ⊆ C. Since C is a generator of Lω, there exists w ∈ Cω such that (vu)ω =∼ w. Then u(vu)ω = (uv)ω =∼ uw. Asuv ˜ 6=u ˜, the periodic word (uv ˜ )ω has two factorizations on C: one starts byu ˜ ande the other byuv ˜ . According to Proposition 2, C is not a code.  e Definition 19. We say that two words u, v ∈ Σ+ are incompatible if there exist x, y ∈ Σ∞ e such that the relation ux =∼ vy is minimal. Remark 20. By the minimality of relation ux =∼ vy, two incompatible words u and v must have no common prefix. Let X ⊆ Σ∞. We denote by P(X) = Pref(X) \{ε}. Lemma 21. Let C ⊆ Σ+ such that C is an ω-code generator of Lω. Let u and v be two incompatible words. Then for all m ∈ Σ∗, the set mP({u, v}) ∩ C is the empty set or a singleton. e Proof. According to Lemma 18, the language C is a prefix code. For each m ∈ Σ∗, each set of mP(u) ∩ C and mP(v) ∩ C is either the empty set or a singleton. Therefore, it is sufficient to show that mP(u) = ∅ or mP(v) = ∅. Assume on the contrary that there exist p ∈ P(u) and q ∈ P(v) such that {mp, mq} ⊆ C. As two words u and v are incompatible, there exist x, y ∈ Σω such that px =∼ qy is a minimal relation. Then we have (mp)x =∼ (mq)y. There are two cases: • Ifmp ˜ 6=mq ˜ , then C is not an ω-code generator of Lω; ∼ ∼ • Ifmp ˜ =mq ˜ , that ise mp = mq, then p = q which contradicts the minimality of the relation px =∼ qy. In both cases, we obtain a contradiction.  This is a corollary of Lemma 21.
10. 390 TRAN VINH DUC Corollary 22. Let C ⊆ Σ+ such that C is an ω-code generator of Lω. Let u and v be two incompatible words. Then for all m ∈ Σ∗, there exists z ∈ {u, v} such that mP(z) ∩ C = ∅. e Proof. According to Lemma 21, we have mP(u) ∩ C = ∅ or mP(v) ∩ C = ∅.  Proposition 23. Let u and v be two incompatible words. If Amb ∩ {u, v}ω = ∅, then Lω has no ω-code generator. Proof. Assume that there exists C ⊆ Σ+ such that C is an ω-code generator of Lω. We build, by induction, an infinite sequence (zi)i≥0 of words such that for all i ≥ 0, e z ∈ {u, v} i (2) (P(z0 . . . zi) ∩ C = ∅. Indeed, according to Corollary 22, there exists z0 ∈ {u, v} such that P(z0) ∩ C = ∅. Assume that we have the sequence (z0, . . . , zn−1) which verifies the condition (2). According to Corollary 22, there exists zn ∈ {u, v} such that z0 . . . zn−1P(zn) ∩ C = ∅ and by induction hypothesis we have P(z0 . . . zn−1) ∩ C = ∅. Then z0, . . . , zn verifies the condition (2). Now consider the infinite word w = z0z1 . . . zn /∈ AmbΣ(L), according to Lemma 17, we have w ∈ Cω. However, by the construction, we have P(w) ∩ C = ∅. This is a contradiction.  The following examples point out how to apply Proposition 23 to prove that some ω- powers have no ω-code generator. Example 24. Let L = {a, ab, bc, c} and Σ = {0, 1, 2, 3}. The language L has only one ∼ ∗ ω minimal relation 02 = 13. Then AmbΣ(L) = Σ {02, 13}Σ . We have ω AmbΣ(L) ∩ {0, 1} = ∅. As two words 0, 1 are incompatibles, according to Proposition 23, Lω has no ω-code generator.
11. SET DECIPHERABLE LANGUAGES AND GENERATORS 391 Example 25. Let L = {a, ab, b2} be a suffix code and Σ = {0, 1, 2}. The language L has ω ∼ ω ∗ ω ω only one minimal relation 02 = 12 . Thus AmbΣ(L) = Σ {02 , 12 }. We have therefore ω ω AmbΣ(L) ∩ {0, 1} = ∅. According to Proposition 23, the ω-language L has no ω-code generator. Now we apply the above results for ω-SD codes. Before going to the main theorem, we need the following lemma. Lemma 26 (see [14, p. 207]). If two words satisfy a nontrivial relation on finite or infinite words, then they are powers of the same word. Theorem 27. Let L be an ω-SD language such that L∗ is the greatest generator (with respect to inclusion) of Lω. Then Lω has an ω-code generator if and only if L is an ω-code. Proof. If L is an ω-code, then L itself is an ω-code generator of Lω. Otherwise, there exists a minimal relation 0x =∼ 1y where 0 and 1 are two distinct letters of alphabet Σ. Then 0 and 1 are incompatible. Let us suppose that L is an ω-SD such that L∗ is the greatest generator of Lω and Lω has an ω-code generator. By Proposition 23, there exists an infinite word ω w ∈ AmbΣ(L) ∩ {0, 1} . That is, there exists a nontrivial relation w =∼ v. Since L is ω-SD and w ∈ {0, 1}ω, we also have v ∈ {0, 1}ω. According to Lemma 26, two words 0˜ and 1˜ are powers of the same word. ω ∼ ω Thus we have 0 = 1 , which contradicts the assumption that L is ω-SD.  5. CONCLUSIONS In this paper, we have faced the open problem to characterize whether the infinite product of a given language L is generated by an ω-code. We define a new class of languages named ω-set decipherable languages, and we solve the problem in the restricted case where L is ω-set decipherable and L∗ is the greatest generator of Lω. Our approach here is to study the minimal relations satisfied by L. These relations capture the structure of the double factorizations of words or infinite words, and they are easy to compute by using the domino graphs. In the future, it would be interesting to consider the problem in the case where L is set decipherable. ACKNOWLEDGMENT This research is funded by the Hanoi University of Science and Technology (HUST) under project number T2018-PC-207. REFERENCES [1] P. C. Bell, D. Reidenbach, and J. O. Shallit, “Unique decipherability in formal languages,” Theoretical Computer Science, vol. 804, pp. 149 – 160, 2020. [2] J. Berstel, D. Perrin, and C. Reutenauer, Codes and Automata, ser. Encyclopedia of Mathe- matics and its Applications. Cambridge University Press, 2009, vol. 129.
12. 392 TRAN VINH DUC [3] T. Dang Quyet, H. Nguyen Dinh, and H. Phan Trung, “Algorithms based on finite automata for testing of ω-codes,” in Future Information Technology, Application, and Service. Springer Netherlands, 2012, pp. 271–279. [4] J. Devolder, “Generators with bounded deciphering delay for rational ω-languages,” Journal of Automata, Languages and Combinatorics, vol. 4, no. 3, pp. 183–204, 1999. [5] J. Devolder, M. Latteux, I. Litovsky, and L. Staiger, “Codes and infinite words,” Acta Cyber- netica, vol. 11, no. 4, pp. 241–256, 1994. [6] F. Guzm´an,“Decidability of codes,” Journal of Pure and Applied Algebra, pp. 13–35, 1999. [7] T. Head and A. Weber, “Deciding multiset decipherability,” in IEEE Trans. Inf. Theory, vol. 41, no. 1, pp. 291–297, 1995. [8] S. Julia, “On ω-generators and codes,” in 23d ICALP (Int. Coll. on Automata, Languages and Programming), ser. Lecture Notes in Computer Sciences, vol. 1099. Berlin: Springer, 1996, pp. 393–402. [9] S. Julia, I. Litovsky, and B. Patrou, “On codes, ω-codes and ω-generators,” Information Pro- cessing Letters, vol. 60, no. 1, pp. 1–5, oct 1996. [10] M. Latteux and E. Timmerman, “Finitely generated ω-langages,” Information Processing Letters, vol. 23, pp. 171–175, 1986. [11] I. Litovsky, “G´en´erateursdes langages rationnels de mots infinis,” Ph.D. dissertation, Universit´e de Lille, 1988. [12] ——, “Prefix-free languages as ω-generators,” Information Processing Letters, vol. 37, pp. 61–65, 1991. [13] I. Litovsky and E. Timmerman, “On generators of rational ω-power languages,” Theoretical Computer Science, vol. 53, pp. 187–200, 1987. [14] M. Lothaire, Algebraic Combinatorics on Words, ser. Encyclopedia of Mathematics and its Applications. Cambridge: Cambridge University Press, 2002, vol. 90. [15] D. Perrin and J. E. Pin, Infinite Words. Academic Press, 2002. [16] A. Saarela, “Independent systems of word equations: From Ehrenfeucht to eighteen,” in Com- binatorics on Words, Springer International Publishing, 2019, pp. 60–67. [17] ——, “Word equations with kth powers of variables,” Journal of Combinatorial Theory, Series A, vol. 165, pp. 15 – 31, 2019. [18] L. Staiger, “On infinitary finite length codes,” Theoretical Informatics and Applications, vol. 20, no. 4, pp. 483–494, 1986. [19] V. D. Tran and I. Litovsky, “One-relation languages and ω-code generators,” in Proc. of the 13th Mons Theoretical Computer Science Days, 2010. [20] R. Zaccagnino, R. Zizza, and C. Zottoli, “Testing DNA code words properties of regular langua- ges,” Theoretical Computer Science, vol. 608, pp. 84 – 97, 2015. Received on July 28, 2020 Revised on September 10, 2020