=Paper=
{{Paper
|id=Vol-1720/full14
|storemode=property
|title=On Exchange-Robust and Subst-Robust Primitive Partial Words
|pdfUrl=https://ceur-ws.org/Vol-1720/full14.pdf
|volume=Vol-1720
|authors=Ananda Chandra Nayak,Amit Kumar Srivastava,Kalpesh Kapoor
|dblpUrl=https://dblp.org/rec/conf/ictcs/NayakSK16
}}
==On Exchange-Robust and Subst-Robust Primitive Partial Words==
https://ceur-ws.org/Vol-1720/full14.pdf
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.