On Occurrence-Preserving Morphisms

In this work, we make three main contributions. First, to answer the above question, we introduce the notion of interference-free morphisms, analyze their properties, and uncover a connection to recognizable morphisms (Theorem 19). Second, we provide a precise characterization of occurrence-preserving morphisms in terms of interference-freeness (Theorem 22). Third, as an application, we apply this characterization to the Fibonacci and Thue-Morse words to identify their minimal unique substrings (MUSs) (Theorem 32 and Theorem 34). We further exploit the connection between MUSs and net occurrences [23] to simplify existing proofs on net occurrences in these words [13]. In the process, we establish new properties of these morphisms and words that may have independent interest.

Let $\mathrm{\Sigma }$ be an ordered alphabet. We assume $\mathrm{\Sigma }=\{𝚊,𝚋\}$ when $|\mathrm{\Sigma }|=2$. A word (or string) is an element of ${\mathrm{\Sigma }}^{\ast }$. The length of a word $w$ is denoted as $|w|$. Let $\epsilon$ denote the empty word of length 0. We use $w[i]$ to denote the $i^{\text{th}}$ character of a word $w$. Let $u\cdot v=uv$ denote the concatenation of two words, $u$ and $v$. A factor (or substring) of a word $w$ of length $n$, starting at position $i$ and ending at position $j$, is written as $w[i\mathrm{\dots }j]$. A factor $w[1\mathrm{\dots }j]$ is called a prefix of $w$, while $w[i\mathrm{\dots }n]$ is called a suffix of $w$. A factor $u$ of $w$ is a proper factor if $u\ne w$. For two words $u$ and $w$, let ${\mathrm{occ}}_w(u)=\{i|w[i\mathrm{\dots }i+|u|-1]=u\}$ be the set of (starting positions of) occurrences of $u$ in $w$, and let ${\mathrm{\#}\mathrm{occ}}_w(u)=|{\mathrm{occ}}_w(u)|$. When convenient, we identify an occurrence $i\in {\mathrm{occ}}_w(u)$ with its corresponding interval $[i,i+|u|-1]$ in $w$. For convenience, we treat the empty word $\epsilon$ as occurring $|w|+1$ times in $w$: before position $1$, between positions $i$ and $i+1$ for $1\le i\le |w|$, and after position $|w|$. We represent the $i^{\text{th}}$ such occurrence by the interval $[i,i-1]$ for $1\le i\le |w|+1$. For a word $w$, let $w^R=w[|w|]\mathrm{\cdots }w[1]$ denote the reverse of $w$. For a non-empty word $w$, a sequence of non-empty words ${(x_k)}_{k=1}^m$ is referred to as a factorization of $w$ if $w=x_1\mathrm{\cdots }{x}_m$. For a word $w$, a word of the form $w[i\mathrm{\dots }|w|]\cdot w[1\mathrm{\dots }i-1]$, for some $1\le i\le |w|$, is called a rotation of $w$. Let $ℛ(w)$ denote the multiset of all $|w|$ rotations of $w$. For a word $w$ with $|w|\ge 2$, let $w^{⊲}=w[1\mathrm{\dots }|w|-1]$ denote its longest proper prefix.

Let $\mathrm{\Sigma }$ and $\mathrm{\Gamma }$ be two alphabets. A morphism is a map $\varphi :{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Gamma }}^{\ast }$ such that $\varphi (uv)=\varphi (u)\varphi (v)$ for all $u,v\in {\mathrm{\Sigma }}^{\ast }$. For each $c\in \mathrm{\Sigma }$, $\varphi (c)$ is called an image¹¹1In this paper, we use the term image only for $\varphi (c)$ with $c\in \mathrm{\Sigma }$, and not for $\varphi (u)$ with $u\in {\mathrm{\Sigma }}^{\ast }$. of $\varphi$, and let $\text{Im}\left(\varphi \right)=\{\varphi (c)|c\in \mathrm{\Sigma }\}$ be the set of images of $\varphi$. Letting $\mathrm{\Sigma }=\{{\alpha }_1,\mathrm{\dots },{\alpha }_{\sigma }\}$, $\varphi$ can be equivalently specified by ${\alpha }_1\mapsto \varphi ({\alpha }_1),\mathrm{\dots },{\alpha }_{\sigma }\mapsto \varphi ({\alpha }_{\sigma })$. Let ${\varphi }^0(u)=u$ and let ${\varphi }^i(u)=\varphi ({\varphi }^{i-1}(u))$ for each $i\ge 1$. Further, $\varphi$ is non-erasing if $\varphi (a)\ne \epsilon$ for all $a\in \mathrm{\Sigma }$; $\varphi$ is injective²²2Note that this defines a stronger notion of injectivity than simply requiring that for all $c\ne c^{\prime }\in \mathrm{\Sigma }$, $\varphi (c)\ne \varphi (c^{\prime })$. if $\varphi (u)\ne \varphi (v)$ for all $u\ne v\in {\mathrm{\Sigma }}^{\ast }$; $\varphi$ is $\mathrm{\ell }$-uniform if $|\varphi (a)|=\mathrm{\ell }$ for all $a\in \mathrm{\Sigma }$. For a binary word $w$, let $\overline{w}$ denote the word obtained by applying the morphism $𝚊\mapsto 𝚋,𝚋\mapsto 𝚊$.

Let $\phi$ denote the Fibonacci morphism defined by $\phi (\text{a})=\text{ab}$ and $\phi (\text{b})=\text{a}$. Let $\mu$ denote the Thue-Morse morphism defined by $\mu (\text{a})=\text{ab}$ and $\mu (\text{b})=\text{ba}$. For each $i\ge 1$, let $F_i={\phi }^{i-1}(\text{b})$ be the (finite) Fibonacci word of order $i$. For each $i\ge 1$, let ${𝒯}_i={\mu }^{i-1}(\text{a})$ be the (finite) Thue-Morse word of order $i$. The Fibonacci and Thue-Morse words can also be obtained as follows: $F_1=\text{b},F_2=\text{a}$, and $F_i=F_{i-1}{F}_{i-2}$ for each $i\ge 3$; ${𝒯}_1=\text{a}$ and ${𝒯}_i={𝒯}_{i-1}\overline{{𝒯}_{i-1}}$ for each $i\ge 2$. Further, for each $i\ge 1$, let $f_i=|F_i|$, which equals the $i^{\text{th}}$ Fibonacci number, and let ${\tau }_i=|{𝒯}_i|=2^{i-1}$. We next review the following known properties of Fibonacci words.

Consider a string $w$ and a unique substring $u$ of $w$. Let $[i,j]$ be the only occurrence of $u$ in $w$. We say $u$ is a minimal unique substring (MUS) of $w$ if both strings $w[i+1\mathrm{\dots }j]$ and $w[i\mathrm{\dots }j-1]$ are repeated in $w$. Let $\text{MUS}\left(w\right)$ denote the set of MUSs of $w$. An occurrence $[i,j]$ in $w$ is a net occurrence if the corresponding string $w[i\mathrm{\dots }j]$ is repeated, while both left extension $w[i-1\mathrm{\dots }j]$ and right extension $w[i\mathrm{\dots }j+1]$ are unique. When $i=1$, $w[i-1\mathrm{\dots }j]$ is assumed to be unique; when $j=|w|$, $w[i\mathrm{\dots }j+1]$ is assumed to be unique. Let $\text{NO}\left(w\right)$ denote the set of net occurrences in $w$.

Let $n=|F_i|$ and consider the factorization of $\phi (F_i)=F_{i+1}=X_1\mathrm{\cdots }{X}_n$ where each $X_j=\phi (F_i[j])\in \text{Im}\left(\phi \right)$ for $1\le j\le n$. Note that $i+1$ is even. By Observation 1, $\mathrm{𝚊𝚋𝚊}$ is a suffix of even Fibonacci words. Thus, $X_{n-1}=\phi (𝚊)=\mathrm{𝚊𝚋}$ and $X_n=\phi (𝚋)=𝚊$. It follows that $\phi (F_i)$ admits an interfered image factorization $\phi (F_i)=x\cdot y\cdot z$ with $x=\epsilon$, $y=X_1\mathrm{\dots }{X}_{n-1}$, and $z=X_n=𝚊$ being a proper prefix of $\phi (𝚊)=\mathrm{𝚊𝚋}$. Therefore, $\phi$ is not interference-free on the desired set. $◀$ This, combined with $\mu$ not being interference-free on $\{\mathrm{𝚊𝚊}\}$ (Example 2), gives the following.

For each occurrence of $u$ in $v$, there exist words $v^{\mathrm{𝑝𝑟𝑒𝑓}},v^{\mathrm{𝑠𝑢𝑓}}\in {\mathrm{\Sigma }}^{\ast }$ such that $v=v^{\mathrm{𝑝𝑟𝑒𝑓}}\cdot u\cdot v^{\mathrm{𝑠𝑢𝑓}}$. Applying $\varphi$ to both sides gives $\varphi (v)=\varphi (v^{\mathrm{𝑝𝑟𝑒𝑓}})\cdot \varphi (u)\cdot \varphi (v^{\mathrm{𝑠𝑢𝑓}})$. Hence, each occurrence of $u$ in $v$ yields an occurrence of $\varphi (u)$ in $\varphi (v)$. Moreover, distinct occurrences of $u$ in $v$ yield distinct occurrences of $\varphi (u)$ in $\varphi (v)$, since they correspond to different prefixes $v^{\mathrm{𝑝𝑟𝑒𝑓}}$. Therefore, ${\mathrm{\#}\mathrm{occ}}_v(u)\le {\mathrm{\#}\mathrm{occ}}_{\varphi (v)}(\varphi (u))$. $◀$

Note that the non-erasing condition is not explicitly stated in Theorem 22; the following observation shows that it is already implied by injectivity.

We proceed by contrapositive. If $\varphi$ is erasing, then there exists $c\in \mathrm{\Sigma }$ such that $\varphi (c)=\epsilon$. Then, $\varphi (cc)=\varphi (c)=\epsilon$ but $cc\ne c$, which means $\varphi$ is not injective. $◀$

The next lemma traces occurrences of $\varphi (u)$ in $\varphi (v)$ back to the corresponding occurrences in $v$, identifying the only two possible cases, illustrated on the left of Figure 5.

Assume, for contradiction, that $\varphi (u)$ is a factor of $\varphi (v)$ while neither Case (i) nor Case (ii) holds. Since $u$ is not a factor of $v$, the only possible way for $\varphi (u)$ to be a factor of $\varphi (v)$ is that there exists a factor $q^{\prime }$ of $v$ such that $q^{\prime }\ne u$ and $\varphi (q^{\prime })=\varphi (u)$. However, this contradicts the injectivity of $\varphi$. $◀$

We aim to show that ${\mathrm{\#}\mathrm{occ}}_v(u)\ge {\mathrm{\#}\mathrm{occ}}_{\varphi (v)}(\varphi (u))$. We follow the two cases described in Lemma 26. In particular, we prove that Case (ii) is impossible and only Case (i) is possible under the interference-free condition in Theorem 22. Recall that $q$ was introduced in Lemma 26. First observe that if $|q|=1$, i.e., $q$ is a symbol, then Case (ii) is impossible, as it would force one of the following two contradictions. For any $1\le i\le |v|$,

• $\mathrm{■}$

  if $\varphi (u)$ is a proper prefix or a proper suffix of $\varphi (v[i])$, then $\varphi (u)$ admits an interfered image factorization where $x=y=\epsilon$ and $z$ is a proper prefix of $\varphi (v[i])$, or $x$ is a proper suffix of $\varphi (v[i])$ and $y=z=\epsilon$;

• $\mathrm{■}$

  if $\varphi (u)$ is a proper factor of $\varphi (v[i])$ but is neither a prefix nor a suffix of $\varphi (v[i])$, then $\varphi (u)$ is an inner image factor.

Thus, we know that $|q|>1$. We now show that if $\varphi$ is interference-free on $\{u\}$ then Case (ii) is impossible. We proceed by contrapositive: assume Case (ii) does occur, and we will show that $\varphi$ is not interference-free on $\{u\}$. Let $\varphi (q)=Y_1\mathrm{\cdots }{Y}_{|q|}$ where $Y_i\in \text{Im}\left(\varphi \right)$ for $1\le i\le |q|$. If $\varphi (u)$ is a proper factor of $\varphi (q)$, then there exists a factor of $\varphi (q)$ of the form $Y_c\mathrm{\cdots }{Y}_d$ (for some ) such that $\varphi (u)$ is a proper factor of $Y_c\mathrm{\cdots }{Y}_d$ and $Y_{c+1}\mathrm{\cdots }{Y}_{d-1}$ is a proper factor of $\varphi (u)$. (We define $Y_{c+1}\mathrm{\cdots }{Y}_{d-1}$ to be $\epsilon$ when $d=c+1$.) Hence, we have $\varphi (u)=x^{\prime }\cdot Y_{c+1}\mathrm{\cdots }{Y}_{d-1}\cdot z^{\prime }$, where $x^{\prime }$ is a suffix of $Y_c$, $z^{\prime }$ is a prefix of $Y_d$, and $x^{\prime }\cdot z^{\prime }\ne Y_c\cdot Y_d$ (illustrated on the right of Figure 5). Now we are ready to show that $\varphi$ is not interference-free on $\{u\}$ by constructing an interfered image factorization of $\varphi (u)=x\cdot y\cdot z$, where

Thus, we have proved by contrapositive that Case (ii) is impossible when $\varphi$ is interference-free on $\{u\}$. Therefore, only Case (i) is possible under the conditions in Theorem 22. In other words, we have shown that if $\varphi (u)$ is a factor of $\varphi (v)$, then $u$ is a factor of $v$. This implies that ${\mathrm{\#}\mathrm{occ}}_v(u)\ge {\mathrm{\#}\mathrm{occ}}_{\varphi (v)}(\varphi (u))$. Combining with Lemma 24, we conclude that ${\mathrm{\#}\mathrm{occ}}_v(u)={\mathrm{\#}\mathrm{occ}}_{\varphi (v)}(\varphi (u))$. $◀$

Finally, Theorem 22 follows from Proposition 23 by induction.

$(\Rightarrow )$ If $u$ occurs at position $p$ in $v$, then $v$ can be factorized as $v=v[1\mathrm{\dots }p-1]\cdot u\cdot y$ for $y\in {\mathrm{\Sigma }}^{\ast }$. It follows that ${\varphi }^k(v)={\varphi }^k(v[1\mathrm{\dots }p-1])\cdot {\varphi }^k(u)\cdot {\varphi }^k(y)$, and thus ${\varphi }^k(u)$ occurs at position $|{\varphi }^k(v[1\mathrm{\dots }p-1])|+1$ in ${\varphi }^k(v)$.

$(\Leftarrow )$ From the “$\Rightarrow$” direction we can infer that ${\mathrm{\#}\mathrm{occ}}_v(u)\le {\mathrm{\#}\mathrm{occ}}_{{\varphi }^k(v)}({\varphi }^k(u))$. By Theorem 22, we know that ${\mathrm{\#}\mathrm{occ}}_v(u)={\mathrm{\#}\mathrm{occ}}_{{\varphi }^k(v)}({\varphi }^k(u))$. Thus, there does not exist an occurrence $p^{\prime }$ of ${\varphi }^k(u)$ in ${\varphi }^k(v)$ such that $p^{\prime }\ne |{\varphi }^k(v[1\mathrm{\dots }p-1])|+1$ for any $p\in {\mathrm{occ}}_v(u)$. Therefore, the “$\Leftarrow$” direction also holds. $◀$

Note that if $\varphi$ is $\mathrm{\ell }$-uniform, then $|{\varphi }^k(v[1\mathrm{\dots }p-1])|+1={\mathrm{\ell }}^k(p-1)+1$.