# Insertions Yielding Equivalent Double Occurrence Words

Daniel A. Cruz
University of South Florida  Tampa FL  33620  USA
<EMAIL_ADDRESS>Margherita Maria Ferrari
University of South Florida  Tampa FL  33620  USA
<EMAIL_ADDRESS>Nataša Jonoska
University of South Florida  Tampa FL  33620  USA
<EMAIL_ADDRESS>Lukas Nabergall
University of Waterloo  Waterloo ON  N2L 3G1  Canada
<EMAIL_ADDRESS>Masahico Saito
University of South Florida  Tampa FL  33620  USA
<EMAIL_ADDRESS>Department of Mathematics and Statistics, University of South
Florida, Tampa FL, 33620, USA

###### Abstract

A double occurrence word (DOW) is a word in which every symbol appears exactly
twice; two DOWs are equivalent if one is a symbol-to-symbol image of the
other. We consider the so called repeat pattern ($\alpha\alpha$) and the
return pattern ($\alpha\alpha^{R}$), with gaps allowed between the $\alpha$’s.
These patterns generalize square and palindromic factors of DOWs,
respectively. We introduce a notion of inserting repeat/return words into DOWs
and study how two distinct insertions into the same word can produce
equivalent DOWs. Given a DOW $w$, we characterize the structure of $w$ which
allows two distinct insertions to yield equivalent DOWs. This characterization
depends on the locations of the insertions and on the length of the inserted
repeat/return words and implies that when one inserted word is a repeat word
and the other is a return word, then both words must be trivial (i.e., have
only one symbol). The characterization also introduces a method to generate
families of words recursively.

Insertions on Double Occurrence Words

##  1 Introduction

A word $w$ over an alphabet $\Sigma$ is a double occurrence word (DOW) if each
element of $\Sigma$ appears either zero or two times. DOWs have been studied
in relation to knot theory [4, 10, 19], mathematical logic [8], and algebraic
combinatorics [17]. DOWs are also known as Gauss words and are closely related
to linear diagrams, chord diagrams, and circle graphs. In the context of
genomics, DOWs and operations on DOWs have been used in studies of DNA
rearrangement [2, 3, 9, 11]. By modeling the DNA rearrangement process using
DOWs, it was observed that over 95% of the scrambled genome of the ciliate
Oxytricha trifallax could be described by iterative insertions of the “repeat
pattern” ($\alpha\alpha$) and the “return pattern” ($\alpha\alpha^{R}$) [5].
Roughly speaking, a pattern is a sequence of variables, and we say that an
instance of a pattern appears in a word $w$ if each variable of the pattern
can be mapped to a non-empty factor of $w$ [11]. The repeat pattern
$\alpha\alpha$ generalizes square factors while the return pattern
$\alpha\alpha^{R}$ generalizes palindromic factors. We refer to instances of
the repeat and return pattern as repeat words and return words, respectively
[1, 5, 11].

Patterns in DNA rearrangement are discussed in [5], while transformations on
DOWs where instances of patterns are deleted or inserted are considered in
[11]. In studies of DNA rearrangement, it has been observed that the insertion
of a repeat or return pattern may have evolutionary significance [6], and the
process of obtaining one word from another by the insertion of a repeat or
return word may be of interest. Relatedly, similar operations on words have
been studied with applications to computational linguistics and natural
language processing. In the literature, four so-called edit operations are
primarily considered: insertion of a symbol, deletion of a symbol,
substitution of one symbol with another, and transposition of two adjacent
symbols [12, 15, 16]. The pattern-based word transformations considered here
may be regarded as a generalization of these edit operations.

Here we define a notion of inserting repeat and return words in DOWs at
prespecified indices. We consider equivalence classes of DOWs where two DOWs
are equivalent if one is obtained from the other by a symbol-to-symbol
morphism. Equivalent words correspond to the same chord diagrams, as well as
isomorphic assembly graphs. The main question considered here is under which
conditions two distinct insertions into the same word can produce equivalent
DOWs. A pair of insertions in a given DOW falls in one of the three types:
interleaving, nested, and sequential (see Section 3 for definitions). The
paper characterizes the words that yield the equivalent results in each of
these situations.

##  2 Background

An ordered alphabet $\Sigma$ is a countable set with a linear order that is
bounded below which can naturally be identified with the set of natural
numbers $\mathbb{N}=\\{1,2,\ldots\\}$, so we set $\Sigma=\mathbb{N}$
throughout the rest of the paper. For $n\in\mathbb{N}$, we denote
$\\{1,2,\ldots,n\\}$ by $[n]$. For the remainder of the paper, we reserve the
letters $a,b$ as symbols in $\Sigma$, and reserve the letters $s,t,u,\ldots,z$
as “words” in $\Sigma^{\ast}$ (defined below).

We use standard definitions and conventions (e.g., [7, 8, 13, 11]). A word $w$
over $\Sigma$ is a finite sequence of symbols $a_{1}\cdots a_{n}$ in $\Sigma$;
the length of $w$, denoted $|w|$, is $n$. The set of all words over $\Sigma$
is denoted by $\Sigma^{*}$ and includes the empty word $\epsilon$ whose length
is $0$; and $\Sigma^{+}=\Sigma^{*}\setminus\\{\epsilon\\}$. The set of all
symbols $\\{a_{1},\ldots,a_{n}\\}$ comprising $w$ is denoted by $\Sigma[w]$.
The reverse of  $w=a_{1}a_{2}\cdots a_{n}$ ($a_{i}\in\Sigma$) is the word
$w^{R}=a_{n}\cdots a_{2}a_{1}$. The word $v$ is a factor of the word $w$,
denoted $v\sqsubseteq w$, if $\exists w_{1},w_{2}\in\Sigma^{*}$ such that
$w=w_{1}vw_{2}$; if $w_{1}=\epsilon$ then $v$ is a prefix of $w$, while if
$w_{2}=\epsilon$ then $v$ is a suffix of $w$; the word $w_{1}w_{2}$ is denoted
by $w-v$. If $|v|<|w|$, then $v$ is a proper factor, prefix, or suffix as
appropriate. The set of common factors of $u,v\in\Sigma^{*}$ is denoted by
$u\cap v$. Let $1\leq d\leq n=|w|$, and write $w=a_{1}a_{2}\cdots a_{n}$. The
prefix (suffix resp.) of $w$ with length $d$ is denoted
$\operatorname{pre}(w,d)=a_{1}a_{2}\cdots a_{d}$
($\operatorname{suf}(w,d)=a_{n-d+1}\cdots a_{n-1}a_{n}$ resp.).

A word $w$ in $\Sigma^{\ast}$ is a double occurrence word (DOW) if every
symbol in $w$ appears either zero or twice. We use $\Sigma_{DOW}$ to denote
the set of all double occurrence words over $\Sigma$. Single occurrence words
(SOWs) denoted $\Sigma_{SOW}$ are nonempty words with distinct symbols. Given
$w\in\Sigma_{DOW}$, $|w|/2$ is the size of $w$. Given $u\in\Sigma_{SOW}$, we
say that $uu$ is a repeat word in $w$ if $w=z_{1}uz_{2}uz_{3}$ for some
$z_{1},z_{2},z_{3}\in\Sigma^{\ast}$. Similarly, $uu^{R}$ is a return word in
$w$ if $w=z_{1}uz_{2}u^{R}z_{3}$ for some $z_{1},z_{2},z_{3}\in\Sigma^{\ast}$.

A morphism $f$ on $\Sigma^{*}$ induced by a bijection (symbol-to-symbol map)
on $\Sigma$ is called an equivalence map. We write $w_{1}\sim w_{2}$ if there
is an equivalence map $f$ such that $f(w_{1})=w_{2}$. The relation $\sim$ is
an equivalence on $\Sigma^{\ast}$. A word $w=a_{1}a_{2}\cdots a_{n}$ is in
ascending order if $a_{1}$ is the least element in the alphabet and the first
appearance of a symbol is one greater than the largest of all preceding
symbols in the word [3]. Since a word in ascending order is unique in the
considered alphabet, we take words in ascending order as class representatives
of the equivalence classes determined by the relation $\sim$.

###### Example 2.1

Consider the words $w=121323$ and $w^{\prime}=131232$. Note that $w\sim
w^{\prime}$, but $w$ is in ascending order while the word $w^{\prime}$ is not
because the symbol $3$ appears before $2$.

###### Definition 2.2

Let $w=z_{1}z_{2}z_{3}\in\Sigma_{DOW}$ for some
$z_{1},z_{2},z_{3}\in\Sigma^{\ast}$ be in ascending order. Let $u$ be a SOW
over $\Sigma\setminus\Sigma[w]$ which is in ascending order and $|u|=\nu$.
Suppose $k$ and $\ell$ are such that $k-1=|z_{1}|$ and $\ell-1=|z_{1}z_{2}|$.
Then

  * •

$w^{\prime}=z_{1}uz_{2}uz_{3}$ is obtained from $w$ by a repeat insertion
denoted $w^{\prime}=w\star\rho(\nu,k,\ell)$, and

  * •

$w^{\prime}=z_{1}uz_{2}u^{R}z_{3}$ is obtained from $w$ by a return insertion
denoted $w^{\prime}=w\star\tau(\nu,k,\ell)$.

We do not specify the word $u$ in the notation of repeat and return insertions
because the inserted word has distinct symbols from $w$ and consists of
symbols immediately following the largest symbol of $w$; hence it is uniquely
determined by its length.

###### Example 2.3

Let $w=1232314554$, then

$\displaystyle w\star\rho(2,4,6)$
$\displaystyle=123{\color[rgb]{1,0,0}\underline{67}}23{\color[rgb]{1,0,0}\underline{67}}14554=w_{1}\qquad\qquad
w\star\tau(2,7,11)=123231{\color[rgb]{1,0,0}\underline{67}}4554{\color[rgb]{1,0,0}\underline{76}}=w_{3}$
$\displaystyle w\star\rho(2,2,4)$
$\displaystyle=1{\color[rgb]{1,0,0}\underline{67}}23{\color[rgb]{1,0,0}\underline{67}}2314554=w_{2}\qquad\qquad\,\,\,w\star\tau(2,9,9)=12323145{\color[rgb]{1,0,0}\underline{6776}}54=w_{4}$

Observe that $w_{1}\sim w_{2}$ and $w_{3}\sim w_{4}$ but $w_{1}\not\sim
w_{3}$.

Let $v$ be a repeat or return word in $w\in\Sigma_{DOW}$; we write
$v=uu^{\prime}$ where $u^{\prime}=u$ if $v$ is a repeat word and
$u^{\prime}=u^{R}$ if $v$ is a return word. For the rest of the paper, we use
$u^{\prime}$ for a SOW $u$ to denote $u$ or $u^{R}$ as is appropriate in the
context of repeat and return words. We use the notation
$w\star\mathcal{I}(\nu,k,\ell)$ to indicate that the insertion is either a
repeat insertion or a return insertion. We denote by Rep (Ret resp.) the set
of all repeat insertions (return insertions resp.), and we write
$\mathcal{I}\in\operatorname{Rep}$ ($\mathcal{I}\in\operatorname{Ret}$ resp.)
to indicate that the insertion is a repeat insertion (return insertion resp.).
Observe that $\left(w\star\mathcal{I}(\nu,k,\ell)\right)^{R}\sim
w^{R}\star\mathcal{I}(\nu,|w|-\ell+2,|w|-k+2)$. We say that $uu$ or $uu^{R}$
is a trivial repeat or return word, respectively, if $|u|=1$, and an insertion
$\mathcal{I}(1,k,\ell)$ is called trivial. A trivial repeat insertion into $w$
is also a trivial return insertion, so we focus on nontrivial insertions. As a
convention, if $k=\ell$ we set
$w\star\mathcal{I}(\nu,k,k)=z_{1}uu^{\prime}z_{2}z_{3}$ as shown in $w_{4}$ in
Example 2.3.

###### Remark 2.4

Suppose $w\star\mathcal{I}_{1}(\nu_{1},k_{1},\ell_{1})\sim
w\star\mathcal{I}_{2}(\nu_{2},k_{2},\ell_{2})$, then $\nu_{1}=\nu_{2}=\nu$,
and because the inserted word has distinct symbols from $w$, by definition we
have that $u_{1}u_{1}^{\prime}$ inserted by $\mathcal{I}_{1}$ and
$u_{2}u_{2}^{\prime}$ by $\mathcal{I}_{2}$ are such that $u_{1}=u_{2}=u$ (and
$u_{1}^{\prime},u_{2}^{\prime}\in\\{u,u^{R}\\}$). For all $w^{\prime}\sim w$
we also have that $w^{\prime}\star\mathcal{I}_{1}(\nu,k_{1},\ell_{1})\sim
w^{\prime}\star\mathcal{I}_{2}(\nu,k_{2},\ell_{2})$. This follows from the
fact that if
$f(w\star\mathcal{I}_{1}(\nu,k_{1},\ell_{1}))=w\star\mathcal{I}_{2}(\nu,k_{2},\ell_{2})$
and $g(w^{\prime})=w$ for equivalence maps $f$ and $g$, then
$f(g(w^{\prime})\star\mathcal{I}_{1}(\nu,k_{1},\ell_{1}))=g(w^{\prime})\star\mathcal{I}_{2}(\nu,k_{2},\ell_{2})$.

Considering the above remark, we have the following definition for equality of
two insertions.

###### Definition 2.5

We say that two nontrivial insertions $\mathcal{I}_{1}(\nu,k_{1},\ell_{1})$
and $\mathcal{I}_{2}(\nu,k_{2},\ell_{2})$ are equal for a DOW $w$ if
$w\star\mathcal{I}_{1}(\nu,k_{1},\ell_{1})\sim
w\star\mathcal{I}_{2}(\nu,k_{2},\ell_{2})$ and
$(k_{1},\ell_{1})=(k_{2},\ell_{2})$.

It becomes a natural question to consider the situations when two distinct
(unequal) nontrivial insertions into $w$ yield equivalent words.

The following three results are used repeatedly throughout Section 3. The
first generalizes a well known lemma by Lyndon and Schützenberger [14]; it
describes the structures of two equivalent words where a suffix of one word is
a prefix of the other.

###### Lemma 2.6

Let $s\in\Sigma^{+}$ and $t,z\in\Sigma^{\ast}$ such that $f(sz)=zt$ for an
equivalence map $f$. Then, $s=s_{1}s_{2}$ with $z=f(s)\cdots
f^{h-1}(s)f^{h}(s_{1})$, and $t=f^{h}(s_{2})f^{h+1}(s_{1})$ for
$h=\left\lceil|z|/|s|\right\rceil$.

(a)

(b)

Figure 1: Representation of $sz\sim zt$ when (a) $0<|z|<|s|$, or (b)
$|z|\geq|s|$.

###### Proof 2.7

If $z=\epsilon$, then $f(t)=s$ and the statement holds with $h=0$ and
$s=s_{1}$. If $0<|z|<|s|$, then write $s=s_{1}s_{2}$ where $|s_{1}|=|z|$. It
follows that $f(s_{1})=z$ because $f(s_{1})$ is a prefix of $f(s)$, and
$f(s_{2})$ is a prefix of $t$ because $f(s_{2})$ is a suffix of $f(s)$ and
$f(s)\cap t\neq\emptyset$. Then $sz\sim zt$ implies $f(z)=f^{2}(s_{1})$ is a
suffix of $t$, so $t=f(s_{2})f^{2}(s_{1})$ (Figure 1a). If $|z|\geq|s|$, let
$h=\left\lceil|z|/|s|\right\rceil$ and write $s=s_{1}s_{2}$ where
$|s_{1}|=|z|-(h-1)|s|$. Note that $s_{1}\neq\epsilon$. Then $z=f(s)\cdots
f^{h-1}(s)f^{h}(s_{1})$ and $t=f^{h}(s_{2})f^{h+1}(s_{1})$ (Figure 1b).

In Lemma 2.6, note that if $sz=zt$, then $f$ is the identity mapping, and so
we arrive at the lemma from [14]. In Section 3, we use the lemma symmetrically
when $s=t$, and $sz\sim zs$. An illustration of the situation described with
Lemma 2.6 can be seen within the prefixes of $w_{1}$ and $w_{2}$, as well as
in the suffixes of $w_{3}$ and $w_{4}$.

###### Lemma 2.8

Suppose $x,y_{1},y_{2}\in\Sigma^{+}$ with $|y_{1}|=|y_{2}|$ and $f$ is an
equivalence map. Let $f(xy_{1})=y_{1}x$ and either $f(x^{R}y_{2})=y_{2}x^{R}$
or $f(y_{2}x)=xy_{2}$. Then either $|x|\leq|y_{1}|=|y_{2}|$ or
$\Sigma[x]\cap\Sigma[y_{2}]\not=\emptyset$.

###### Proof 2.9

Let $x=x^{\prime}a$ for $a\in\Sigma$ and let $|x|>|y_{1}|=|y_{2}|$. Then
$f(x^{\prime}ay_{1})=y_{1}x$ implies $f(a)\in\Sigma[x]$. In both cases when
$f(ax^{\prime R}y_{2})=y_{2}x^{R}$ or $f(y_{2}x^{\prime}a)=xy_{2}$ we have
$f(a)\in\Sigma[y_{2}]$.

The last lemma from [11] details useful properties of repeat and return words.

###### Lemma 2.10

Let $w\in\Sigma_{DOW}$, let $xx^{\prime}$ and $yy^{\prime}$ be two repeat
(return resp.) words in $w$, and let $u\in x\cap y$. Then both
$(x-u)(x^{\prime}-u)$ ($(x-u)(x^{\prime}-u^{R})$ resp.) and
$(y-u)(y^{\prime}-u)$ ($(y-u)(y^{\prime}-u^{R})$ resp.) are repeat (return
resp.) words in $w$. Furthermore, if $xx^{\prime}$ and $yy^{\prime}$ are
repeat and return words, respectively, in $w$, then $x\cap y=\\{\epsilon\\}$,
$|x|=1$, or $|y|=1$.

##  3 Insertions Yielding Equivalent Words

In this section, we fix $w\in\Sigma_{DOW}$ in ascending order of length $n$.
Let $\mathcal{I}_{i}(\nu_{i},k_{i},\ell_{i})$ for $i=1,2$ be distinct
insertions into $w$ such that
$w_{i}=w\star\mathcal{I}_{i}(\nu_{i},k_{i},\ell_{i})$ are equivalent with
$f(w_{1})=w_{2}$ for an equivalence map $f$. By Remark 2.4 and Definition 2.5,
$\nu_{1}=\nu_{2}=\nu$ and $(k_{1},\ell_{1})\neq(k_{2},\ell_{2})$. Without loss
of generality, we assume that $k_{1}\leq k_{2}$. Because the inserted words
have no symbols in common with $w$, we consider that $uu_{1}^{\prime}$ is
inserted with $\mathcal{I}_{1}$ and $uu_{2}^{\prime}$ is inserted with
$\mathcal{I}_{2}$ ($u_{1}^{\prime},u_{2}^{\prime}\in\\{u,u^{R}\\}$). If
$\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$
($\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$ resp.), then we
consider that they both insert $uu^{\prime}$.

Observe that $k_{1}\neq k_{2}$, because if $k_{1}=k_{2}$, then $f(u)=u$,
implying $\ell_{1}=\ell_{2}$, and hence the insertions are equal. Up to
symmetry, the indices $k_{1},k_{2},\ell_{1},\ell_{2}$ can have the following
possibilities.

  * •

Interleaving insertions, $k_{1}<k_{2}\leq\ell_{1}<\ell_{2}$: $\mathcal{I}_{2}$
inserts $u$ at a location before $\mathcal{I}_{1}$ inserts $u_{1}^{\prime}$.

  * •

Nested insertions, $k_{1}<k_{2}\leq\ell_{2}<\ell_{1}$: $\mathcal{I}_{2}$
inserts $u$ and $u_{2}^{\prime}$ at locations before $\mathcal{I}_{1}$ inserts
$u_{1}^{\prime}$.

  * •

Sequential insertions, $k_{1}\leq\ell_{1}<k_{2}\leq\ell_{2}$:
$\mathcal{I}_{2}$ inserts $u$ and $u_{2}^{\prime}$ at locations after
$\mathcal{I}_{1}$ inserts $u_{1}^{\prime}$.

Further, without loss of generality, we can assume $k_{1}=1$ and
$\ell=\max\\{\ell_{1},\ell_{2}\\}=n+1$. For the remainder of the section, we
set $w=z_{1}z_{2}z_{3}$ where $|z_{1}|=k_{2}-1$ in the case of interleaving
and nested insertions and $|z_{1}|=\ell_{1}-1$ in the case of sequential
insertions. Also $|z_{1}z_{2}|$ equals $\ell_{1}-1$, $\ell_{2}-1$, or
$k_{2}-1$ for interleaving, nested, or sequential insertions, respectively.
Hence the four positions for the two insertions into $w$ are 1, $|z_{1}|+1$,
$|z_{1}z_{2}|+1$, and $n+1$. We consider that $w$ is in ascending order.

###  3.1 Interleaving and Nested Insertions

Let $t\in\Sigma_{DOW}$ be in ascending order. We say that $t$ is an
interleaving sequence of return words if there exist integers $h,\nu\geq 1$
such that $t=x_{1}x_{2}\cdots x_{h}x_{1}^{R}x_{2}^{R}\cdots x_{h}^{R}$, where
$|x_{i}|=\nu$ for all $i$; in this case we write $t=\text{Int}(h,\nu)$.
Clearly, $x_{i}\in\Sigma_{SOW}$ for all $i$. Note that if $\nu=1$, then
$\text{Int}(h,1)$ is a repeat word of size $h\geq 1$.

In Proposition 3.1, we consider two interleaving insertions into a DOW $w$
which yield equivalent words. To describe the structure of $w$, we track the
image of the inserted word $u$ in the resulting words
$w_{1},w_{2}\in\Sigma_{DOW}$ by using the equivalence map as described by
Lemmas 2.6 and 2.8. We also use this “image tracking” method when considering
nested and sequential insertions.

###### Proposition 3.1

If $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$ are interleaving insertions, that
is $k_{1}<k_{2}\leq\ell_{1}<\ell_{2}$, then $z_{1},z_{3}\in\Sigma_{SOW}$ are
such that

  1. (1)

If $\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$, then $z_{1}z_{3}$
is a repeat word in $w$.

  2. (2)

If $\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$, then
$z_{1}z_{3}\sim\text{Int}(h,\nu)$ where $h=(k_{2}-k_{1})/\nu$ is a positive
integer.

###### Proof 3.2

We have that $w_{1}=uz_{1}z_{2}u_{1}^{\prime}z_{3}$ and
$w_{2}=z_{1}uz_{2}z_{3}u_{2}^{\prime}$. Because $uz_{1}\sim z_{1}u$ and $u$ is
SOW, we have that $z_{1}$ is a SOW by Lemma 2.6. Similarly, we have that
$z_{3}$ is a SOW, and thus $|z_{1}|=|z_{3}|$ since $z_{2}$ is a DOW. Moreover,
$z_{1}=x_{1}x_{2}\cdots x_{h}$, where $f^{i}(u)=x_{i}$ for $1\leq i<h$ (if any
such exist) and $x_{h}=f^{h}(v_{1})$ where $v_{1}$ is a prefix of $u$.

(1) Suppose $\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$. Then
$u=u_{1}^{\prime}=u_{2}^{\prime}$ and the two equivalences $uz_{1}\sim z_{1}u$
and $uz_{3}\sim z_{3}u$ are with the same equivalence map. Since $z_{1}$ and
$z_{3}$ are of the same length, by Lemma 2.6 they have the same structure,
i.e., $z_{1}=x_{1}x_{2}\cdots x_{h}=z_{3}$.

(2) Suppose $\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$. Then
$u_{1}^{\prime}=u_{2}^{\prime}=u^{R}$. By Lemma 2.8, $|z_{1}|=|z_{3}|\geq|u|$
because $f(uz_{1})=z_{1}u$, $f(u^{R}z_{3})=z_{3}u^{R}$, and
$\Sigma[w]\cap\Sigma[u]=\emptyset$. Finally, observe that $|x_{h}|=|u|=\nu$.

Figure 2: Representation of $w_{1}$ and $w_{2}$ when
$\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$ are such that
$k_{1}<k_{2}\leq\ell_{1}<\ell_{2}$.

Since $u^{R}z_{3}\sim z_{3}u^{R}$, by Lemma 2.6,
$z_{3}=x_{1}^{R}x_{2}^{R}\cdots x_{h-1}^{R}x_{h}^{R}$ with $f^{i}(u)=x_{i}$
($1\leq i<h$) and $u=f^{h}(v_{2})f^{h+1}(v_{1})=v_{1}v_{2}$. It follows that
$f(x_{h-1}^{R}x_{h}^{R})=f^{h}(v_{2}^{R})f^{h}(v_{1}^{R})f^{h+1}(v_{1}^{R})=f^{h}(v_{2}^{R})x_{h}^{R}f^{h+1}(v_{1}^{R})$
is a suffix of $z_{3}u^{R}$ (Figure 2). If $|x_{h}|=|v_{1}|<|u|$,
$f^{h+1}(v_{1}^{R})$ is a proper suffix of $u^{R}$, and so
$\emptyset\neq\Sigma[x_{h}^{R}]\cap\Sigma[u]\subset\Sigma[z_{3}]\cap\Sigma[u]$,
contradictory to Definition 2.2. The above implies that
$h=|z_{1}|/|u|=(k_{2}-k_{1})/\nu$ is a positive integer.

###### Example 3.3

Let $w=12345677612345$ and consider the insertions $\rho(2,1,10)$ and
$\rho(2,6,15)$ into $w$; also let $w^{\prime}=123456652143$ with insertions
$\tau(2,1,9)$ and $\tau(2,5,13)$ into $w^{\prime}$.

$\displaystyle w_{1}$
$\displaystyle={\color[rgb]{1,0,0}\underline{89}}123456776{\color[rgb]{1,0,0}\underline{89}}12345\qquad\qquad
w_{1}^{\prime}={\color[rgb]{1,0,0}\underline{78}}12345665{\color[rgb]{1,0,0}\underline{87}}2143$
$\displaystyle w_{2}$
$\displaystyle=12345{\color[rgb]{1,0,0}\underline{89}}677612345{\color[rgb]{1,0,0}\underline{89}}\qquad\qquad
w_{2}^{\prime}=1234{\color[rgb]{1,0,0}\underline{78}}56652143{\color[rgb]{1,0,0}\underline{87}}$

Note that $w_{1}\sim w_{2}$ with $z_{1}=z_{3}=12345$, and $w_{1}^{\prime}\sim
w_{2}^{\prime}$ with $z_{1}z_{3}=12342143\sim\text{Int}(2,2)$.

Let $t\in\Sigma_{DOW}$ be in ascending order. We say that $t$ is a nested
sequence of repeat words if there exist integers $h,\nu\geq 1$ such that
$t=x_{1}x_{2}\cdots x_{h}x_{h}x_{h-1}\cdots x_{1}$, where $|x_{i}|=\nu$ for
all $i$; in this case we write $t=\text{Nes}(h,\nu)$. Clearly,
$x_{i}\in\Sigma_{SOW}$ for all $i$ and if $\nu=1$, then $\text{Nes}(h,1)$ is a
return word of size $h\geq 1$.

###### Proposition 3.4

If $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$ are nested insertions, that is
$k_{1}<k_{2}\leq\ell_{2}<\ell_{1}$, then $z_{1},z_{3}\in\Sigma_{SOW}$ are such
that

  1. (1)

If $\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$, then $z_{1}z_{3}$
is a return word in $w$.

  2. (2)

If $\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$, then
$z_{1}z_{3}\sim\text{Nes}(h,\nu)$ where $h=(k_{2}-k_{1})/\nu$ is a positive
integer.

###### Proof 3.5

We have that $w_{1}=uz_{1}z_{2}z_{3}u_{1}^{\prime}$ and
$w_{2}=z_{1}uz_{2}u_{2}^{\prime}z_{3}$. As in the proof of Proposition 3.1, it
must be that $z_{1}$ and $z_{3}$ are SOW by Lemma 2.6 because $u$ is SOW;
hence $|z_{1}|=|z_{3}|$. Also, $z_{1}=x_{1}x_{2}\cdots x_{h}$, where
$f^{i}(u)=x_{i}$ for $1\leq i<h$ (if any such exist) and $x_{h}=f^{h}(v_{1})$
where $v_{1}$ is a prefix of $u$.

(1) First, assume that $\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$
and $u_{1}^{\prime}=u_{2}^{\prime}=u^{R}$. Because $u^{R}z_{3}=f(z_{3}u^{R})$,
applying Lemma 2.6 symmetrically we have that
$z_{3}=x_{h}^{R}x_{h-1}^{R}\cdots x_{1}^{R}=z_{1}^{R}$.

Figure 3: Representation of $w_{1}$ and $w_{2}$ when
$\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$ are such that
$k_{1}<k_{2}\leq\ell_{2}<\ell_{1}$.

(2) Suppose $\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$ and
$u=u_{1}^{\prime}=u_{2}^{\prime}$. Because $f(uz_{1})=z_{1}u$ and
$f(z_{3}u)=uz_{3}$, by Lemma 2.8 we have $|u|\leq|z_{1}|=|z_{3}|$. Similarly
as in Proposition 3.1, we observe that $|x_{h}|=|u|$. Applying Lemma 2.6
symmetrically (Figure 3) $z_{3}=x_{h}x_{h-1}\cdots x_{2}x_{1}$. It follows
that
$f(x_{h}x_{h-1})=f^{h+1}(v_{1})f^{h}(v_{1})f^{h}(v_{2})=f^{h+1}(v_{1})x_{h}f^{h}(v_{2})$
is a prefix of $uz_{3}$ and if $|x_{h}|=|v_{1}|<|u|$, then $f^{h+1}(v_{1})$ is
a proper prefix of $u$, and so $\Sigma[x_{h}]\cap\Sigma[u]\neq\emptyset$. But
then
$\emptyset\neq\Sigma[x_{h}]\cap\Sigma[u]\subset\Sigma[z_{3}]\cap\Sigma[u]$,
contradictory to Definition 2.2. This implies that
$h=|z_{1}|/|u|=(k_{2}-k_{1})/\nu$ is a positive integer.

###### Example 3.6

Let $w=123456653412$ with the insertions $\rho(2,1,13)$ and $\rho(2,5,9)$ into
$w$; also let $w^{\prime}=12345677654321$ with the insertions $\tau(2,1,15)$
and $\tau(2,6,10)$ into $w^{\prime}$.

$\displaystyle w_{1}$
$\displaystyle={\color[rgb]{1,0,0}\underline{78}}123456653412{\color[rgb]{1,0,0}\underline{78}}\qquad\qquad
w_{1}^{\prime}={\color[rgb]{1,0,0}\underline{89}}12345677654321{\color[rgb]{1,0,0}\underline{98}}$
$\displaystyle w_{2}$
$\displaystyle=1234{\color[rgb]{1,0,0}\underline{78}}5665{\color[rgb]{1,0,0}\underline{78}}3412\qquad\qquad
w_{2}^{\prime}=12345{\color[rgb]{1,0,0}\underline{89}}6776{\color[rgb]{1,0,0}\underline{98}}54321$

Note that $w_{1}\sim w_{2}$ with $z_{1}z_{3}=12343412\sim\text{Nes}(2,2)$ and
$w_{1}^{\prime}\sim w_{2}^{\prime}$ with $z_{1}=12345$ and $z_{3}=z_{1}^{R}$.

###### Proposition 3.7

Let $\nu\in\mathbb{N}$, and suppose one of the following holds:

$(1)\quad t=12\cdots m12\cdots m$ $(3)\quad t=\text{Nes}(h,\nu)$ $(2)\quad
t=\text{Int}(h,\nu)$ $(4)\quad t=12\cdots mm\cdots 21$

for some $m\geq 1$ or $h\geq 1$, as appropriate. Then there exist two distinct
insertions, $\mathcal{I}_{1}(\nu,k_{1},\ell_{1})$ and
$\mathcal{I}_{2}(\nu,k_{2},\ell_{2})$, such that
$t\star\mathcal{I}_{1}(\nu,k_{1},\ell_{1})\sim
t\star\mathcal{I}_{2}(\nu,k_{2},\ell_{2})$. Moreover, the following table
holds for this pair of insertions (based on the corresponding case):

Interleaving Nested $\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$ (1)
(3) $\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$ (2) (4)

###### Proof 3.8

Let $t\in\Sigma_{DOW}$ correspond to one of the given cases with $|t|=n$. We
define a pair of distinct insertions into $t$ as follows so that the table
above holds:  $(1)$ \- $(2)$ $\mathcal{I}_{1}(\nu,1,\frac{n}{2}+1)$ and
$\mathcal{I}_{2}(\nu,\frac{n}{2}+1,n+1)$ $(3)$ \- $(4)$
$\mathcal{I}_{1}(\nu,1,n+1)$ and
$\mathcal{I}_{2}(\nu,\frac{n}{2}+1,\frac{n}{2}+1)$ In all cases, let
$uu^{\prime}\in\Sigma_{DOW}$ be inserted into $t$. Observe the following for
each case:

  1. (1)

$(u12\cdots m)(u12\cdots m)\sim(12\cdots mu)(12\cdots mu)$

  2. (2)

$(ux_{1}x_{2}\cdots x_{h})(u^{R}x_{1}^{R}x_{2}^{R}\cdots
x_{h}^{R})\sim(x_{1}x_{2}\cdots x_{h}u)(x_{1}^{R}x_{2}^{R}\cdots
x_{h}^{R}u^{R})$

  3. (3)

$(ux_{1}x_{2}\cdots x_{h})(x_{h}\cdots x_{2}x_{1}u)\sim(x_{1}x_{2}\cdots
x_{h}u)(ux_{h}\cdots x_{2}x_{1})$

  4. (4)

$(u12\cdots m)(m\cdots 21u^{R})\sim(12\cdots mu)(u^{R}m\cdots 21)$.

###  3.2 Sequential Insertions

In this section we consider the case when both indices of insertion
$\mathcal{I}_{1}$ into $w$ precede both indices of the insertion
$\mathcal{I}_{2}$ into $w$. First we observe the following lemma.

###### Lemma 3.9

If $k_{1}\leq\ell_{1}<k_{2}\leq\ell_{2}$, then $k_{2}-\ell_{1}\geq\nu$.

###### Proof 3.10

We have that $w_{1}=uz_{1}u_{1}^{\prime}z_{2}z_{3}$ and
$w_{2}=z_{1}z_{2}uz_{3}u_{2}^{\prime}$ with $f(w_{1})=w_{2}$.

(a)

(b)

Figure 4: Representation of $w_{1}$ and $w_{2}$ when
$k_{1}\leq\ell_{1}<k_{2}\leq\ell_{2}$ and $k_{2}-\ell_{1}<|u|$.

If $|u|>|z_{2}|=k_{2}-\ell_{1}$ then a prefix of $u_{1}^{\prime}$ maps to
suffix of $u$. Because a prefix of $u$ maps also to prefix of $z_{1}$,
$u_{1}^{\prime}\neq u$, i.e., $u_{1}^{\prime}=u^{R}$. Similarly, because a
suffix of $z_{2}z_{3}$ maps to a suffix of $u_{2}^{\prime}$, and a prefix of
$u^{R}$ maps to a suffix of $u$, it can’t be $u=u_{2}^{\prime}$ (symbols of
$w$ are disjoint with those in $u$). Hence, $u_{2}^{\prime}=u^{R}$. We can
exclude the situation in Figure 4a where $f(u)$ is a prefix of $z_{1}z_{2}$.
Thus it must be that $|z_{1}z_{2}|<|u|$, and a suffix of $u$, call it $v$,
maps to a prefix of $u$. Because $\Sigma[u]\cap\Sigma[z_{3}]=\emptyset$, it
must be that the prefix $v^{R}$ of $u^{R}$ maps into a suffix of $u$. Hence
the symbols in a prefix of $u$ equal symbols in a suffix of $u$, which can
only happen if $|z_{1}|=0$ contrary to the assumption that $k_{1}\neq k_{2}$.
Therefore $|u|\leq|z_{2}|$.

The structure of the words that allow distinct sequential insertions yielding
equivalent words is described with the following recursive construction.

###### Definition 3.11

Let $m\geq 0$ and $\nu,j\geq 1$ be integers and let $s_{0}=12\cdots m12\cdots
m$ (if $m=0$, $s_{0}=\epsilon$). Define
$s_{j}=s_{j-1}\star\rho(\nu,|s_{j-1}|-m+1,|s_{j-1}|+1)$ for $j=1,2,\dots$. The
word $s_{j}$ is called a $\rho$-tangled cord at level $j$, and is denoted
$s_{j}=T_{\rho}(\nu,m,j)$.

Let $\nu$ divide $m$ and $t_{0}=\text{Int}(h,\nu)$ where $h=\frac{m}{\nu}$ (if
$m=0$, $s_{0}=\epsilon$). Define
$t_{j}=t_{j-1}\star\tau(\nu,|s_{j-1}|-m+1,|s_{j-1}|+1)$ for $j=1,2,\dots$. The
word $t_{j}$ is called a $\tau$-tangled cord at level $j$, and is denoted
$t_{j}=T_{\tau}(\nu,m,j)$.

In both $\rho$\- and $\tau$-tangled cord words the insertion in the subsequent
word is performed at the end of the previous word (inserting $u^{\prime}$) and
$m$ symbols from the last symbol (inserting $u$).

###### Example 3.12

A level 3 $\rho$-tangled cord $w=T_{\rho}(2,1,3)$ is obtained in the following
way

$s_{0}=11\qquad
s_{1}=1{\color[rgb]{1,0,0}\underline{23}}1{\color[rgb]{1,0,0}\underline{23}}\qquad
s_{2}=12312{\color[rgb]{1,0,0}\underline{45}}3{\color[rgb]{1,0,0}\underline{45}}\qquad
s_{3}=123124534{\color[rgb]{1,0,0}\underline{67}}5{\color[rgb]{1,0,0}\underline{67}},$

and a level 2 $\tau$-tangled cord $w=T_{\tau}(2,4,2)$ is obtained with

$t_{0}=12342143\qquad
t_{1}=1234{\color[rgb]{1,0,0}\underline{56}}2143{\color[rgb]{1,0,0}\underline{65}}\qquad
t_{2}=12345621{\color[rgb]{1,0,0}\underline{78}}4365{\color[rgb]{1,0,0}\underline{87}}.$

Recall that $\text{Int}(h,1)$ for $h\geq 1$ is a repeat word of size $h$. It
follows that $T_{\rho}(1,m,j)=T_{\tau}(1,m,j)$ for $m\geq 0$ and $j\geq 1$.
Moreover, if $w=T_{\sigma}(\nu,0,j)$ for $\sigma\in\\{\rho,\tau\\}$ and
$\nu,j\geq 1$, then for $|v_{i}|=\nu$,

$w=\begin{cases}v_{1}v_{1}\cdots v_{j}v_{j}&\text{if }\sigma=\rho\\\
v_{1}v_{1}^{R}\cdots v_{j}v_{j}^{R}&\text{if }\sigma=\tau.\end{cases}$

As with interleaving and nested insertions, we will use the “image tracking”
method given by Lemmas 2.6 and 2.8 when considering sequential insertions.
Since both indices $k_{1}\leq\ell_{1}$ of the first insertion precede the
indices $k_{2}\leq\ell_{2}$ of the second, we must adapt this method to
describe the structure of $w$ in between $\ell_{1}$ and $k_{2}$. In Lemma
3.13, we begin by considering the case in which $k_{1}=\ell_{1}=1$.

###### Lemma 3.13

If $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$ are sequential insertions such that
$k_{1}=\ell_{1}<k_{2}\leq\ell_{2}$, then $k_{2}=\ell_{2}$ and
$k_{2}-\ell_{1}=2p\nu$ for some positive integer $p$. Moreover, if
$\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$
($\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$ resp.) then
$z_{1}z_{2}z_{3}\sim T_{\rho}(\nu,0,p)$ ($z_{1}z_{2}z_{3}\sim
T_{\tau}(\nu,0,p)$ resp.).

(alphsubfigure)  (alphsubfigure)

Figure 5: Representation of $w_{1}$ and $w_{2}$ when $|z_{1}|=0$ and $|z_{2}|$
is not an even multiple of $|u|$.

###### Proof 3.14

Suppose that $k_{1}=\ell_{1}<k_{2}\leq\ell_{2}$. The situation is such that
$w_{1}=uu^{\prime}z_{2}z_{3}$ and $w_{2}=z_{2}uz_{3}u^{\prime}$. Recall that
$|z_{2}|\geq|u|=\nu$ by Lemma 3.9. Assume that $|z_{2}|=k_{2}-\ell_{1}$ is not
an even multiple of $|u|$, and let $u=b_{1}\cdots b_{\nu}$. If
$\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$, then there exists a
positive integer $i$ such that either $f^{i}(b_{1})$ or $f^{i}(b_{\nu})$
belongs to $\Sigma[z_{2}]\cap\Sigma[u]$ (see Figure 5) contradicting the fact
that $\Sigma[w]\cap\Sigma[u]=\emptyset$. Similarly, if
$\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$, then there exists a
positive integer $i$ such that $f^{i}(b_{\nu})f^{i}(b_{\nu})\sqsubseteq u$, or
$f^{i}(b_{1})\in\Sigma[z_{2}]\cap\Sigma[u]$. Then either
$u\not\in\Sigma_{SOW}$ or $\Sigma[w]\cap\Sigma[u]\neq\emptyset$. It follows
that $k_{2}-\ell_{1}=|z_{2}|=2p|u|=2p\nu$ for some positive integer $p$ such
that $f^{p+1}(u)=u$.

We now apply Lemma 2.6 with $s=uu^{\prime}$, $z=z_{2}$, and
$t=u\operatorname{pre}(z_{3}u^{\prime},\nu)$. Note that $|z_{2}|=2p\nu$
implies that $s=uu^{\prime}=s_{1}$, and thus
$u\operatorname{pre}(z_{3}u^{\prime},\nu)=uu^{\prime}$ (i.e.,
$z_{3}=\epsilon$) because $\Sigma[u]\cap\Sigma[w]=\emptyset$. Thus
$z_{2}=y_{1}y_{1}\cdots y_{p}y_{p}$ ($z_{2}=y_{1}y_{1}^{R}\cdots
y_{p}y_{p}^{R}$ resp.) where $y_{i}=f^{i}(u)$ for $1\leq i\leq p$ in the case
of two repeat (return resp.) insertions. That is to say, $z_{2}$ is equivalent
to $T_{\rho}(\nu,0,p)$ ($T_{\tau}(\nu,0,p)$ resp.).

###### Proposition 3.15

If $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$ are sequential insertions such that
$k_{1}\leq\ell_{1}<k_{2}\leq\ell_{2}$, then $k_{2}-\ell_{1}=2p\nu$ for some
positive integer $p$ and $|z_{1}|=|z_{3}|=q$. Moreover, if
$\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$ then
$z_{1}z_{2}z_{3}\sim T_{\rho}(\nu,q,p)$, while if
$\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$ then
$z_{1}z_{2}z_{3}\sim T_{\tau}(\nu,q,p)$ where $\nu$ divides $q$.

###### Proof 3.16

The situation $k_{1}=\ell_{1}$ follows from Lemma 3.13, so we assume that
$k_{1}<\ell_{1}<k_{2}\leq\ell_{2}$ with $w_{1}=uz_{1}u^{\prime}z_{2}z_{3}$,
$w_{2}=z_{1}z_{2}uz_{3}u^{\prime}$, and recall that $|z_{2}|\geq|u|=\nu$ by
Lemma 3.9.

(1) Suppose $\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$; we
consider two cases: (1.a) $0<|z_{1}|<|u|$ and (1.b) $|z_{1}|\geq|u|$.

(1.a) Let $0<|z_{1}|<|u|$, write $x_{1}=z_{1}$, and let $y_{1}$ be the prefix
of $z_{2}$ such that $|y_{1}|=|u|$; note that $y_{1}$ exists by Lemma 3.9 and
that $uz_{1}\sim z_{1}y_{1}$. Lemma 2.6 implies $u_{1}=v_{1}v_{2}$ with
$v_{1}\neq\epsilon$, $z_{1}=f(v_{1})=x_{1}$, and
$y_{1}=f(v_{2})f^{2}(v_{1})=f(v_{2})f(x_{1})$.

Write $v=f(v_{2})$ so that $y_{1}=vf(x_{1})$. Then,
$f(uy_{1})=x_{1}vf(y_{1})=x_{1}vf(v)f^{2}(x_{1})$. Note that
$x_{1}v\sqsubseteq z_{2}$, which implies that $y_{1}x_{1}v$ is a prefix of
$z_{2}$ of length $2|u|$. Moreover, $f(y_{1})$ cannot have a proper factor in
common with $u$, otherwise $f(x_{1})\cap u\neq\emptyset$ contradicting the
fact that $\Sigma[z_{2}]\cap\Sigma[u]=\emptyset$. Thus, there are two
possibilities: either $f(y_{1})=u$ or $f(y_{1})$ is a proper factor of
$z_{2}$. In the first situation, $z_{2}=y_{1}x_{1}v=vf(x_{1})x_{1}v$, and thus
$|z_{2}|=2|u|=2\nu$, with $f(v)$ a prefix of $u$; thus, $z_{3}=f(x_{1})$ and
$|z_{3}|=|z_{1}|$. Then
$z_{1}z_{2}z_{3}=x_{1}y_{1}x_{1}vf(x_{1})=x_{1}y_{1}x_{1}y_{1}$. Observe that
$z_{1}z_{2}z_{3}\sim T_{\rho}(\nu,\ell_{1}-k_{1},1)$ and in particular
$s_{0}\sim x_{1}x_{1}$ (where $s_{0}$ starts the induction of the tangled cord
as in Definition 3.11).

Figure 6: Representation of $w_{1}$ and $w_{2}$ when $|z_{1}|<|u|$ and
$f(y_{1})$ is a proper factor of $z_{2}$.

In the second situation, we set $y_{2}=f(y_{1})=f(v)f^{2}(x_{1})\sqsubseteq
z_{2}$. Similarly as above, we have that $y_{1}x_{1}vy_{2}f(x_{1})f(v)$ is a
prefix of $z_{2}$ of length $4|u|$, and either $f(y_{2})=u$ or $f(y_{2})$ is a
proper factor of $z_{2}$. Inductively, there is $p\geq 1$ such that
$y_{p}=f^{p-1}(v)f^{p}(x_{1})$ and $f(y_{p})=u$ (see Figure 6). It follows
that

$z_{2}=y_{1}x_{1}vy_{2}f(x_{1})f(v)\cdots y_{p}f^{p-1}(x_{1})f^{p-1}(v)\text{
with }p=\frac{k_{2}-\ell_{1}}{2\nu}.$

Because $f^{p}(v)$ is a prefix of $u$, $z_{3}=f^{p}(x_{1})$ and
$|z_{3}|=|z_{1}|$. As a consequence,

$z_{1}z_{2}z_{3}=x_{1}y_{1}x_{1}vy_{2}f(x_{1})f(v)\cdots
y_{p}f^{p-1}(x_{1})f^{p-1}(v)f^{p}(x_{1})=s_{p}$

for $p\geq 1$. Observe that $z_{1}z_{2}z_{3}\sim
T_{\rho}(\nu,\ell_{1}-k_{1},p)$ because $y_{i}=f^{i-1}(v)f^{i}(x_{1})$ for
$1\leq i\leq p$. In fact, taking $s_{0}\sim x_{1}x_{1}$ we have

$s_{p}=x_{1}y_{1}x_{1}vy_{2}f(x_{1})f(v)\cdots y_{p}f^{p-1}(x_{1})y_{p}\sim
s_{p-1}\star\rho(\nu,|s_{p-1}|-|z_{1}|+1,|s_{p-1}|+1)\sim
T_{\rho}(\nu,|z_{1}|,p).$

(1.b) Let $|z_{1}|\geq|u|=\nu$, and set as above $y_{1}$ to be the prefix of
$z_{2}$ such that $|y_{1}|=|u|$. Because $uz_{1}\sim z_{1}y_{1}$, by Lemma 2.6
we have that $u=v_{1}v_{2}$ with $v_{1}\neq\epsilon$, $z_{1}=x_{1}x_{2}\cdots
x_{h}$, where $f^{i}(u)=x_{i}$ for $1\leq i<h$ (if any such exist) with
$x_{h}=f^{h}(v_{1})$, and
$y_{1}=f^{h}(v_{2})f^{h+1}(v_{1})=f^{h}(v_{2})f(x_{h})$. Write
$v=f^{h}(v_{2})$ so that $y_{1}=vf(x_{h})$; if $v_{2}=\epsilon$, then
$v=\epsilon$ and $y_{1}=f(x_{h})$ (see Figure 7). Similarly as in the case
(1.a), using the same notation, it implies that there is a positive integer
$p\geq 1$ such that $f(y_{p})=u$.

Figure 7: Representation of $w_{1}$ and $w_{2}$ when $|z_{1}|\geq|u|$ and
$f(y_{1})$ is a proper factor of $z_{2}$. If $p<h$, then $s=x_{p}$; otherwise
$s=f^{p-h}(x_{h}v)$.

Suppose first $p<h$; then $z_{2}=y_{1}x_{1}\cdots y_{p}x_{p}$, indicating
$p=\frac{k_{2}-\ell_{1}}{2\nu}$ because $|y_{i}|=|x_{i}|$ for $1\leq i\leq
p<h$ (see Figure 7 where $s=x_{p}$). Because $y_{p}x_{p}$ is a suffix of
$z_{2}$ and $f(y_{p}x_{p})=ux_{p+1}$, it follows that $x_{p+1}\cdots x_{h}$ is
a prefix of $z_{3}$. Note that $f(x_{h-1}x_{h})=x_{h}vf(x_{h})=x_{h}y_{1}$; so
$x_{p+1}\cdots x_{h}y_{1}$ is a prefix of $z_{3}$. Inductively, we have that
$z_{3}=x_{p+1}\cdots x_{h}y_{1}\cdots y_{p}$ because $f^{-1}(u)=y_{p}$, and so
$|z_{3}|=|z_{1}|$ since $|y_{i}|=|u|=\nu$ for all $i$. Hence,

$z_{1}z_{2}z_{3}=x_{1}\cdots x_{h}y_{1}x_{1}\cdots y_{p}x_{p}x_{p+1}\cdots
x_{h}y_{1}\cdots y_{p}$

for $1\leq p<h$. Observe that $z_{1}z_{2}z_{3}\sim
T_{\rho}(\nu,\ell_{1}-k_{1},p)$ in this case (i.e., when $1\leq p<h$). Indeed,
following Definition 3.11, taking $s_{0}\sim x_{1}\cdots x_{h}x_{1}\cdots
x_{h}$ we have that

$\displaystyle s_{1}$ $\displaystyle\sim x_{1}\cdots x_{h}y_{1}x_{1}\cdots
x_{h}y_{1}$ $\displaystyle s_{2}$ $\displaystyle\sim x_{1}\cdots
x_{h}y_{1}x_{1}y_{2}x_{2}\cdots x_{h}y_{1}y_{2}$ $\displaystyle\vdots$
$\displaystyle s_{p}$ $\displaystyle\sim x_{1}\cdots
x_{h}y_{1}x_{1}y_{2}x_{2}\cdots y_{p}x_{p}x_{p+1}\cdots x_{h}y_{1}\cdots
y_{p}.$

Now suppose that $p\geq h$, then

$z_{2}=y_{1}x_{1}y_{2}x_{2}\cdots
x_{h-1}y_{h}x_{h}vy_{h+1}f(x_{h})f(v)y_{h+2}\cdots
y_{p}f^{p-h}(x_{h})f^{p-h}(v),$

where $y_{i}=f^{i-1}(v)f^{i}(x_{h})$ for $1\leq i\leq p$ (see Figure 7, where
$s=f^{p-h}(x_{h}v)$). Because $x_{h}v$ has length $|u|=\nu$, we again obtain
that $|z_{2}|$ is a multiple of $2|u|=2\nu$; in particular $|z_{2}|=2p\nu$
where $p=\frac{k_{2}-\ell_{1}}{2\nu}$. Because $f^{-1}(u)=y_{p}$, we have that

$z_{3}=f^{p-h+1}(x_{h})\underbrace{f^{p-h+1}(v)f^{p-h+2}(x_{h})}_{y_{p-h+2}}\underbrace{f^{p-h+2}(v)f^{p-h+3}(x_{h})}_{y_{p-h+3}}\cdots\underbrace{f^{p-1}(v)f^{p}(x_{h})}_{y_{p}}.$

Note that $|z_{3}|=|z_{1}|$ since $|y_{i}|=|u|=\nu$ for all $i$. We observe
that $z_{1}z_{2}z_{3}\sim T_{\rho}(\nu,\ell_{1}-k_{1},p)$ in the case $p\geq
h$ as well. Indeed, taking $s_{0},\ldots,s_{p}$ as in Definition 3.11:

$\displaystyle s_{0}$ $\displaystyle\sim x_{1}\cdots x_{h}x_{1}\cdots x_{h}$
$\displaystyle s_{1}$ $\displaystyle\sim x_{1}\cdots x_{h}y_{1}x_{1}\cdots
x_{h}y_{1}$ $\displaystyle\vdots$ $\displaystyle s_{h}$ $\displaystyle\sim
x_{1}\cdots x_{h}y_{1}x_{1}y_{2}x_{2}\cdots y_{h}x_{h}y_{1}y_{2}\cdots y_{h}$
$\displaystyle s_{h+1}$ $\displaystyle\sim x_{1}\cdots
x_{h}y_{1}x_{1}y_{2}x_{2}\cdots y_{h}x_{h}vy_{h+1}f(x_{h})y_{2}\cdots
y_{h}y_{h+1}$ $\displaystyle\vdots$ $\displaystyle s_{p}$ $\displaystyle\sim
z_{1}z_{2}z_{3}.$

(2) Suppose that $\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$.
First, observe that $|z_{1}|\geq|u|$. On the contrary, suppose that
$0<|z_{1}|<|u_{1}|$. Similarly, and with the same notation, as in case (1.a),
we have that

$z_{2}=y_{1}v^{R}x_{1}^{R}y_{2}f(v^{R})f(x_{1}^{R})\cdots
y_{p}f^{p-1}(v^{R})f^{p-1}(x_{1}^{R})\text{ with
}p=\frac{k_{2}-\ell_{1}}{2|u|},$

where $x_{1}=z_{1}$, $v$ is the nonempty prefix of $z_{2}$ such that
$x_{1}v=f(u)$, $y_{i}=f^{i-1}(v)f^{i}(x_{1})$ for $1\leq i\leq p$ and
$f(y_{p})=f(f^{p-1}(v)f^{p}(x_{1}))=f^{p}(v)f^{p+1}(x_{1})=u$. Note that
$f^{p}(v)$ is a proper prefix of $u$, hence $f^{p}(v)^{R}$ is a proper suffix
of $u^{R}$. Considering the suffix $y_{p}f^{p-1}(v^{R})f^{p-1}(x_{1}^{R})$ of
$z_{2}$, we have that
$f(y_{p}f^{p-1}(v^{R}))=f(y_{p})f^{p}(v^{R})=uf^{p}(v)^{R}\sqsubseteq w_{2}$
(see Figure 6). But $uf^{p}(v)^{R}\sqsubseteq w_{2}$ and $u^{R}\sqsubseteq
w_{2}$ contradicts the fact that $w_{2}$ is a DOW; thus $|z_{1}|\geq|u|$.

In the rest of the proof we use similar arguments to those used in case (1.b)
for repeat insertions (with the same notation).

If $p<h$, then $z_{2}=y_{1}x_{1}^{R}\cdots y_{p}x_{p}^{R}$ with $f(y_{p})=u$,
which implies that $p=\frac{k_{2}-\ell_{1}}{2\nu}$ because $|y_{i}|=|x_{i}|$
for $1\leq i\leq p<h$. It follows that

$x_{p+1}^{R}\cdots x_{h-1}^{R}v^{R}x_{h}^{R}f(v^{R})f(x_{h}^{R})\cdots
f^{p-1}(v^{R})f^{p-1}(x_{h}^{R})f^{p}(x_{h}^{R})$

is a prefix of $z_{3}$ (see Figure 7). Assume that $\nu$ does not divide
$|z_{1}|=\ell_{1}-k_{1}$ in this situation; then $v\neq\epsilon$. Since
$f(y_{p})=f(f^{p-1}(v)f^{p}(x_{h}))=f^{p}(v)f^{p+1}(x_{h})=u$, we have that
$f^{p}(v)^{R}$ is a proper suffix of $u^{R}$ and $f^{p+1}(x_{h})^{R}$ is a
proper prefix of $u^{R}$. But then
$f(f^{p-1}(v^{R})f^{p-1}(x_{h}^{R})f^{p}(x_{h}^{R}))=f^{p}(v^{R})f^{p}(x_{h}^{R})f^{p+1}(x_{h}^{R})\sqsubseteq
w_{2}$ with $u^{R}\sqsubseteq w_{2}$ contradicts the fact that $w_{2}$ is a
DOW. Thus,

$p<h=\left\lceil\frac{\ell_{1}-k_{1}}{\nu}\right\rceil=\frac{\ell_{1}-k_{1}}{\nu}.$

Then $|z_{1}|=h\nu$, $v=\epsilon$, $|x_{h}|=\nu$, and $y_{i}=f^{i}(x_{h})$ for
$1\leq i\leq p$. Because $f^{-1}(u^{R})=y_{p}^{R}$, it follows that
$z_{3}=x_{p+1}^{R}\cdots x_{h}^{R}f(x_{h}^{R})\cdots
f^{p}(x_{h}^{R})=x_{p+1}^{R}\cdots x_{h}^{R}y_{1}^{R}\cdots y_{p}^{R}$, and so
$|z_{3}|=|z_{1}|=h\nu$ since $|y_{i}|=|u|$ for all $i$. Hence,

$z_{1}z_{2}z_{3}=x_{1}\cdots x_{h}y_{1}x_{1}^{R}\cdots
y_{p}x_{p}^{R}x_{p+1}^{R}\cdots x_{h}^{R}y_{1}^{R}\cdots y_{p}^{R}$

for $1\leq p<h$. Similarly as in case (1.b) we observe that
$z_{1}z_{2}z_{3}\sim T_{\tau}(\nu,\ell_{1}-k_{1},p)$ in this situation.

In case $p\geq h$ we have that

$z_{2}=y_{1}x_{1}^{R}y_{2}x_{2}^{R}\cdots
x_{h-1}^{R}y_{h}v^{R}x_{h}^{R}y_{h+1}f(v^{R})f(x_{h}^{R})y_{h+2}\cdots
y_{p}f^{p-h}(v^{R})f^{p-h}(x_{h}^{R}),$

where $y_{i}=f^{i-1}(v)f^{i}(x_{h})$ for $1\leq i\leq p$ and $f(y_{p})=u$.
Because $|v^{R}x_{h}^{R}|=|u|$, it follows that $|z_{2}|$ is a multiple of
$2|u|$; in particular $|z_{2}|=2p\nu$, where $p=\frac{k_{2}-\ell_{1}}{2\nu}$.
Moreover, we have that

$f^{p-h+1}(v^{R})f^{p-h+1}(x_{h}^{R})\cdots
f^{p-1}(v^{R})f^{p-1}(x_{h}^{R})f^{p}(x_{h}^{R})$

is a prefix of $z_{3}$ (see Figure 7). Similarly as above, $|u|=\nu$ divides
$|z_{1}|=\ell_{1}-k_{1}$. Thus $h=\frac{\ell_{1}-k_{1}}{\nu}$; so
$|z_{1}|=h\nu$, $v=\epsilon$, $|x_{h}|=|u|$, and $y_{i}=f^{i}(x_{h})$ for
$1\leq i\leq p$. It then follows that

$\displaystyle z_{2}$ $\displaystyle=y_{1}x_{1}^{R}y_{2}x_{2}^{R}\cdots
x_{h-1}^{R}y_{h}x_{h}^{R}y_{h+1}f(x_{h}^{R})y_{h+2}\cdots
y_{p}f^{p-h}(x_{h}^{R})$ $\displaystyle=y_{1}x_{1}^{R}y_{2}x_{2}^{R}\cdots
x_{h-1}^{R}y_{h}x_{h}^{R}y_{h+1}y_{1}^{R}y_{h+2}\cdots y_{p}y_{p-h}^{R}$
$\displaystyle z_{3}$
$\displaystyle=f^{p-h+1}(x_{h}^{R})f^{p-h+2}(x_{h}^{R})\cdots
f^{p}(x_{h}^{R})=y_{p-h+1}^{R}y_{p-h+2}^{R}\cdots y_{p}^{R}$

because $f^{-1}(u^{R})=y_{p}^{R}$. Note that $|z_{3}|=|z_{1}|=h\nu$ since
$|y_{i}|=|u|$ for all $i$. Finally we observe that $z_{1}z_{2}z_{3}\sim
T_{\tau}(\nu,\ell_{1}-k_{1},p)$.

###### Example 3.17

Let $w=12312453467567=T_{\rho}(2,1,3)$ and consider the insertions
$\rho(2,1,2)$ and $\rho(2,14,15)$ into $w$; also, let
$w^{\prime}=123456214365=T_{\tau}(2,4,1)$ and consider the insertions
$\tau(2,1,5)$ and $\tau(2,9,13)$ into $w^{\prime}$. Then

$\displaystyle w_{1}$
$\displaystyle={\color[rgb]{1,0,0}\underline{89}}1{\color[rgb]{1,0,0}\underline{89}}2312453467567\qquad\qquad
w_{1}^{\prime}={\color[rgb]{1,0,0}\underline{78}}1234{\color[rgb]{1,0,0}\underline{87}}56214365$
$\displaystyle w_{2}$
$\displaystyle=1231245346756{\color[rgb]{1,0,0}\underline{89}}7{\color[rgb]{1,0,0}\underline{89}}\qquad\qquad
w_{2}^{\prime}=12345621{\color[rgb]{1,0,0}\underline{78}}4365{\color[rgb]{1,0,0}\underline{87}}$

Note that $w_{1}\sim w_{2}$ and $w_{1}^{\prime}\sim w_{2}^{\prime}$.

###### Corollary 3.18

For every $T_{\sigma}(\nu,m,j)$, we have that
$T_{\sigma}(\nu,m,j)\star\mathcal{I}(\nu,1,m+1)\sim T_{\sigma}(\nu,m,j+1)$
where $\sigma\in\\{\rho,\tau\\}$ and $\mathcal{I}\in\operatorname{Rep}$
($\mathcal{I}\in\operatorname{Ret}$ resp.) if $\sigma=\rho$ ($\sigma=\tau$
resp.).

###### Proof 3.19

The result follows by using similar arguments as in the proofs of Lemma 3.13
and Proposition 3.15.

A DOW is a _palindrome_ if it is equivalent to its reverse [3]. Let $m\geq 1$
be an integer; observe that the repeat word $12\cdots m12\cdots m$ and the
return word $12\cdots mm\cdots 21$ are palindromes. Let $h,\nu\geq 1$. Observe
that $\text{Int}(h,\nu)=x_{1}\cdots x_{h}x_{1}^{R}\cdots x_{h}^{R}$ is a
palindrome. Indeed, consider $f:\Sigma\to\Sigma$ such that
$f(x_{i})=x_{h-i+1}$ for all $i$. Similarly, $\text{Nes}(h,\nu)=x_{1}\cdots
x_{h}x_{h}\cdots x_{1}$ is a palindrome; consider $f:\Sigma\to\Sigma$ such
that $f(x_{i})=x_{i}^{R}$ for all $i$.

###### Proposition 3.20

Every $T_{\sigma}(\nu,m,j)$ is a palindrome where $\sigma\in\\{\rho,\tau\\}$.

###### Proof 3.21

Let $\nu\geq 1$, $m\geq 0$, and $\sigma\in\\{\rho,\tau\\}$. We show that the
result holds by inducting on $j$. Note that $T_{\rho}(\nu,m,1)$ is a repeat
word of size $m+\nu$ and $T_{\tau}(\nu,m,1)=\text{Int}(\frac{m}{\nu}+1,\nu)$.
In either case, $T_{\sigma}(\nu,m,1)$ is a palindrome. Next, suppose that
$w=T_{\sigma}(\nu,m,j-1)$ is a palindrome for $j>1$, and let $n=|w|$. The
following shows that $T_{\rho}(\nu,m,j)$ is a palindrome:

$T_{\rho}(\nu,m,j)$ $\sim w\star\rho(\nu,1,m+1)$ (by Corollary 3.18) $\sim
w^{R}\star\rho(\nu,1,m+1)$ (because $w\sim w^{R}$)
$\sim\left(w\star\rho(\nu,n-m+1,n+1)\right)^{R}$
$\sim\left(T_{\rho}(\nu,m,j)\right)^{R}$ (by the definition of
$T_{\rho}(\nu,m,j)$).

The case for $T_{\tau}(\nu,m,j)$ follows equivalently.

Observe that there exist words that are palindromes but are neither
$\rho$-tangled cords nor $\tau$-tangled cords, like $12324143$. However, note
that $12324143$ is equivalent to a cyclic permutation of the tangled cord
$T_{\rho}(1,1,3)$.

###### Definition 3.22

Let $w\in\Sigma_{DOW}$, and let $uu^{\prime}$ be a repeat (return resp.) word
in $w$. We say that $uu^{\prime}$ is a maximal repeat (return resp.) word in
$w$ if for any repeat (return resp.) word $vv^{\prime}$ in $w$ such that
$u\sqsubseteq v$, we have that $u=v$.

###### Example 3.23

Consider $T_{\mathcal{\rho}}(2,3,2)=s_{2}$ and
$T_{\mathcal{\tau}}(2,4,1)=s_{1}^{\prime}$.

$s_{0}=123123$ $s_{0}^{\prime}=12342143$
$s_{1}=s_{0}\star\rho(2,4,7)=123{\color[rgb]{1,0,0}\underline{45}}123{\color[rgb]{1,0,0}\underline{45}}$
$s_{1}^{\prime}=s_{0}^{\prime}\star\tau(2,5,9)=1234{\color[rgb]{1,0,0}\underline{56}}2143{\color[rgb]{1,0,0}\underline{65}}$
$s_{2}=s_{1}\star\rho(2,8,11)=1234512{\color[rgb]{1,0,0}\underline{67}}345{\color[rgb]{1,0,0}\underline{67}}$

Note that $T_{\mathcal{\rho}}(2,3,2)$ contains four maximal repeat words:
$33$, $1212$, $4545$, and $6767$. On the other hand,
$T_{\mathcal{\tau}}(2,4,1)$ contains three maximal return words: $1221$,
$3443$ and $5665$.

As the previous example suggests, every $\tau$-tangled cord ends with a
maximal return word of size $\nu$. The same property holds for $\rho$-tangled
cord whenever $j>1$.

###### Proposition 3.24

The following hold.

  1. (1)

If $T_{\mathcal{\rho}}(\nu_{1},m_{1},j_{1})\sim
T_{\mathcal{\rho}}(\nu_{2},m_{2},j_{2})$ and $j_{1}>1$, then
$(\nu_{1},m_{1},j_{1})=(\nu_{2},m_{2},j_{2})$.

  2. (2)

If $T_{\mathcal{\tau}}(\nu_{1},m_{1},j_{1})\sim
T_{\mathcal{\tau}}(\nu_{2},m_{2},j_{2})$, then
$(\nu_{1},m_{1},j_{1})=(\nu_{2},m_{2},j_{2})$.

###### Proof 3.25

(1) Let $T_{\mathcal{\rho}}(\nu_{1},m_{1},j_{1})$ and
$T_{\mathcal{\rho}}(\nu_{2},m_{2},j_{2})$ be as given with $j_{1}>1$. Because
these DOWs are equivalent and thus have equal lengths, note that
$m_{1}+\nu_{1}j_{1}=m_{2}+\nu_{2}j_{2}$. Moreover,
$T_{\mathcal{\rho}}(\nu_{1},m_{1},j_{1})$ ends with a maximal repeat word of
size $\nu_{1}$. If $j_{2}=1$, then $T_{\mathcal{\rho}}(\nu_{2},m_{2},j_{2})$
is a repeat word of size $m_{2}+\nu_{2}$ which cannot be equivalent to
$T_{\mathcal{\rho}}(\nu_{1},m_{1},j_{1})$; thus, $j_{2}>1$. It follows that
$T_{\mathcal{\rho}}(\nu_{2},m_{2},j_{2})$ ends with a maximal repeat word of
size $\nu_{2}$; so $\nu_{1}=\nu_{2}$. By setting $\nu=\nu_{1}$, we get
$|m_{1}-m_{2}|=\nu|j_{1}-j_{2}|$. We now distinguish between the following two
cases:

(i) $m_{1},m_{2}>0$ (ii) $m_{1}=0$ or $m_{2}=0$.

(1.i) Suppose $m_{1},m_{2}>0$. Then
$\operatorname{pre}(T_{\mathcal{\rho}}(\nu,m_{1},j_{1}),m_{1}+\nu+1)=12\cdots
m_{1}v_{1}1$ and
$\operatorname{pre}(T_{\mathcal{\rho}}(\nu,m_{2},j_{2}),m_{2}+\nu+1)=12\cdots
m_{2}\hat{v}_{1}1$, with $|v_{1}|=|\hat{v}_{1}|=\nu$. It follows that
$m_{1}=m_{2}$ because $T_{\mathcal{\rho}}(\nu,m_{1},j_{1})\sim
T_{\mathcal{\rho}}(\nu,m_{2},j_{2})$.

(1.ii) Suppose that $m_{1}=0$ but $m_{2}\neq 0$. Then
$\operatorname{pre}(T_{\mathcal{\rho}}(\nu,m_{1},j_{1}),2\nu)=v_{1}v_{1}$
while
$\operatorname{pre}(T_{\mathcal{\rho}}(\nu,m_{2},j_{2}),m_{2}+\nu)=12\cdots
m_{2}\hat{v}_{1}$, with $|v_{1}|=|\hat{v}_{1}|=\nu$. But this contradicts the
assumption that $T_{\mathcal{\tau}}(\nu,m_{1},j_{1})\sim
T_{\mathcal{\tau}}(\nu,m_{2},j_{2})$. So $m_{1}=0$ implies $m_{2}=0$. The same
argument can be applied to show that $m_{2}=0$ implies $m_{1}=0$.

In both cases above, $m_{1}=m_{2}$ and so $j_{1}=j_{2}$. We can apply a
similar argument to prove (2).

###  3.3 Repeat vs Return Insertions

In this section we show that two distinct nontrivial insertions which yield
equivalent words must both be of the same type, that is, both repeat
insertions or both return insertions. We note that the proof for this result
follows the same methodology, notation, and very similar arguments to those
presented in Sections 3.1 and 3.2.

###### Theorem 3.26

Let $\mathcal{I}_{1}(\nu,k_{1},\ell_{1})$ and
$\mathcal{I}_{2}(\nu,k_{2},\ell_{2})$ be two distinct nontrivial insertions
into $w\in\Sigma_{DOW}$. If
$w_{1}=w\star\mathcal{I}_{1}(\nu,k_{1},\ell_{1})\sim
w\star\mathcal{I}_{2}(\nu,k_{2},\ell_{2})=w_{2}$, then either
$\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$ or
$\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$.

###### Proof 3.27

Let $w=z_{1}z_{2}z_{3}$, as in Sections 3.1 and 3.2 be of length $n$, and
$w_{1}\sim w_{2}$ with equivalence map $f$. Because $\mathcal{I}_{1}$ and
$\mathcal{I}_{2}$ are nontrivial, $\nu\geq 2$. We prove the result by
contradiction.

(a)

(b)

Figure 8: Representation of $w_{1}$ and $w_{2}$ when
$\mathcal{I}_{1}\in\operatorname{Rep}$,
$\mathcal{I}_{2}\in\operatorname{Ret}$; (a) $0<|z_{1}|<|u|$, or (b)
$|z_{1}|\geq|u|$.

Case of interleaving or nested insertions. Suppose
$k_{1}<k_{2}\leq\ell_{1}<\ell_{2}$ and without loss of generality we assume
that $\mathcal{I}_{1}\in\operatorname{Rep}$ and
$\mathcal{I}_{2}\in\operatorname{Ret}$. If $|z_{1}|<|u|$, then $f(u)\cap
u\neq\emptyset$ (see Figure 8a). Because $uu$ is a repeat word in $w_{1}$,
$f(u)f(u)$ is a repeat word in $w_{2}$; so by Lemma 2.10 we have $|f(u)|=1$ or
$|u|=1$ because $uu^{R}$ is return word in $w_{2}$. Thus $|u|=1$ implying that
the insertions must be trivial. If $|z_{1}|\geq|u|$, then observe that $f(u)$
is a prefix of $z_{1}$. But then $f^{2}(u)$ is either a factor of $z_{1}$ or
$f^{2}(u)\cap u\neq\emptyset$. Inductively, for some $h>1$ we have that
$f^{i}(u)$ is a factor of $z_{1}$ for $1\leq i<h$ and $f^{h}(u)\cap
u\neq\emptyset$ (see Figure 8b). Consider the second occurrence of $u$ in
$w_{1}$; we have that $f^{i}(u)$ is a factor of $z_{3}$ for $1\leq i<h$ and
$f^{h}(u)\cap u^{R}\neq\emptyset$. But $f^{i}(u)f^{i}(u)$ is a repeat word in
$w_{2}$ of size $|u|$ for every $1\leq i\leq h$; by Lemma 2.10, $f^{h}(u)\cap
u\neq\emptyset$ implies that $|f^{h}(u)|=1$ or $|u|=1$ because $uu^{R}$ is a
return word in $w_{2}$. Thus, $|u|=1$ contradicting $\nu\geq 2$. The case of
nested insertions, that is, $k_{1}<k_{2}\leq\ell_{2}<\ell_{1}$, follows by
similar arguments.

Sequential insertions. Suppose that $k_{1}\leq\ell_{1}<k_{2}\leq\ell_{2}$ and
without loss of generality assume that $\mathcal{I}_{1}\in\operatorname{Rep}$
and $\mathcal{I}_{2}\in\operatorname{Ret}$. As in Lemma 3.13 and Proposition
3.15, we consider the cases: (I) $k_{1}=\ell_{1}$ and (II)
$k_{1}\neq\ell_{1}$. In both cases recall that $|z_{2}|\geq|u|$ by Lemma 3.9.

Figure 9: Representation of $w_{1}$ and $w_{2}$ when
$\mathcal{I}_{1}\in\operatorname{Rep}$,
$\mathcal{I}_{2}\in\operatorname{Ret}$, and $k_{1}=\ell_{1}$.

(I) Let $k_{1}=\ell_{1}$; i.e., $z_{1}=\epsilon$. As in proof of Lemma 3.13
for repeat insertions, we have that $z_{2}=y_{1}y_{1}\cdots y_{p}y_{p}$ where
$y_{i}=f^{i}(u)$ for $1\leq i\leq p$, $f(y_{p})=u$ and
$p=\frac{k_{2}-\ell_{1}}{2\nu}$ (see Figure 9). It follows that
$f(y_{p})f(y_{p})$ is a repeat word in $w_{2}$ of size $|u|$. Then, by Lemma
2.10, $f(y_{p})=u$ implies that $|f(y_{p})|=1$ or $|u|=1$, and the insertions
must be trivial.

(II) Let $k_{1}\neq\ell_{1}$, so that $z_{1}\neq\epsilon$. If $0<|z_{1}|<|u|$,
by the proof of Proposition 3.15 for case (1.a), we have that

$z_{2}=y_{1}x_{1}vy_{2}f(x_{1})f(v)\cdots y_{p}f^{p-1}(x_{1})f^{p-1}(v)\text{
with }p=\frac{k_{2}-\ell_{1}}{2\nu},$

where $x_{1}=z_{1}$, $v$ is the nonempty prefix of $z_{2}$ such that
$x_{1}v=f(u)$, $y_{i}=f^{i-1}(v)f^{i}(x_{1})$ for $1\leq i\leq p$ and
$f(y_{p})=f(f^{p-1}(v)f^{p}(x_{1}))=f^{p}(v)f^{p+1}(x_{1})=u$ (see Figure 6).
It follows that $f(y_{p}f^{p-1}(x_{1})f^{p-1}(v))=uf^{p}(x_{1})f^{p}(v)$,
where $f^{p}(x_{1})$ is a proper suffix of $y_{p}$ and $f^{p}(v)$ is a proper
prefix of $u$. Because $u^{R}\sqsubseteq w_{2}$, this contradicts the fact
that $w_{2}$ is a DOW.

So assume that $|z_{1}|\geq|u|$, and let $y_{1}$ be the prefix of $z_{2}$ such
that $|y_{1}|=|u|$ (exists by Lemma 3.9). By applying arguments similar to the
ones used in the proof of Proposition 3.15 for case (1.b) (with the same
notation), we obtain that there exists a positive integer $p\geq 1$ such that
$f(y_{p})=u$. If $p<h$, then $z_{2}=y_{1}x_{1}\cdots y_{p}x_{p}$ and
$z_{3}=x_{p+1}\cdots x_{h}y_{1}\cdots y_{p}$ (see Figure 7). On the other
hand, for $p\geq h$ we have

$z_{2}=y_{1}x_{1}y_{2}x_{2}\cdots
x_{h-1}y_{h}x_{h}vy_{h+1}f(x_{h})f(v)y_{h+2}\cdots
y_{p}f^{p-h}(x_{h})f^{p-h}(v)$

and $z_{3}=f^{p-h+1}(x_{h})y_{p-h+2}\cdots y_{p}$ (see Figure 7). In both
cases, $p=\frac{k_{2}-\ell_{1}}{2\nu}$ and $f(y_{p})f(y_{p})$ is a repeat word
in $w_{2}$ of size $|u|$. Then, by Lemma 2.10, $f(y_{p})=u$ implies that
$|f(y_{p})|=1$ or $|u|=1$ contradicting the fact that the insertions are
nontrivial.

##  4 Summary

In this section, we summarize the results from Section 3. First, we collect
the main results for Section 3, generalizing appropriately. Let
$w\in\Sigma_{DOW}$ be in ascending order of length $n$ and
$\mathcal{I}_{i}(\nu,k_{i},\ell_{i})$ for $i=1,2$ be two distinct insertions
into $w$. Assume that $k_{1}<k_{2}$ without loss of generality. Write
$w=z_{0}z_{1}z_{2}z_{3}z_{4}$ and assume that the four locations of insertions
(two from each $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$) appear between words
$z_{i}$ and $z_{i+1}$ for $i=0,\ldots,3$. In particular $|z_{0}|=k_{1}-1$. In
the following result we summarize Propositions 3.1, 3.4, and 3.15. Observe
that, by Theorem 3.26, the classification below is exhaustive.

###### Theorem 4.1

Let $w\in\Sigma_{DOW}$, and let $\mathcal{I}_{i}(\nu,k_{i},\ell_{i})$ for
$i=1,2$ be two distinct insertions into $w$. Let
$w_{i}=w\star\mathcal{I}(\nu,k_{i},\ell_{i})$ for $i=1,2$. Write
$w=z_{0}z_{1}z_{2}z_{3}z_{4}$ using the notation above. If $w_{1}\sim w_{2}$,
then the following hold:

$\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$
$\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$ Interleaving
$z_{1}z_{3}$ is a repeat word
$z_{1}z_{3}\sim\text{Int}\left(\frac{|z_{1}|}{\nu},\nu\right)$
$k_{1}<k_{2}\leq\ell_{1}<\ell_{2}$ Nested
$z_{1}z_{3}\sim\text{Nes}\left(\frac{|z_{1}|}{\nu},\nu\right)$ $z_{1}z_{3}$ is
a return word $k_{1}<k_{2}\leq\ell_{2}<\ell_{1}$ Sequential
$z_{1}z_{2}z_{3}\sim T_{\rho}\left(\nu,|z_{1}|,\frac{|z_{2}|}{2\nu}\right)$
$z_{1}z_{2}z_{3}\sim T_{\tau}\left(\nu,|z_{1}|,\frac{|z_{2}|}{2\nu}\right)$
$k_{1}\leq\ell_{1}<k_{2}\leq\ell_{2}$

###### Remark 4.2

Let $w,w_{1},w_{2}\in\Sigma_{DOW}$ be as in Theorem 4.1; then the structure of
the words $w_{1}$ and $w_{2}$ obtained by the insertions satisfies the
following properties ($uu^{\prime}$ is the inserted repeat or return word):

$\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$
$\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$ Interleaving
$z_{1}uz_{3}u$ is a repeat word
$z_{1}uz_{3}u^{R}\sim\text{Int}\left(\frac{|z_{1}|}{\nu}+1,\nu\right)$ Nested
$z_{1}uuz_{3}\sim\text{Nes}\left(\frac{|z_{1}|}{\nu}+1,\nu\right)$
$z_{1}uu^{R}z_{3}$ is a return word Sequential $z_{1}z_{2}uz_{3}u\sim
T_{\rho}\left(\nu,|z_{1}|,\frac{|z_{2}|}{2\nu}+1\right)$
$z_{1}z_{2}uz_{3}u^{R}\sim
T_{\tau}\left(\nu,|z_{1}|,\frac{|z_{2}|}{2\nu}+1\right)$

We generalize Proposition 3.7 and Corollary 3.18 with the following theorem.

###### Theorem 4.3

Let $w\in\Sigma_{DOW}$ and $\nu\in\mathbb{N}$. Suppose
$z_{1}z_{2}z_{3}\sqsubseteq w$ for some $z_{1},z_{3}\in\Sigma_{SOW}$ and
$z_{2}\in\Sigma^{\ast}$. If one of the following (1) - (6) holds, then there
exist two distinct insertions, $\mathcal{I}_{1}(\nu,k_{1},\ell_{1})$ and
$\mathcal{I}_{2}(\nu,k_{2},\ell_{2})$, such that
$w\star\mathcal{I}_{1}(\nu,k_{1},\ell_{1})\sim
w\star\mathcal{I}_{2}(\nu,k_{2},\ell_{2})$.  $(1)\quad z_{1}z_{3}$ is a repeat
word in $w$ ($\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$ and
interleaving insertions) $(2)\quad z_{1}z_{3}\sim\text{Int}(h,\nu)$ for some
$h\geq 1$ ($\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$ and
interleaving insertions) $(3)\quad z_{1}z_{3}\sim\text{Nes}(h,\nu)$ for some
$h\geq 1$ ($\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$ and nested
insertions) $(4)\quad z_{1}z_{3}$ is a return word in $w$
($\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$ and nested insertions)
$(5)\quad z_{1}z_{2}z_{3}\sim T_{\mathcal{\rho}}(\nu,m,j)$
($\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Rep}$ and sequential
insertions) for some $m\geq 0$ and $j\geq 1$ $(6)\quad z_{1}z_{2}z_{3}\sim
T_{\mathcal{\tau}}(\nu,m,j)$
($\mathcal{I}_{1},\mathcal{I}_{2}\in\operatorname{Ret}$ and sequential
insertions) for some $m\geq 0$ and $j\geq 1$

###### Remark 4.4

Observe that $11$ is the class representative for trivial repeat and return
words in $\Sigma^{\ast}$, and

$\text{Int}(1,1)=\text{Nes}(1,1)=T_{\rho}(1,0,1)=T_{\tau}(1,0,1)=11.$

By Theorem 4.3, it follows that for any
$w\in\Sigma_{DOW}\setminus\\{\epsilon\\}$, any $a\in\Sigma[w]$ can serve as
$z_{1}=a$ and $z_{3}=a$, and for any $\nu\in\mathbb{N}$, there exist a pair of
interleaving (nested resp.) insertions into $w$, $\rho(\nu,k_{1},\ell_{1})$
and $\rho(\nu,k_{2},\ell_{2})$ ($\tau(\nu,k_{1},\ell_{1})$ and
$\tau(\nu,k_{2},\ell_{2})$ resp.), which yield equivalent words. Moreover, if
$aa\sqsubseteq w$, then there is also a pair of sequential and trivial
insertions into $w$ which yield equivalent words.

##  5 Conclusion

In this paper, we characterized the structure of a DOW $w$ which allows two
distinct insertions to yield equivalent words. In particular, we proved that a
nontrivial repeat insertion and a nontrivial return insertion into $w$ cannot
produce equivalent resulting words. We summarized these results in Section 4;
with them, we can consider a “word graph” in which vertices are equivalence
classes of DOWs (with respect to $\sim$) and directed edges exist from
$[w]_{\sim}$ to $[w^{\prime}]_{\sim}$ if $w^{\prime}\sim
w\star\mathcal{I}(\nu,k,\ell)$ for some insertion $\mathcal{I}(\nu,k,\ell)$.
Our results characterize when two insertions define the same edge in this
graph. It is also natural to define the distance between $[w]_{\sim}$ and
$[w^{\prime}]_{\sim}$ as the length of a shortest path from $[w]_{\sim}$ to
$[w^{\prime}]_{\sim}$ in the word graph. The notion of determining the
distance from the empty word $[\epsilon]_{\sim}$ to $[w]_{\sim}$ may describe
the complexity of a particular DNA rearrangement processes in the ciliate
Oxytricha trifallax [5, 11]. It may also be of interested to compare different
paths between two given equivalence classes and to characterize the subgraphs
which may appear in such a word graph.

Acknowledgement. This work is supported by NIH grant R01 GM109459, Simons
Foundation grant 594594, and NSF grants CCF-1526485, DMS-1800443, and
DMS-1764406.

## References

  * [1] Arredondo RC. Properties of graphs used to model DNA recombination. Graduate Theses and Dissertations, University of South Florida. 2014.
  * [2] Braun J, Nabergall L, Neme R, Landweber LF, Saito M, Jonoska N. Russian doll genes and complex chromosome rearrangements in Oxytricha trifallax. G3: Genes, Genomes, Genetics. 2018; 8(5):1669–1674. doi:10.1534/g3.118.200176.
  * [3] Burns J, Dolzhenko E, Jonoska N, Muche T, Saito M. Four-regular graphs with rigid vertices associated to DNA recombination. Discrete Applied Mathematics. 2013; 161(10-11):1378–1394. doi:10.1016/j.dam.2013.01.003.
  * [4] Burns J, Jonoska N, Saito M. Genus ranges of chord diagrams. Journal of Knot Theory and its Ramifications. 2015; 24(4):1550022, doi:10.1142/S0218216515500224.
  * [5] Burns J, Kukushkin D, Chen X, Landweber LF, Saito M, Jonoska N. Recurring patterns among scrambled genes in the encrypted genome of the ciliate Oxytricha trifallax. Journal of Theoretical Biology. 2016; 410:171–180. doi:10.1016/j.jtbi.2016.08.038.
  * [6] Chang WJ, Bryson PD, Liang H, Shin MK, Landweber LF. The evolutionary origin of a complex scrambled gene. Proceedings of the National Academy of Sciences of the United States of America. 2005; 102(42):15149–15154. doi:10.1073/pnas.0507682102.
  * [7] Choffrut C, Karhumäki J. Combinatorics of words. Handbook of Formal Languages, Springer Berlin/Heidelberg. 1997; 329–438. doi:10.1007/978-3-642-59136-5_6.
  * [8] Courcelle B. Circle graphs and monadic second-order logic. Journal of Applied Logic. 2008; 6(3):416–442. doi:10.1016/j.jal.2007.05.001.
  * [9] Ehrenfeucht A, Harju T, Petre I, Prescott DM, Rozenberg G. Computation in living cells: gene assembly in ciliates. Natural Computing Series, Springer Berlin/Heidelberg. 2003. doi:10.1007/978-3-662-06371-2.
  * [10] Gibson A. Homotopy invariants of Gauss words. Mathematische Annalen. 2011; 349(4):871–887. doi:10.1007/s00208-010-0536-0.
  * [11] Jonoska N, Nabergall L, Saito M. Patterns and distances in words related to DNA rearrangement. Fundamenta Informaticae. 2017; 154(1-4):225–238. doi:10.3233/FI-2017-1563.
  * [12] Levenshtein V. Binary codes capable of correcting spurious insertions and deletions of ones. Russian Problemy Peredachi Informatsii. 1965; 1:12–25.
  * [13] Lothaire M. Algebraic combinatorics on words. Cambridge University Press. 2002. doi:10.1017/CBO9781107326019.
  * [14] Lyndon RC, Schützenberger MP. The equation $a^{M}=b^{N}c^{P}$ in a free group. Michigan Math. J. 1962; 9(4):289–298. doi:10.1307/mmj/1028998766.
  * [15] Needleman S, Wunsch C. A general method applicable to the search for similarities in the amino acid sequences of two proteins. Journal of Molecular Biology. 1970; 48(3):444–453. doi:10.1016/0022-2836(70)90057-4.
  * [16] Sankoff D, Kruskal J. Time Warps, String Edits, and Macromolecules. The Theory and Practice of Sequence Comparison, Reading. 1983.
  * [17] Shtylla B, Traldi L, Zulli L. On the realization of double occurrence words. Discrete Mathematics. 2009; 309(6):1769–1773. doi:10.1016/j.disc.2008.02.035.
  * [18] Stein PR. On a class of linked diagrams, I. Enumeration. Journal of Combinatorial Theory, Series A. 1978; 24(3):357–366. doi:10.1016/0097-3165(78)90065-1.
  * [19] Turaev V. Virtual strings, Annales de l’Institut Fourier. 2004; 54(7):2455–2525. doi:10.5802/aif.2086.