Copyright©2019 P-ISSN: 2087-1244 E-ISSN: 2476-907X 23 ComTech: Computer, Mathematics and Engineering Applications, 10(1), June 2019, 23-27 DOI: 10.21512/comtech.v10i1.4716 Maximality on Construction of Ternary Cross Bifix Free Code Mohammad Affaf Department Pendidikan Matematika, STKIP PGRI Bangkalan Jln. Soekarno Hatta No.52, Jawa Timur 69116, Indonesia mohaffaf@stkippgri-bkl.ac.id Received: 28th April 2018/ Revised: 30th January 2019/ Accepted: 14th February 2019 How to Cite: Affaf, M. (2019). Maximality on Construction of Ternary Cross Bifix Free Code. ComTech: Computer, Mathematics and Engineering Applications, 10(1), 23-27. https://doi.org/10.21512/comtech.v10i1.4716 Abstract - The purpose of this research was to show that ternary cross bifix free code CBFS3(2m+1) and CBFS3(2m+2) achieved the maximum for every natural number m. This research was a literature review. A cross bifix free codes was constructed by using Dyck path method which achieved the maximality, that was non-expandable on binary set sequences for appropriate length. This result is obtained by partitioning members of CBFS3(2m+1) and CBFS3(2m+2) and comparing them with the maximality of CBFS2(2m+1) and CBFS2(2m+2). For small length 3, the result also shows that the code CBFS3(3) is optimal. Keywords: maximality, construction, ternary cross bifix free code I. INTRODUCTION Synchronization problem between transmitter and receiver on the data frame in the system of communication is called frame synchronization. Frame synchronization is one of the main topics in digital communication systems. In this system, to guarantee the synchronization between a transmitter and receiver, it can be done by periodically inserting a fixed sequence into the transmitted data. To find out what the transmitted data is, the receiver should find the fixed sequence. The technique is introduced by Massey (1972) and claimed that the search process is found by Nielsen (1973). Frame synchronization method is not only used in digital communication systems but also in gene expression as shown by Weindl and Hagenauer (2007). In fixed sequences, the gene uses a fixed sequence to sign the fundamental expression first (Levy & Yaakobi, 2017). This situation gives the probability that the frame synchronization method can be used on simulation genome. Frame synchronization method can be done by transmitting data coming from code {x1, x2 x3,...,xk} and having a special property. To recognize the beginning of the frame, it should guarantee that all suffixes of xi do not occur as the prefix of xj for all xi, and xj belongs to {x1, x2 x3,...,xk}. This method is firstly introduced by Van Wijngaarden and Willink (2000). This kind of code is called as cross bifix free code/set. At the beginning of the 21st century, the research of cross bifix free code arose to resolve frame synchronization via distributed sequence method with the generalization of bifix free studies. Cross bifix free code is a set of sequences in which no prefix of any length less than n of any sequences is the suffix of any sequence in the set. A cross bifix free code is constructed by using Dyck path method which achieves maximality and is non-expandable on binary set sequences for appropriate length. Many researchers propose algorithms to construct the cross bifix free code since it has a wide impact on practice. Bajic (2007) was the first researcher that constructed the code by using a Kernel set method and was extended in Bajic and Loncar-Turukalo (2014). Then, Bilotta, Pergola, and Pinzani (2012) introduced a binary cross bifix free code construction for an arbitrary length by using Dyck Path. Moreover, a ternary cross bifix free code is constructed by generalizing the construction of cross bifix free codes which using Dyck path (Affaf and Ulum, 2017a, 2017b). The code constructed using the Dyck path also extends on Bernini, Bilotta, Pinzani, Sabri, and Vajnovszki (2014) and Bilotta, Grazzini, Pergola, and Pinzani (2013). Then, Chee, Kiah, Purkayastha, and Wang (2013) introduced the construction of cross bifix free code using alphabet having q symbol. Furthermore, The construction by Chee et al. (2013) is generalized by Blackburn (2015). All the codes constructed are claimed to achieve the maximality, non-expandable on the appropriate set of sequences, except the code in Affaf and Ulum (2017a, 2017b). However, it is unknown whether the ternary codes on Affaf and Ulum (2017a, 2017b) achieve maximality of cross bifix free codes or not. If it is not, the construction cannot be categorized as good construction because a singleton set of bifix free sequences is also a cross bifix free code. In this research, the maximality of ternary cross bifix free code by Affaf and Ulum (2017a, 2017b) will be explained. In this research, the researcher explains about the maximality of ternary cross bifix free code especially the maximality of CBFS3(2m+1) and CBFS3(2m+2) for every natural number m. 24 ComTech: Computer, Mathematics and Engineering Applications, Vol. 10 No. 1 June 2019, 23-27 II. METHODS This research is a literature review. The method used is collecting a number of information relating to construction and maximality of cross bifix free code. From this amount of information, it will be used to show that ternary cross bifix codes CBFS3(2m+1) and CBFS3(2m+2) on Affaf and Ulum (2017a, 2017b) to achieve the maximum. The researcher briefly explains the definition and terminology on cross bifix free codes and the construction of cross bifix free code by Bilotta et al. (2012), Affaf and Ulum (2017a, 2017b), that is CBFS2(n), CBFS3(2m+1), and CBFS3(2m+2) respectively. The construction by Bilotta et al. (2012) is a cross bifix free set, CBFS2(n), which is non- expandable on H2(n). This implies that for every h belongs to H2(n), andit does not lie in CBFS2(n). Then, CBFS2 (n)∪{h} is not cross bifix free code. On the other side, The construction by Affaf and Ulum (2017a, 2017b) shows that CBFS3(2m+1) and CBFS3(2m+2) are a cross bifix free code. Next, the researcher will also give the construction of cross bifix free set by Chee et al. (2013), which is non- expandable on Hq (n). In the definitions and terminology on cross bifix free code, Σ is a finite set with cardinality q. The element of Σ is a symbol, and Σ is an alphabet. The set of all finite sequence (may be an empty sequence) on Σ denoted by Σ* and element of Σ* is word or codeword. Then, it will be Σ+ = Σ*\{ε} where ε is an empty sequence. For example, Σ={0,1}, ε, 101, 00011, 1110001 is the element of Σ*. For ω, an element on Σ+ is with ω = uvw where u and w are in Σ+ and v in Σ*. Then, u and w are prefix, and ω as suffix. Those are denoted by pre(ω) dan suf(ω) respectively. For prefix and suffix ω with length k is denoted by prek(ω) and sufk(ω) respectively. From the definition of prefix and suffix, it is clear that the length of prefix or suffix of a codeword in Σ+ is less than the length of the codeword. A bifix of codeword ω is a word which appears as prefix dan suffix of ω. A codeword in Σ+ is bifix free if there is no prek(ω) appearing as sufk(ω). Furthermore, non-empty subset C of Σn, that is subset of sequence on Σ with length n, is called cross bifix free code with length n if, for every ωi and ωj in C, there is no prek(ωi) appearing as sufk(ωj) for any k which is less than n. For example, for Σ={0,1}, codeword 1010101 in Σ+ contains 3 bifix codes, that are 1, 101, and 10101. Then, sets of codeword 0000111, 000110011, 0001011, 0001101, 0010101 which are subset of Σ7 is cross bifix free code with 7 length. Then, there are three constructions of binary cross bifix free code CBFS2(n). First, it is the construction of CBFS2(2m+1). Cross bifix free code of CBFS2(2m+1) is defined as: CBFS2 (2m+1)={xα : α ∈ D2m } (1) It is the set of paths beginning with a rising step linked to a 2m-length of Dyck path. For example, for n = 7, the researcher shows that CBFS2(7) has elements of 1111000, 1110100, 1110010, 1101100, and 1101010. |prek ω|i and |sufk ω|i denote the number of i which occurs in prek ω and sufk ω respectively. It can be noted that for every 0 |prek ω|1 and |sufk ω|0 ≤ |sufk ω|1 for every ω in CBFS2(2m+1). Thus, CBFS2(2m+1) is the set of bifix free sequences. On the other side, it can also be noted that for every γ and ω in CBFS2(2m+1) holds |prek ω|0 > |prek ω|1 and |sufk ω|0 ≤ |sufk ω|1. Now, if CBFS2(2m+1) is not cross bifix free code, there are α and β in CBFS2(2m+1) like prekα = sufkβ for some k which satisfies 0 < k < n. Consequently, there is also |prekα|i = |sufkβ|i for i ∈{0,1}. Then, since it is |prekα|0 > |prekα|1, it will be |sufkβ|0 > |sufkβ|1. However, this is a contradiction with |sufkω|0 ≤ |sufkω|1 for every ω in CBFS2(2m+1). Thus, the set of CBFS2(2m+1) must be a cross bifix free code. The cardinality of CBFS2(2m+1) is given by Cm, the m-th Catalan number, for natural number m ≥ 1. From the construction of CBFS2(2m+1), Bilotta et al. (2012) got Theorem II.B.1.1. For m ≥ 1, CBFS2(2m+1) was a cross bifix free code which was non-expandable on H2(2m+1). Second, it is the construction of CBFS2(2m+2) for m even. Cross bifix free code CBFS2(2m+1) for m even is defined by Bilotta et al. (2012) as: (2) It is the set of paths consisting of the following consecutive subpaths: a 2i-length Dyck path, a rise step, a 2(m-i)-length Dyck path with , and a fall step. For example, for n = 10, the researcher gets that CBFS2(10) has elements of 1111100000, 1111010000, 1110110000, 1111001000, 1110101000, 1101110000, 1111000100, 1101101000, 1110100100, 1101011000, 1101100100, 1110010100, 1110011000, 1101010100, 1011110000, 1011101000, 1011100100, 1011011000, 1011010100, 1010111000, 1010110100, 1100110100, and 1100111000. Then, the cardinality of CBFS2(2m+2) for m even is given by for integer m ≥ 0. From the construction of CBFS2(2m+2) for m even, Bilotta et al. (2012) got TheoremII.B.2.1. For m ≥ 0, CBFS2(2m+2) was a cross bifix free code which was non-expandable on H2(2m+2). Third, it is the construction of CBFS2(2m+2) for m odd cross bifix free code CBFS2(2m+2) for m odd, defined by Bilotta et al. (2012) as (3) It shows the set of paths consisting the following consecutive subpaths: a 2i-length Dyck path, a rise step, a 2(m-i)-length Dyck path for , a fall step, and excluding those consisting of the following consecutive subpaths: a rise step, a (m-1)-length Dyck path, a fall step followed by a rise step, a (m-1)-length Dyck path, and a fall step. For example, for n = 8, the researcher obtains that CBFS2(8) has elements 11110000, 11101000, 11011000, 11100100, 11010100, 10111000, 10110100, and 10101100. In cardinality of CBFS2(2m+2) for m odd, it is given by for natural number m ≥ 1. From the 25Maximality on Construction..... (Mohammad Affaf) construction of CBFS2(2m+1) for m odd, Bilotta et al. (2012) obtained Theorem II.B.3.1. For m ≥ 1, CBFS2(2m+2) was a Cross Bifix Free Set which was non-expandable on H2(2m+2). Next, there is also the construction of ternary cross bifix free code, CBFS3(2m+1). The construction of cross bifix free code by Affaf and Ulum (2017a) is: Construction II.C.1.1. Let CBFS2(2m+1) be the construction by Bilotta et al. (2012). It shows that ω = ω1 ω2 ω3…ω2m+1 is the element of CBFS2(2m+1). Next, it defines 0ω={i∈{0,1,2}:ωi = 0}. It is a set of all positions on ω which is symbolized by 0. The researcher defines the set CBFS3(2m+2) as: (4) It shows that as a set of ternary sequences which i position is symbolized by even on {0,1,2} if the symbol of the position is 0 in ω. From the Construction II.C.1.1, the researcher gets Theorem II.C.1.2. Code of CBFS3(2m+1) is a cross bifix free set with cardinality 2m+1Cm. There is also the construction of ternary cross bifix free code, CBFS3(2m+2). The construction of cross bifix free set is by Affaf and Ulum (2017b). Construction II.D.1.1. Let CBFS2(2m+2) be cross bifix free codes on Bilotta et al. (2012). The extension of CBFS2(2m+2) to CBFS3(2m+2) is given by putting all elements of CBFS2(2m+2) into CBFS3(2m+2) and all elements of H3(2m+2) which can be obtained from CBFS2(2m+2) by replacing 0 by 2 into CBFS3(2m+2). From the Construction II.D.1.1, the researcher gets Theorem II.D.1.2. Set of CBFS3(2m+2) is a cross bifix free code with cardinality for m even and for m odd. Then, it is the construction of q-ary cross bifix free code, . The construction of a cross bifix free codes by Chee et al. (2013) is as follows: Construction II.E.1.1. It is given a natural number n and some natural number k with 2 ≤ k ≤ n-2. It denotes as set of all sequence of s1 s2 s3…sn in{0,1,⋯q-1} n which satisfies two conditions: (1) s1 = s2 = s3 = ⋯ = sk = 0, s(k+1) ≠ 0 and sn ≠ 0, and (2) subsequence of s(k+2) s(k+3) s(k+4)… s(n-1) does not contain any string of consecutive 0. For example, for q = 2, n = 7, and k = 3, the researcher obtains as the binary sequence with a length of seven. It is easy to check that binary sequence set of is {0001 111,0001011,0001101,0001001} or cross bifix free code. It should be noted that the prefix of the element in starts with consecutive zeroes and the suffix contains at most k-1 consecutive zeroes. Thus, no prefix of any length of any element can matchany suffix of itself or any other element in . Therefore, must be a cross bifix free code. Next, it should consider all the possible configurations of elements in Hq(n) that can be appended to the set of . The researcher cannot append any element starting with a non- zero element since the non-zero element occurs in the last position of some element in . Similarly, the researcher cannot append any element ending with a zero element. There are other possible configurations of elements that the researcher needs to consider. First, let s be an element containing at least consecutive zeroes in the last n-1 position. The researcher considers the suffix starts with the last set of consecutive zeroes and contains the most k-1 consecutive zeroes following it. The suffix has the form of 0kαu, that α is nonzero and u is a vector of length m that has the most consecutive k-1 zeroes. Then, the element of length, n, that is 0kαu1n-m-k-1, is an element in and has a prefix matching a suffix of s. Thus, s cannot be appended to . Second, it lets s be an element which contains a prefix at most of k-1 zeroes followed by a non-zero element, that is s = 0lαu. It shows that α is non-zero, 0 < l ≤ k-1, and u has the length of n-l-1. It is readily seen that 0lα is also the suffix of the element in 0k1n-k-l-10lα in . Hence, the element in Hq(n) cannot be appended to .Thus, no additional element can be appended to the set , while it still preserves the cross-bifix-free property. From the Construction II.E.1.1, the researcher obtains Theorem II.E.1.2. It gives the natural number n and some natural number k with 2 ≤ k ≤ n-2. Set of is a cross bifix free code with cardinality (q-1)2Fk,q(n-k-2) which is non-expandable on Hq(n), and Fk,q(n) sequence satisfies Fk,q(n) = (q-1) Fk,q(n-l) with the conditional value of Fk,q(0), Fk,q(1), Fk,q(2), …, Fk,q(k-1). Moreover, there are upper bound and optimal codes. First, the upper bound of cross bifix free code will be explained. Chee et al. (2013) revisited the construction in Bajic (2007). They gave a new construction of cross-bifix- free code that generalizes the construction in two ways. Firstly, they provided new binary codes that were greater in cardinality compared to the ones in Bilotta et al. (2012) for larger lengths. In the process, they discovered the interesting connections of the size of the codes obtained in the so-called k-generalized Fibonacci number. Secondly, they generalized the construction of q-ary alphabets for any q ≥ 2. To the best of their knowledge, this was the first construction of cross bifix free codes over alphabets of size greater than two. The size of the generalized q-ary constructions was also related to a Fibonacci sequence, which they called the (q-1)-weighted k-generalized Fibonacci sequence. Using this relation to the Fibonacci sequences, Chee et al. (2013) analyzed the asymptotic size of their construction. In the process of this asymptotic analysis, they generalized a result of Dresden and Du (2014) on k-generalized Fibonacci sequence to (q-1)-weighted k-generalized Fibonacci sequence. They let C(n,q) denote the optimal size of a cross bifixfree code of length n over an alphabet of size q. An upper bound for the optimal size of a cross bifix free code is readily obtained from the research of the statistical properties of the sets in the data stream. The main object of research is the time when searching for any word of the cross bifix free code in the data stream returns with a positive match. From the information, Chee et al. (2013) got the result that the upper bound of optimal code size was no more than , that is 26 ComTech: Computer, Mathematics and Engineering Applications, Vol. 10 No. 1 June 2019, 23-27 (5) However, Blackburn (2015) stated that the optimal code size would never reach A. In Theorem II.F.1.1, it lets n and q be integers with n ≥ 2 and q ≥ 2. It also lets C(n,q) be the number of codewords in the largest cross bifix free codes of length n and symbolic q, it becomes as follows: (6) In obtaining these results, Blackburn (2015) looks at the set of that is: = {(ω,i) : ω = ω1 …ω2n-1 ∈ F 2n-1, ωi …ωi+n-1∈ C(n,q), i ∈ [2n-1]} (7) It shows that |F| = q, C(n,q) is a cross bifix free code with optimal size, and [2n-1] is {1,2,…,2n-1}. For example, (11101010010110,2) is an element of . It should consider that two elements in cannot appear as distinct cyclic subsequence of any ω of length 2n-1. Thus, for any ω in F2n-1, there is at most one choice for an integer i such that (ω,i) in . It is clear that it is | | = (2n-1) C(n,q)qn-1 since there are 2n-1 choice for i, C(n,q) choices for the codeword starting in the ith position of ω, and qn-1 choices for the remaining positions in ω. Moreover, no subsequence of any of the qconstant words ω of length in 2n-1 can appear as a codeword in C(n,q). So, the researcher gets | | ≤ q2n-1 - q < q2n-1. Finally, from | | = (2n-1) C(n,q)qn-1, it will be concluded that (2n-1) C(n,q) qn-1 < , is C(n,q) < . Second, it is optimal size of cross bifix free code. Blackburn (2015) gave the construction of cross bifix free codes C by using the construction of Chee et al. (2013). Blackburn defines it as Definition II.F.2.1. It gives the natural number k and non-empty set F with cardinality q. In S ⊆ F k, c 1 c 2 c 3 … c r ∈ F r is S-free if and only if r < k or if r ≥ k, and ci ci+1 ci+2 …ci+k-1 ∉ S is for every i in {1, 2, …, r-k+1}. By using Definition II.F.2.1, Blackburn (2015) modified the construction of Chee et al. (2013) by Construction II.F.2.2. It gives a natural number l and some natural number k with 1 ≤ k ≤ n-1 and 1 ≤ l ≤ q-1. It lets F = I ∪ J be a partition of a set Fof cardinality q into two parts I and J of cardinalities l and q-l. If S ⊆ Ik ⊆ Fk and C are the set of all c = c1 c2 c3 … cn ∈ F k like (1) c1 c2 c3 … cK ∈ S, (2) ck+1 ∈ S and cn ∈ S, and (3) ck+2 ck+3 …cn-1 is S-free, there is cross bifix free code. From the Construction II.F.2.2, Blackburn (2015) got Theorem II.F.2.3. It lets n and q be positive integers like n ≥ 2 and q ≥ 2. It lets the largest cross bifix free code have cardinality C(n,q). When n divides q, the researcher has: (8) III. RESULTS AND DISCUSSIONS In maximality on construction CBFS3(n), Affaf (2018) explained that |CBFS3 (3)| was close to the optimal cardinality that it was possible to achieve maximum cardinality. On the other side, in the construction by Affaf and Ulum (2017a), the researcher swaps symbol 1 with 0 on CBFS2 (2m+1) and extends it to CBFS3(2m+1). However, it does not pass the expansion of CBFS2(2m+2) to CBFS3(2m+2). In this research, it is assumed that the researcher swaps symbol 1 with 0 on CBFS3(2m+1) and CBFS3(2m+2). For example, for 1111000 on CBFS3(2m+2) and 111000 on CBFS3(2m+2), the researcher writes those as 0000111 and 000111 respectively. In Affaf and Ulum (2017b), CBFS3(2m+2) on Construction II.C.1.1. is also shown as (9) In other word, the researcher can simplify CBFS3(2m+1) and CBFS3(2m+2) as CBFS3(n), that is (10) (11) Furthermore, the research will claim that CBFS3(n) is non-expandable. This result is stated on Theorem III.A.1.1. For n ≥ 1, CBFS2(n) is cross bifix free code which is non-expandable on H3(n). For the proof, Since all elements of CBFS2(n) are started by 0 and finished by 1 and set of all ternary sequences, the ith position is an even on {0,1,2}. If the position is 0 on ω and the ith position is odd on {0,1,2}, the position is 1 on ω for all ω ∈ CBFS2 (n), and all elements h in H3(n) are started by symbolic odd or finished by symbolic even, there is z in such that pre1 h = suf1z or suf1h = pre1z, respectively. Thus, it is enough to show that CBFS3(n) is non-expandable on . It is all ternary sequence with length n which is started by even symbol and finished by an odd symbol. Then, it is h . The is binary sequence with length n obtained from h by replacing all even symbol on h by 0 and all odd symbol by 1. For sure, is an element of H2(n). Furthermore, by Theorem II.A.2.1, Theorem II.B.2.1, and Theorem II.C.2.1, CBFS2(n) is non-expandable on H2(n). In other words, there is ω in CBFS2(n) like prek ω = sufk or sufkω = prek for some natural number k which satisfies 1 < k < n. Therefore, there is c ∈ like prek c = sufkh or sufkc = prekh. So, CBFS3(n) is cross bifix free code which is non-expandable on H3(n). Next, Theorem III.A.I.I states that CBFS3(n) is maximal for arbitrary length. In this part, it will be shown that for n = 3, CBFS3(n) is optimal. This result states Theorem III.B.I.I. For n = 3, CBFS3(n) is optimal. From Blackburn (2015), the researcher knows that C(3,q), the number of optimality of cross bifix free code with q symbol and length n = 3, is equal to . So, for q = 3, the researcher gets . On the other side, the cardinality of CBFS3(3) is equal to 2 1+1C1 according to reference Affaf and Ulum (2017a). Finally, the researcher concludes that C(3,q)=|CBFS3(3)| is for q = 3. So, CBFS3(3) is optimal. In the comparison cardinality of CBFS3(n) and the optimal code, C(n,3)shows that the optimal cardinality 27Maximality on Construction..... (Mohammad Affaf) of the ternary cross bifix free codes with length n, and |CBFS3(n)| mentions that the cardinality of the ternary cross bifix free code CBFS3(n). Using Stirling’s approximation, the researcher obtains that the number Cm is approximate: (12) So, the researcher gets: (13) That is, (14) From here, it can be seen that |CBFS3(n)| is near- optimal cardinality so that |CBFSq(n)| for arbitrary q is very likely to achieve the maximum. IV. CONCLUSIONS In this research, the researcher has shown that the construction of CBFS3(n) on Affaf and Ulum (2017a, 2017b) achieves the maximality, and it is non-expandable in H3(n). Furthermore, for n = 3, CBFS3(n), it reaches the optimality. It can be seen that |CBFS3(n)| is near-optimal cardinality so that |CBFS3(q)| for arbitrary q is very likely to achieve the maximum too. It means that future research can be done by exploring whether for any q or the code CBFS3(q) will also be maximal. ACKNOWLEDGEMENT This research was supported by a grant from STKIP PGRI Bangkalan in 2018. The author felt indebted to the LPPM STKIP PGRI Bangkalan which provided a grant to assist this research. REFERENCES Affaf, M. (2018). Kemaksimalan kode cross bifix bebas. In Seminar Nasional Pendidikan Matematika Ahmad Dahlan (Vol. 6). Affaf, M., & Ulum, Z. (2017a). Konstruksi kode cross bifix bebas ternair untuk panjang ganjil. In Prosiding SI MaNIs (Seminar Nasional Integrasi Matematika dan Nilai-Nilai Islami) (Vol. 1, No. 1, pp. 1-5). Affaf, M., & Ulum, Z. (2017b). Konstruksi kode cross bifix bebas ternari berpanjang genap untuk mengatasi masalah sinkronisasi frame. JIKO (Jurnal Informatika dan Komputer), 2(2), 109-116. Bajic, D. (2007). On construction of cross-bifix-free kernel sets. In 2nd COST2100 MCM. Bajic, D., & Loncar-Turukalo, T. (2014). A simple suboptimal construction of cross-bifix-free codes. Cryptography and Communications, 6(1), 27-37. Bernini, A., Bilotta, S., Pinzani, R., Sabri, A., & Vajnovszki, V. (2014). Prefix partitioned gray codes for particular cross-bifix-free sets. Cryptography and Communications, 6(4), 359-369. Bilotta, S., Grazzini, E., Pergola, E., & Pinzani, R. (2013). Avoiding cross-bifix-free binary words. Acta Informatica, 50(3), 157-173. Bilotta, S., Pergola, E., & Pinzani, R. (2012). A new approach to cross-bifix-free sets. IEEE Transactions on Information Theory, 58(6), 4058-4063. Blackburn, S. R. (2015). Non-overlapping codes. IEEE Transactions on Information Theory, 61(9), 4890- 4894. Chee, Y. M., Kiah, H. M., Purkayastha, P., & Wang, C. (2013). Cross-bifix-free codes within a constant factor of optimality. IEEE Transactions on Information Theory, 59(7), 4668-4674. Dresden, G. P., & Du, Z. (2014). A simplified Binet formula for k-generalized Fibonacci numbers. Journal of Integer Sequences, 17(4), 1-9. Levy, M., & Yaakobi, E. (2017). Mutually uncorrelated codes for DNA storage. In 2017 IEEE International Symposium on Information Theory (ISIT)(pp. 3115- 3119). Massey, J. (1972). Optimum frame synchronization. IEEE Transactions on Communications, 20(2), 115-119. Nielsen, P. (1973). On the expected duration of a search for a fixed pattern in random data. IEEE Transactions on Information Theory, 19(5), 702-704. Van Wijngaarden, A. D. L., & Willink, T. J. (2000). Frame synchronization using distributed sequences. IEEE Transactions on Communications, 48(12), 2127- 2138. Weindl, J., & Hagenauer, J. (2007). Applying techniques from frame synchronization for biological sequence analysis. In 2007 IEEE International Conference on Communications (pp. 833-838). IEEE.