On Exchange-Robust and Subst-Robust Primitive Partial Words Ananda Chandra Nayak1 , Amit K. Srivastava2 and Kalpesh Kapoor1 1 Department of Mathematics Indian Institute of Technology Guwahati, Guwahati, India 2 Department of Computer Science & Engg. Indian Institute of Technology Guwahati, Guwahati, India {n.ananda,amit.srivastava,kalpesh}@iitg.ernet.in Abstract. A partial word is a word that may have some unknown places known as “holes” and can be replaced by the symbols from the underlying alphabet. A partial word u is said to be primitive if there does not exist a word v such that u is contained in a nontrivial integer power of v. We study the preservation of primitivity in partial words by the effect of some point mutation operations. In this paper, we investigate the effect of exchanging two adjacent symbols and of substituting a symbol by another symbol from the alphabet. We characterize the classes of primitive partial words with one hole which are not exchange robust and not substitute robust. We prove that the language of exchange robust primitive partial words with one hole is not right 1-dense and also prove that the language of primitive partial words with one hole which is substitute robust is closed under conjugacy relation. We show that the language of non-exchange- robust primitive partial words is not context-free over a binary alphabet. Keywords: Combinatorics on words, primitive word, partial word, exchange- robust partial word, subst-robust partial word 1 Introduction Let V be a finite alphabet. A word is a sequence of symbols from the alphabet V . A partial word is a word that may have some unknown positions known as “holes” or “do not know” symbols and are represented by ♦. The holes in the partial words are place holder for the usual symbols in the alphabet. The study of partial words is motivated by its application in molecular biology [1]. For example, the alignment of two DNA sequences to recover as much information as possible can be seen as the construction of two compatible partial words. The combinatorial Copyright c by the paper’s authors. Copying permitted for private and academic pur- poses. V. Biló, A. Caruso (Eds.): ICTCS 2016, Proceedings of the 17th Italian Conference on Theoretical Computer Science, 73100 Lecce, Italy, September 7–9 2016, pp. 190–202 published in CEUR Workshop Proceedins Vol-1720 at http://ceur-ws.org/Vol-1720 On Exchange-Robust and Subst-Robust Primitive Partial Words 191 properties of words play a vital role in the areas including formal languages [18], coding theory [2], string searching algorithms [6], and computational biology [10]. In study of an algebraic structure, it is interest to investigate the operators that preserves the algebraic structure. For example, homomorphisms are well- known structure-preserving transformations in algebra and word combinatorics. A word is said to be primitive if it cannot be represented as a power of a shorter word. The algorithmic, algebraic and applied combinatorial properties of primitive words have been extensively studied; see for example [11,12]. In [17,13], Păun et al. have studied the conditions to preserve primitivity under morphisms. Dassow et al. [7] investigated some operations where they proved that ww0 is a primitive word where w is a given word and w0 is a modified mirror image of w. This has been extended by Blanchet-Sadri et al. [5] for partial words. In [16], Păun et al. introduced the notion of robustness of primitive words as point mutation operations such as inserting a symbol, deletion of a symbol, substituting a symbol by another symbol in the primitive word which preserves the primitivity. In this paper, we discuss the robustness of primitive partial words with respect to substitution and exchange operations. These classes of primitive partial words are known as subst-robust and exchange-robust primitive partial words. The rest of the paper is organized as follows. In Section 2 we discuss the basic concepts and related results that are required in later sections. We characterize the exchange-robust primitive partial words and identify some important properties in Section 3. We prove that the language of non-exchange-robust primitive partial words is not context-free over a given alphabet in Section 4. In Section 5, we characterize the primitive partial words which remain primitive on substituting a symbol by another symbol and identify some important results. Section 6 presents about the conclusion and future work. 2 Prerequisites Let V be a finite and nontrivial alphabet. A sequence of symbols from V is called a word or string. A total word w = a0 a1 . . . an−1 of length n is a total function w : {0, 1, . . . , n − 1} 7→ V where ai ∈ V for i = 0, 1, . . . , n − 1. The length of a word w is denoted by |w| and defined as the number of symbols appearing in w. The empty word, λ, does not contain any symbol and |λ| = 0. The set of all strings over the alphabet V is denoted as V ∗ . The notation α(w) is used for the set of distinct symbols appearing in w and |α(w)| is the number of distinct symbols in w. A positive integer p is said to be a period of w if ai = ai+p for 0 ≤ i ≤ n − p − 1. Let w = xyz be a word. Then y is called a factor of w and x and z are called prefix and suffix of w, respectively. The reverse of a word w is written as rev(w) and defined as rev(w) = an−1 · · · a1 a0 when w = a0 a1 · · · an−1 . A word w is primitive if there does not exist a word u such that w = un with n ≥ 2. The language of primitive and nonprimitive words are denoted as Q and Z, respectively [11]. For a language L, we define length(L) = {|w| : w ∈ L}. A partial word u of length n over an alphabet V can be defined by a partial function u : {0, . . . , n − 1} 7→ V [4]. A partial word u may contain some 192 A. C. Nayak, A. K. Srivastava, K. Kapoor ‘do not know’ symbols known as holes along with the symbols from the underlying alphabet. A “hole” or “do not know” symbol is represented by ♦. For 0 ≤ i < n, if u(i) is defined then we say that i ∈ D(u) (the domain of u), otherwise i ∈ H(u) (the set of holes) [3]. A total word is a partial word with empty set of holes. For example, u = ♦bac♦a is a partial word of length 6 and D(u) = {1, 2, 3, 5} and H(u) = {0, 4}. We use V♦ to denote enlarged alphabet V ∪ {♦}. If u is a partial word of length n over V , then the companion of u is the total function u♦ : {0, . . . , n − 1} → V ∪ {♦}. Let u and v be two partial words of equal length. Then u is said to be contained in v, if all elements in D(u) are also in the set D(v) and u(i) = v(i) for all i ∈ D(u) and denoted by u @ v. A partial word u is said to be compatible to a partial word v if there exists a partial word w such that u @ w and v @ w and is denoted by u ↑ v. A partial word u is said to be primitive if there does not exist a word v such that u @ v n with n ≥ 2 [4]. For example, w = abb♦ is a primitive partial word and u = ab♦b is a nonprimitive partial word over V = {a, b}. The languages of primitive partial words and nonprimitive partial words are denoted as Qp and Zp , respectively. In particular, Qip denotes the language of primitive partial words with at most i holes. A local period of a partial word u is a positive integer p such that u(i) = u(i + p) whenever i, i + p ∈ D(u) [4]. Let w = uv be a nonempty partial word. Then, the partial words u and v are said to be prefix and suffix of w, respectively. A partial word y is said to be a factor of a word w if w can be written as xyz, where x, z ∈ V♦∗ and y ∈ V♦+ . The set Vi∗ contains all partial words with exactly i-holes. The partial word y is said to be proper factor if x = 6 λ or z = 6 λ. A prefix (suffix) of length k of a partial word w is denoted as pref(w, k) (suff(w, k)), respectively, where k ∈ {0, 1, . . . , |w|} and pref(w, 0) = suff(w, 0) = λ. We now recall some results from the literature that will be useful later in this paper. Theorem 1 (Fine and Wilf’s Theorem [9]). Let u and v be nonempty words over V . Suppose uh and v k , for some h and k, have a common prefix (or suffix) of length |u| + |v| − gcd(|u|, |v|). Then there exists z ∈ V ∗ of length gcd(|u|, |v|) such that u, v ∈ z ∗ . Berstel and Boasson revisited Fine and Wilf’s theorem for partial words with one hole. Theorem 2 (Berstel and Boasson [1]). Let w be a partial word with one hole which is locally p-periodic and locally q-periodic. If |w| ≥ p + q then w is gcd(p, q)-periodic. Definition 3 (Reflective Language [19]). A language L is called reflective if xy ∈ L implies yx ∈ L for all x, y ∈ V ∗ . Lemma 4. [3] Let u and v be partial words. If there exists a primitive word x such that uv @ xn for some positive integer n, then there exists a primitive word y such that vu @ y n . Moreover, if uv is primitive then vu is primitive. On Exchange-Robust and Subst-Robust Primitive Partial Words 193 Corollary 5. The languages Qp and Zp are reflective. Proposition 6. [3] Let w be a partial word with one hole such that |α(w)| ≥ 2. If a is any letter, then either w or wa is primitive. The following result shows that we can obtain at least one primitive word by substituting a symbol by another symbol. Proposition 7. [16] Let |V | ≥ 3. For any word x ∈ V ∗ and for each decompo- sition x = x1 ax2 , x1 , x2 ∈ V ∗ , a ∈ V , there is b ∈ V , b 6= a such that x1 bx2 is primitive. But the result is not true in case of partial words. For example, consider w = x♦xa. Substituting a by any letter from V will generate nonprimitive partial words. Proposition 8. [3] Let u be a partial word with one hole which is not of the form x♦x where x ∈ V + . Then for a ∈ V , at most one of the partial words ua is not primitive. 3 Exchange-Robust Primitive Partial Words with One Hole In this section, we consider a new formal language known as exchange-robust primitive partial words with one hole which remains primitive when any two consecutive symbols in a partial word are exchanged. In particular, we consider a 6= ♦ for a ∈ V because exchanging a and ♦ will generate different partial words. For example, consider w = aba♦aa ∈ Qp , but exchanging position 3 and 4 we have w0 = abaa♦a ∈ / Qp . Definition 9 (Exchange-Robust Partial Words). A primitive partial word w = a0 a1 · · · ai+1 ai+2 · · · an−1 of length n with one hole is said to be exchange- robust if and only if pref(w, i) . ai+1 ai . suff(w, n − i − 2) is a primitive partial word for all i ∈ {0, 1, . . . n − 2}. Remark : If a symbol a and a hole ♦ are adjacent, we exchange a and ♦. We denote Q1Xp as the set of all primitive partial words with one hole which are exchange-robust over the alphabet V . Clearly, the set of all exchange-robust primitive partial words with one hole is a subset Qp . There are infinitely many primitive partial words with one hole which are exchange-robust. For example, an ♦bn a, n ≥ 2 is exchange-robust. Our next result concerns the exchange of two different symbols at consecutive places in a nonprimitive total word. We prove that the new word we obtained by exchanging any two distinct consecutive symbols at any position in a nonprimitive word results in a primitive word. 194 A. C. Nayak, A. K. Srivastava, K. Kapoor Lemma 10. Let w be a total word with |α(w)| ≥ 2. If w = x1 abx2 ∈ Z with a 6= b then x1 bax2 ∈ Q. Proof. We prove it by contradiction. Let w be a nonprimitive word. Then there exists a unique primitive word u such that w = um , m ≥ 2. We can express w = um1 u1 abu2 um2 where u1 abu2 = u and m1 , m2 ≥ 0, m1 + m2 ≥ 1. Assume for contradiction that w0 = um1 u1 bau2 um2 ∈ / Q. As we know the languages Q and Z are reflective, then it is enough to consider the word abu2 um2 um1 u1 . Suppose abu2 um2 um1 u1 = v m and bau2 um2 um1 u1 = y n , m, n ≥ 2 and y ∈ Q. Let p be the common suffix of v m and y n . The words v m and y n have common suffix of length m|v| − 2 and n|y| − 2, respectively. We have |p| = m|v| − 2 = n|y| − 2. It is not possible to have m = n = 2 which is not feasible. So at least one of m and n is strictly greater than 2. Without loss of generality, let us assume that m ≥ 3 and n ≥ 2. Now, 2|p| = m|v| + n|y| − 4 ⇒ |p| = m n 2 |v| + 2 |y| − 2 ⇒ |p| ≥ |y| + |v| + 12 |v| − 2 (∵ m ≥ 3 and n ≥ 2) Since |v| ≥ 2, we obtain that |p| ≥ |y| + |v| − 1. Hence by Theorem 1, v and y are powers of the same primitive word which is a contradiction. Thus bau2 um2 um1 u1 ∈ Q which implies that w0 = um1 u1 bau2 um2 ∈ Q. t u The above result does not hold for partial words. Consider the partial word w = a♦baab ∈ Zp . if we exchange b and a, we have w0 = a♦abab ∈ / Qp . Next we study the primitive partial words with one hole in which exchange of two distinct consecutive symbols results in a nonprimitive partial word. We call this set of partial words as non-exchange-robust primitive partial words with one hole. We denote the set of non-exchange-robust primitive partial words with one hole over an alphabet V as Q1X 1X 1X p . It is easy to see that Qp ∪ Qp = Qp . 1 Definition 11 (Non-exchange-robust Primitive Partial Words). A prim- itive partial word with one hole is said to be non-exchange-robust if and only if exchange of two distinct consecutive symbols results in a nonprimitive partial word. We give the structural characterization of non-exchange-robust primitive partial words with one hole. Theorem 12. A primitive partial word w with one hole is non-exchange-robust if and only if w is contained in some word of the form uk1 u1 abu2 uk2 , a, b ∈ V, a 6= b where u1 xyu2 @ u1 abu2 for x, y ∈ V♦ such that u1 yxu2 @ u1 bau2 = um with m ≥ 2. Proof. We prove the necessary and sufficient conditions as follows: (⇒) Let w be a primitive partial word with one hole. Suppose w = v1 xyv2 @ uk1 u1 abu2 uk2 where a = 6 b such that v1 @ uk1 u1 , v2 @ u2 uk2 , xy @ ab. If we exchange x and y, we get w0 = v1 yxv2 @ uk1 u1 bau2 such that u1 bau2 = um for On Exchange-Robust and Subst-Robust Primitive Partial Words 195 m ≥ 2. Hence w0 @ uk , k ≥ 2 where k1 + m + k2 = k and thus w is not an exchange-robust primitive partial word. (⇐) Let w ∈ Q1p which is not an exchange-robust partial word. Then there exists at least one consecutive positions where exchanging them makes the partial word nonprimitive. The partial word w can be written as either v1 abv2 where v1 , v2 ∈ V♦∗ or v1 a♦v2 or v1 ♦av2 where v1 , v2 ∈ V ∗ . In first case, as we have exactly one hole, it is exactly in one among v1 or v2 . Let w0 = v1 bav2 ∈ Zp that is w0 = v1 bav2 @ um for m ≥ 2. Now v1 @ ui u1 and v2 @ u2 uj for i, j ≥ 0. Combining both we have v1 bav2 @ ui u1 bau2 uj where u1 bau2 = uk for k ≥ 2. The other two cases can be handled similarly. t u Let us define Q1X 1 p = Qp \ Qp 1X where ‘\’ is the set minus operator. There are primitive partial words of arbitrary length which are non-exchange-robust; for example, (ab)n ♦a(ab)n for n ≥ 1. We denote the set of exchange-robust (non- exchange-robust, respectively) primitive partial words with arbitrary number of holes by QX X p (Qp , respectively). The set of Qp 1X is not closed under the cyclic permutation unlike the language of del-robust primitive partial words with one hole [14]. For example, consider the partial word abbabb♦ab ∈ Qp1X . One of the cyclic permutation of the partial word is ababbabb♦, which is exchange-robust. Definition 13 ([16]). A language L is said to be dense if for any word y there exist x, z ∈ V ∗ such that xyz ∈ L. Let k be a positive integer. If for every u ∈ V ∗ there exists a word x ∈ V ∗ , |x| ≤ k such that ux ∈ L then L is said to be right k-dense. Next we prove that the language of primitive partial words with at most one hole is dense over the alphabet V♦ . We show that the language of primitive partial words with one hole which are exchange-robust is not dense. Lemma 14. The language Q1p is dense over alphabet V♦ in V1∗ . Proof. Consider a partial word w with at most one hole . Let |w| = n, n ≥ 1. There are two different cases depending upon whether w is a primitive partial word or a nonprimitive partial word. Case A. Let w is a primitive partial word. By choosing x = λ and y = λ according to definition we have xwy ∈ Q1p . Case B. Let w be a nonprimitive partial word. Here we consider two subcases depending on whether w is contained in power of a symbol from the alphabet or power of a word having at least two different letters. Case B.1 Let w @ an , n ≥ 2 for some symbol a ∈ V . It can be easily seen that wbn ∈ Q1p where a and b are two distinct letters. Here x = λ and y = bn for some b 6= a such that xwy ∈ Q1p . Case B.2 Let w @ uk , where |α(u)| ≥ 2 and k|n. By choosing x = λ and y = bn , we have xwy ∈ Q1p . 196 A. C. Nayak, A. K. Srivastava, K. Kapoor Hence, for every w ∈ V1∗ , there exist x, y ∈ V1∗ such that xwy ∈ Q1p . So Q1p is dense over the alphabet V♦ in V1∗ . t u We prove the following proposition. Proposition 15. The language Q1X p is not right 1-dense. Proof. It is sufficient to find one partial word for which we cannot find any word which satisfies the condition. Let w = x♦x be a primitive partial word with one hole where x ∈ V ∗ . Let us assume that w is not an exchange-robust primitive partial word. Here both wa and wb are not primitive. Hence we cannot find a word z with |z| ≤ 1 for w such that wz ∈ Q1X 1X p . Thus Qp is not right 1-dense. t u For the above proposition, such partial word exists. For example, take w = aaba♦aaba. We have w ∈/ Q1X p and if we concatenate a or b at the right end of w then we obtain a nonprimitive partial word. 4 QX p is not context-free In this section we prove that the language of non-exchange-robust primitive partial words is not a context-free language over a given alphabet. In our proof, we use the fact that intersection of a CFL and a regular language is also context- free. We also use the result that the family of context-free languages are closed under generalized sequential machine(gsm) mapping, and for details see [8]. Theorem 16. The language of non-exchange robust partial words is not context- free over the alphabet V = {a, b}. Proof. Consider the regular language R = ba+ ba+ ba+ ba+ . Consider the language L = {ban1 ban2 ban3 ban4 | n1 , n2 , n3 , n4 ≥ 1, (|n1 − n3 | ≤ 1, |n2 − n4 | ≤ 1, |(n1 + n2 ) − (n3 + n4 )| = 0 or 2) and (n1 6= n3 or n2 6= n4 )} (1) We claim that QX p ∩ R = L. The inclusion QX p ∩ R ⊇ L is easy to observe. For the converse, let us take a word w = ban1 ban2 ban3 ban4 ∈ QX X p ∩ R. As w ∈ Qp , then w can be represented as w = u1 abu2 such that u1 bau2 ∈ Z. We have the following possibilities of exchanging. Case 1. aban1 −1 ban2 ban3 ban4 Case 2. ban1 −1 ban2 +1 ban3 ban4 Case 3. ban1 +1 ban2 −1 ban3 ban4 Case 4. ban1 ban2 −1 ban3 +1 ban4 Case 5. ban1 ban2 +1 ban3 −1 ban4 Case 6. ban1 ban2 ban3 −1 ban4 +1 Case 7. ban1 ban2 ban3 +1 ban4 −1 On Exchange-Robust and Subst-Robust Primitive Partial Words 197 It is easy to see that all the above cases are in the language QX p only if we have (1) n1 6= n3 or n2 6= n4 (otherwise ban1 ban2 ban1 ban2 ∈ / Q) (2) |n1 − n3 | ≤ 1, |n2 − n4 | ≤ 1, |(i + j) − (k + l)| = 0 or 2 (otherwise the word w0 ∈ QXp Hence the inclusion QX p ∩ R ⊆ L. As we know that a CFL is closed under the gsm mapping then using a sequential transducer (a gsm), the language QX p ∩ R can be translated into a new language L0 = {an1 bn2 cn3 dn4 | n1 , n2 , n3 , n4 ≥ 1, |n1 − n3 | ≤ 1, |n2 − n4 | ≤ 1, |(n1 + n2 ) − (n3 + n4 )| = 0 or 2 and (n1 6= n3 or n2 6= n4 )} (2) Now we prove that L0 is not a context-free language. Assume for contradiction that L0 is context-free. Suppose there exist a constant N > 0 which must exist by Ogden’s lemma. As L0 satisfies Ogden’s lemma (see Appendix), then every w ∈ L0 , |w| ≥ N can be decomposed into w = uvxyz such that the following conditions hold: (i) vxy contains at most N marked symbols, (ii) v and y have at least one marked symbol, (iii) and uv i xy i z ∈ L0 for all i ≥ 0. Consider a string w = an1 bn2 cn3 dn4 such that n1 = N, n2 = N, n3 = N + 1 and n4 = N − 1. As |n1 − n3 | ≤ 1, |n2 − n4 | ≤ 1, |(n1 + n2 ) − (n3 + n4 )| = 0 and n1 =6 n3 , n2 6= n4 then w ∈ L0 . Let us mark all the occurrences of b which are at least N of them. Now we can decompose w = uvxyz in such a way that all the conditions of Ogden’s lemma are satisfied. Clearly, neither v nor y contain two different symbols. There are two cases depending on whether vy contains an occurrence of a or not. (I) Suppose vy does not contain any occurrence of a. In this case, we have u = aN bi1 , v = bm1 , x = bm2 , y = bm3 such that m1 +m3 ≥ 1, k1 = m1 +m2 +m3 and z = bN −(k1 +i1 ) cN +1 dN −1 . For i = 2, uvxyz = aN bN +(m1 +m3 ) cN +1 dN −1 = ap1 bp2 cp3 dp4 which is a contradiction as |p2 − p4 | ≥ 2. (II) Suppose vy contains occurrences of a. Let v = aj and y = bk for j, k ≥ 1. If j < k, then for a large value of i, we can have w0 = uv i xy i z = ap1 bp2 cp3 dp4 such that |p1 − p3 | > 1 which is a contradiction. Therefore we must have j ≥ k. Consider the word uv i xy i z which becomes aN −j+ji bN −k+ki cN +1 dN −1 . For i = 5, we have w00 = aN +4j bN +4k cN +1 dN −1 where |(N + 4j) − (N + 1)| = 4j − 1 ≥ 3, |(N + 4k) − (N − 1)| = 4k + 1 ≥ 5 and |(N + 4j + N + 4k) − (N + 1 + N − 1)| = 4(j + k) ≥ 8 which is a contradiction. Hence L0 is not context-free. As we know that the family of context-free languages is closed under sequential transducers and intersection with regular languages, we conclude that QX p is also not context-free. t u 5 Subst-Robust Primitive Partial Words In this section we study the set of primitive partial words that remains primitive on substitution of a symbol by another symbol. We refer to the definition of 198 A. C. Nayak, A. K. Srivastava, K. Kapoor substitute robust total words [16] and define symbol substitution in partial words as follows. Consider a partial word x ∈ V1+ . We define one(x) = {x1 bx2 | x = x1 ax2 , x1 , x2 ∈ V1∗ , a, b ∈ V, a 6= b}. Let L ⊆ V♦∗ and x ∈ L. Then x is called subst-robust (w.r.to L) if one(x) ⊆ L. Definition 17 (Subst-Robust Primitive Partial Words). A primitive par- tial word w with one hole is said to be subst-robust if and only if one(w) ⊆ Q1p . Remark: Since ♦ is considered as a place holder for any of the symbol from the given alphabet, only a symbol a ∈ V can be substituted by another symbol b ∈ V such that a 6= b. Proposition 18 ([16]). If L consists of only subst-robust words, then L = {w ∈ V ∗ | |w| ∈ length(L)}. The above proposition is not true in case of partial words with one hole. For example, let L0 = {a♦b, b♦b, b♦a, a♦a}. Though L0 is subst-robust, it does not contain all the partial words with one hole of length 3. Next we extend the result of Păun et al. [16] in case of partial words. Lemma 19. Let x = x1 αβx2 be a partial word with one hole where α, β ∈ V and |x| ≥ 4. Then at least one of the partial words x1 α0 βx2 , x1 αβ 0 x2 is primitive where α 6= α0 and β 6= β 0 . Proof. We prove it by contradiction. Consider a partial word x with one hole and |x| ≥ 4. As |x| ≥ 4, then x can be written as x = x1 αβx2 where α, β ∈ V , |x1 x2 | ≥ 2 and either x1 or x2 contains a hole. As Q1p is reflective, then to prove the lemma it is sufficient to prove that at least one of the partial word x2 x1 α0 β or x2 x1 αβ 0 is primitive. Assume the contrary. Let x2 x1 α0 β @ um and x2 x1 αβ 0 @ v n for m, n ≥ 2 and u, v ∈ Q. It is not possible to have m = n = 2 otherwise u = v which is a contradiction. So at least one of m, n is greater than 2. without loss of generality, let us assume that m ≥ 3, n ≥ 2. Similarly, we cannot have |u| = 1; otherwise x2 x1 α0 β @ um implies that u ∈ {a, b}. Since α 6= α0 , β 6= β 0 then x2 x1 αβ 0 is primitive which is a contradiction to the assumption. Hence we have |u| ≥ 2. Now, we have |x2 x1 | = m|u| − 2 and |x2 x1 | = n|v| − 2 which implies that 2|x2 x1 | = m|u| + n|v| − 4 ⇒ |x2 x1 | = m n 2 |u| + 2 |v| − 2 As m ≥ 3 and n ≥ 2, we can write that |x2 x1 | ≥ |u| + |v| + 12 |u| − 2. Also |u| ≥ 2 implies that |x2 x1 | ≥ |u| + |v| − 1. We consider the following cases. (a) If |x2 x1 | = |u| + |v| − 1 then m = n = 2 which leads to a contradiction. (b) If |x2 x1 | > |u|+|v|−1 then by Theorem 2, there exist a word y such that u = y k and v = y l for some integers k and l. Hence x2 x1 α0 β @ y km and x2 x1 αβ 0 @ y ln which is a contradiction. Thus at least one of the x2 x1 α0 β, x2 x1 αβ 0 is a primitive partial word. t u On Exchange-Robust and Subst-Robust Primitive Partial Words 199 In the above lemma, |x| ≥ 4 is necessary. For example, let x = ♦ab and substi- tuting a by b or b by a will generate nonprimitive partial words. Lemma 19 does not hold for partial words with at least two holes. For example, w = ♦aa♦ over V = {a, b}. Substituting first occurrence of a by b or last occurrence of a by b will generate nonprimitive partial words. We denote Q1S p as the set of primitive partial words with one hole which remains primitive on substitution of a symbol by another symbol from the given alphabet. There are infinitely many primitive partial words with one hole which are subst-robust. For example, w = (ab)n ♦ for n ≥ 2 is subst-robust. It is worth mentioning here that there are primitive partial words with one hole which are at the same time exchange-robust and subst-robust. An example of such partial word is wm = ♦aba2 b2 . . . am bm for m ≥ 2 over V = {a, b}. Let w = ab♦a be a primitive partial word over V = {a, b}. Substituting last occurence of a by b will generate a nonprimitive partial word. We call the set of primitive partial words as non-subst-robust primitive partial words with one hole which on substitution of a symbol by another symbol results in a nonprimitive partial word and denote by Q1Sp . 0 Q1S 1 / Q1p } p = {w | w = u1 au2 ∈ Qp and w = u1 bu2 ∈ Observe that Q1S 1 1S p = Qp \ Qp . Next, we characterize the set of primitive partial words with one hole which are not subst-robust. Theorem 20. A primitive partial word with one hole w = xay where x, y ∈ V♦∗ , a ∈ V is not subst-robust if and only if it is contained in a word of the form uk1 u1 au2 uk2 where x @ uk1 u1 , y @ u2 uk2 with k1 + k2 ≥ 1 such that u1 bu2 = u where a 6= b. Proof. (⇒): Let us assume that w = xay is a non-subst-robust primitive partial word with one hole. Then there exist a position in w in which a symbol can be substituted by another symbol and makes it nonprimitive. Let w0 = xby be the nonprimitive partial word and hence w0 = xby @ um , m ≥ 2 for some u ∈ Q. Therefore, we have x @ uk1 u1 , y @ u2 uk2 such that u1 bu2 = u for b 6= a. Hence w @ uk1 u1 au2 uk2 . (⇐): Let w be a primitive partial word with one hole and w = xay @ uk1 u1 au2 uk2 , k1 + k2 ≥ 1 where x, y ∈ V♦∗ , a ∈ V with x @ uk1 u1 and y @ u2 uk2 . Also it is given that substituting a symbol b 6= a, we have u1 bu2 = u. If we substitute a symbol b 6= a in w = xay, we get w0 = xby such that w0 = xby @ uk1 uuk2 = uk1 +k2 +1 and k1 + k2 + 1 ≥ 2. Hence w = xay is not subst-robust. Next we prove that the language of subst-robust primitive words with one hole is closed under cyclic permutation. We know that two partial words x and y are conjugate if there exist partial words u and v such that x @ uv and y @ vu. A language L is closed under conjugacy relation if the cyclic permutations of all the words are in L. 200 A. C. Nayak, A. K. Srivastava, K. Kapoor Lemma 21. The language Q1S p is closed under conjugacy relation. Proof. We prove it by contradiction. Let w = v1 v2 be a primitive partial word 0 with one hole such that w ∈ Q1S p . Suppose w = v2 v1 ∈ / Q1S 1S p . w = v1 v2 ∈ Qp 0 1S 0 implies w = v1 v2 ∈ Qp . Since w = v2 v1 ∈/ Qp then we can write w = v2 v1 @ uk1 u1 au2 uk2 such that u1 bu2 = u. We consider two cases depending on whether a is in v1 or in v2 . Case A. If the symbol a in contained in v2 then we consider the following possibilities. Case A.1 If entire u1 au2 is from v2 then v2 @ uk1 u1 au2 ur u01 and v1 @ u02 us where u = u01 u02 and r + s + 1 = k2 . Now v1 v2 @ u02 us uk1 u1 au2 ur u01 . Substituting a by b we obtain a nonprimitive partial word which is a contradiction that v1 v2 ∈ Q1S p . Case A.2 If a portion of u2 is from v2 then v2 @ uk1 u1 au02 and v1 @ u002 uk2 where u2 = u02 u002 . Now v1 v2 @ u002 uk2 uk1 u1 au02 which will result a nonprimitive partial word after a is substituted by the letter b. Moreover v1 v2 @ (u002 u1 bu02 )k1 +k2 +1 and v1 v2 is not subst-robust primitive partial word. Case B. If the symbol a is not contained in v2 then we can handle two different cases as the previous one. t u The following corollary is a consequence of Theorem 20. Corollary 22. A primitive partial word with one hole w ∈ Q1S p if and only if it is either contained in un u0 a or it’s cyclic permutation for some u ∈ Qp and u0 b = u for b 6= a. Proof. The proof of necessary and sufficient conditions are as follow: (Necessary Part:) Let w = xay be a primitive partial word with one hole which is not subst-robust.Then w = xay @ uk1 u1 au2 uk2 for some u ∈ Q such that u1 bu2 = u and k1 + k2 + 1 ≥ 2. As the language Qp1S is reflective, then yxa @ u2 uk2 uk1 u1 a = (u2 u1 b)k1 +k2 u2 u1 a = xk1 +k2 x0 a where x = u2 u2 and x0 = u2 u1 . (Sufficient Part:) Let w be a partial word. If w is contained in un u0 a where 0 u b = u or it’s cyclic permutation then by substituting a by b where b 6= a, we obtain w0 ∈ un+1 which is a nonprimitive partial word. Hence w is not a subst-robust primitive partial word. 6 Conclusion We investigated exchange-robust and substitute robust primitive partial words with one hole. The structural characterization of each of the class of primitive partial words with one hole have been discussed and also some important com- binatorial properties related to each of the class have been identified. We have shown that the language of non-exchange-robust primitive partial words is not On Exchange-Robust and Subst-Robust Primitive Partial Words 201 a context-free language. We mention some of the interesting questions that are still unanswered. (1) The notion of robustness can be studied further for partial words with at least two holes. (2) Is the language of primitive partial words QX p context-free? (3) One can consider to exchange two symbols at any positions and preserve primitivity. References 1. Berstel, J., Boasson, L.: Partial words and a theorem of Fine and Wilf. Theoretical Computer Science 218(1), 135–141 (1999) 2. Berstel, J., Perrin, D., et al.: Theory of codes, vol. 22. Citeseer (1985) 3. Blanchet-Sadri, F.: Primitive partial words. Discrete Applied Mathematics 148(3), 195–213 (2005) 4. Blanchet-Sadri, F.: Algorithmic combinatorics on partial words. CRC Press (2007) 5. Blanchet-Sadri, F., Nelson, S., Tebbe, A.: On operations preserving primitivity of partial words with one hole. In: AFL. pp. 93–107 (2011) 6. Crochemore, M., Rytter, W.: Jewels of stringology: text algorithms. World Scientific (2002) 7. Dassow, J., Martin, G.M., Vico, F.J.: Some operations preserving primitivity of words. Theoretical Computer Science 410(30), 2910–2919 (2009) 8. Dömösi, P., Ito, M.: Context-free languages and primitive words. World Scientific (2014) 9. Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society 16(1), 109–114 (1965) 10. Gusfield, D.: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press (1997) 11. Lothaire, M.: Combinatorics on Words. Cambridge University Press (1997) 12. Lothaire, M.: Applied Combinatorics on Words. Cambridge University Press (2005) 13. Mitrana, V.: Primitive morphisms. Information processing letters 64(6), 277–281 (1997) 14. Nayak, A.C., Srivastava, A.K.: On del-robust primitive partial words with one hole. In: Language and Automata Theory and Applications, pp. 233–244. Springer (2016) 15. Ogden, W.: A helpful result for proving inherent ambiguity. Theory of Computing Systems 2(3), 191–194 (1968) 16. Păun, G., Santean, N., Thierrin, G., Yu, S.: On the robustness of primitive words. Discrete applied mathematics 117(1), 239–252 (2002) 17. Paun, G., Thierrin, G.: Morphisms and primitivity. Bulletin-European Association For Theoretical Computer Science 61, 85–88 (1997) 18. Rozenberg, G., Salomaa, A.: Handbook of Formal Languages: Volume 1. Word, Language, Grammar, vol. 1. Springer (1997) 19. Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press (2008) A Ogden’s Lemma for CFL For completeness we recall the Ogden’s lemma to prove that the language of non-exchange-robust partial words is not context-free. 202 A. C. Nayak, A. K. Srivastava, K. Kapoor Lemma 23 (Ogden’s Lemma [15]). Let L be a context-free language. The there exists a constant N > 0 such that every string w ∈ L that has at least N marked symbols can be decomposed in the form w = uvxyz such that the following conditions hold: (i) together v and x have at least one marked symbol. (ii) vxy contains at most N marked symbols. (iii) uv i xy i z ∈ L for all i ≥ 0.