Computing the index of non-isometric k -ary words with Hamming and Lee distance

Abstract

Isometric words are those words whose occurrence as a factor in a transformation of a word u in a word v can be avoided, while preserving the minimal length of the transformation. Such minimal length refers to a distance between u and v. In the literature, isometric words have been considered with respect to the Hamming distance and the Lee distance; the former especially for binary words, while the latter for k-ary words, with $k ⩾ 2$ . Ham- and Lee- isometric words have been characterized in terms of their overlaps with errors. In this paper, we give algorithms to decide whether a word f, of length n, is Ham- or Lee-isometric and provide evidence of the possible non-isometricity by returning a pair of words of minimal length whose transformation cannot avoid the factor f. Such a pair of words is called a pair of witnesses and the minimal length of the witnesses is called the index of f. The algorithms run in $O (n)$ time with a preprocessing of $O (n)$ time and space to construct a data structure that allows answering $LCA$ queries on the suffix tree of f in constant time. The correctness of the algorithms lies on some theoretical results on the index and the witnesses of a word that are here presented. The investigation on the index is completed by the characterization of words with minimum/maximum index. All the results are shown referring to both Hamming and Lee distance.

Keywords

Isometric words words avoiding factors index of a word overlap Hamming and Lee distances

1. Introduction

The notion of isometric word has been introduced in the framework of the research on hypercubes and, more in general, on k-ary n-cubes. The k-ary n-cube is one of the most attractive interconnection network for parallel computer systems. With the aim of providing a class of subgraphs of the hypercube $Q_{n}$ having a considerably smaller size, still maintaining some metric properties, Hsu introduced the Fibonacci cubes [13]. They are they subgraphs of the hypercube restricted to vertices associated with binary words that do not contain 11 as a factor. Fibonacci cubes are isometric subgraphs of $Q_{n}$ . They received a lot of attention afterwards (see [15] for a survey) and they have been then extended to define the generalized Fibonacci cube $Q_{n} (f)$ [14], as the subgraph of the hypercube $Q_{n}$ restricted to the vertices associated with binary words avoiding the word f as a factor, i.e. f-free binary words. In this framework, a binary word f is said isometric when, for any $n ⩾ 1$ , $Q_{n} (f)$ can be isometrically embedded into $Q_{n}$ , and non-isometric, otherwise [16]. For example, the word 11 is isometric.

Observe that, in the binary case, the distance between two vertices in the hypercube coincides with their Hamming distance. Hence, isometric binary words can be characterized ignoring hypercubes and adopting a point of view closer to combinatorics on words. A binary word f is isometric if and only if for any integer $d ⩾ | f |$ and any pair of words u and v of length d which do not contain the factor f, u can be transformed in v by exchanging one by one the bits on which they differ and generating only words which do not contain f. Differently saying, this transformation is composed by single steps transforming a word in another at Hamming distance 1. We will call it an f-free Ham-transformation and the resulting isometric words, Ham-isometric words. When moving from binary to k-ary alphabets, with $k ⩾ 2$ , the hypercubes are replaced by the k-ary n-cubes where the vertices are k-ary words of length n. In this case, the distance between two vertices is no more captured by the Hamming distance, but by the Lee distance. Hence, in an analogous way, f-free Lee-transformations and Lee-isometric k-ary words have been introduced; see [4], and [3] on quaternary words. Recently, isometric words have been introduced and investigated in [1,2] referring to an edit distance based on swap and mismatch errors. Also, binary non-isometric words have been considered in the two-dimensional setting, and bad pictures have been investigated [7]. See [9] for such results in a common framework.

Deciding whether a word is Ham-isometric (Lee-isometric, resp.) can be efficiently done using a characterization of Ham-non-isometric (Lee-non-isometric, resp.) words as the ones showing a particular overlap with errors, called 2-Ham-error overlap (2-Lee-error overlap, resp.). A 2-Ham-error overlap (2-Lee-error overlap, resp.) of a word f is a prefix of f whose Hamming (Lee, resp.) distance from the suffix of same length is exactly 2. The evidence that a given word f is Ham-non-isometric (Lee-non-isometric, resp.) can be given by exhibiting a pair of f-free words whose Ham-transformations (Lee-transformations, resp.) cannot avoid the factor f. Such pair of words is called a pair of Ham-witnesses (Lee-witnesses, resp.) and the minimal length of the witnesses is called the Ham-index (Lee-index, resp.) of f. The main goal of this paper is in efficiently deciding whether a word is isometric or not, computing its index and providing a pair of witnesses of minimal length. All the results and considerations will be given for k-ary words, for any $k ⩾ 2$ , and referring to both Hamming and Lee distance. With the sake of readability, when a sentence or statement holds true in general for both distances, we will sometimes omit to specify the distance (Hamming or Lee distance).

The notion of Lee-isometric word equals that of Ham-isometric one for the first values of the cardinality k of the alphabet, $k = 2, 3$ . Actually, the Lee and Hamming distances coincide in these cases. Observe that Ham-isometric words exist on any k-ary alphabet, with $k ⩾ 2$ . On the contrary, when $k > 4$ , no Lee-isometric word exists and any Lee-non-isometric word has Lee-index equal to its length [4]. Therefore, the computation of the Ham-index is proposed for any $k ⩾ 2$ , while the results on the Lee-index are stated only for $k = 4$ . A “standard” construction of Ham-witnesses for a Ham-non-isometric word was given in [18] for binary words, and generalized to k-ary words in [3,4]. A pair of Ham-witnesses is constructed in correspondence to any 2-Ham-error overlap. To complete the scenario, we provide a “standard” construction of Lee-witnesses for a Lee-non-isometric quaternary word. In this case, a new situation must be handled; it is when the Lee distance 2 is realized by an error in a unique position, rather than by two errors in two distinct positions. In this case, a pair of Lee-witnesses can be directly computed from the word, without going through its binary representation, as it was in [3]. As a main result, we show that such “standard” witnesses are minimal in length, that is the index of f can be computed as their minimal length, taken over all 2-error overlaps of f. This result is shown in Theorem 2 referring to the Hamming distance and in Theorem 3 referring to the Lee distance. The construction of such standard witnesses allows to restate some lower and upper bounds on the Ham-index (Lee-index, resp.) of f, already given in [3,4]. The investigation on the index of a non-isometric word is completed by the characterization of words which attain the bounds, i.e., which exhibit a minimum/maximum index.

The above mentioned results (see Section 3) have been then applied to design algorithms to efficiently decide whether a word is isometric, to compute its index and to provide some witnesses, if the word is non-isometric. More precisely, we will first show Algorithm 1, that computes the Ham-index of a k-ary word, with $k ⩾ 2$ , and yields a pair of Ham-witnesses of minimal length, when the word is Ham-non-isometric. An analogous Algorithm 2 is then provided when $k = 4$ and the Lee-distance is concerned. Note that an algorithm for computing the index of a binary word and a pair of its witnesses is given in [18] referring to the Hamming distance; it runs in $O (n^{3})$ time on a binary word of length n. The algorithms designed in this paper run in $O (n)$ time and space. Some implementing ideas – namely the Kangaroo method – take inspiration from algorithms provided in a recent paper [8] to check whether a word is Ham-isometric and Lee-isometric in $O (n)$ time and space. These algorithms check if a word f has at least one q-error overlap, for some integer q, while our algorithms continue finding and analysing all 2- error overlaps to provide the additional information, as said before, while preserving time and space complexity.

The efficiency of Algorithm 1 and Algorithm 2 relies on the Kangaroo method [12,17]. This method is generally used in designing algorithms for efficient pattern matching with mismatches. It allows finding the mismatches in a given alignment of two words by “jumping” from one error to the next, as here explained. Recall that a 2-Ham-error overlap of $f = f [0 \dots n - 1]$ is a suffix of f that differs from the prefix of the same length in exactly 2 positions; while a 2-Lee-error overlap of $f = f [0 \dots n - 1]$ is a suffix of f at Lee distance 2 from the prefix of the same length. In both cases, it can be detected comparing each suffix ${suf}_{n - i} (f)$ of f, starting at position i, for $i = 1, \dots, n - 1$ , with the string itself, that can be considered as the suffix ${suf}_{n} (f)$ starting at position 0. The key observation is that the first position where the suffixes (possibly) differ is the position just after the longest common prefix of the two suffixes. Similarly for the second error position. Suffix trees are a well-known data structure to handle the suffixes of a given word. In particular, the longest common prefix of two suffixes can be obtained as the Lowest Common Ancestor ( $LCA$ ) of the two corresponding leaves in the tree. A $LCA$ query on the suffix tree can be answered in constant time and $O (n)$ space, if the suffix tree is replaced by some equivalent arrays (the Suffix Array, its inverse, and the Longest Common Prefix Array [10]) and a constant time algorithm to answer Range Minimum Queries ( $RMQ$ ) is available [11].

The algorithm for computing the Lee-index is obtained adapting the one for the Ham-index to the new distance, without changing its complexity. Hopefully, these algorithms could be modified, to compute the index and related witnesses of a word, referring to other distances, besides Hamming and Lee ones.

A preliminary and partial version of this paper is [5].

2. Isometric words

This section is devoted to establishing the definitions and notation about Ham-isometric and Lee-isometric words.

Let Σ be an alphabet and $| Σ | = k$ . Throughout the paper, Σ will be identified with $Z_{k} = {0, 1, \dots, k - 1}$ , the ring of integers modulo k. A word (or string) $f \in Σ^{*}$ of length n is $f = x_{1} x_{2} \dots x_{n}$ , where $x_{1}, x_{2}, \dots, x_{n}$ are symbols in Σ. The set of words over Σ of length n is denoted $Σ^{n}$ . Let $f [i]$ denote the symbol of f in position i, i.e. $f [i] = x_{i}$ . Then, $f [i \dots j] = x_{i} \dots x_{j}$ , for $1 ⩽ i ⩽ j ⩽ n$ , is a factor of f. A word $s \in Σ^{*}$ is said f-free if it does not contain f as a factor. The prefix of f of length l is ${pre}_{l} (f) = f [1 \dots l]$ ; while the suffix of f of length l is ${suf}_{l} (f) = f [n - l + 1 \dots n]$ . When ${pre}_{l} (f) = {suf}_{l} (f)$ then ${pre}_{l} (f)$ is referred to as an overlap of f of length l.

Note that, throughout the paper, a word $f \in Σ^{n}$ is indexed starting from 1, that is $f = f [1 \dots n]$ , according to the literature on isometric words, unless for Section 5, devoted to the algorithms, where f is indexed starting from 0, that is $f = f [0 \dots n - 1]$ , according to usual programming languages.

Let $u, v \in Σ^{n}$ , $u = x_{1} \dots x_{n}$ and $v = y_{1} \dots y_{n}$ , be two words of the same length. Then, the Hamming distance ${dist}_{H} (u, v)$ between u and v is the number of positions at which u and v differ. The Lee distance between u and v is $\begin{array}{c} {dist}_{L} (u, v) = \sum_{i = 1}^{n} min (| x_{i} - y_{i} |, k - | x_{i} - y_{i} |) \end{array}$ where Σ is identified with $Z_{k}$ .

In the sequel, Σ will denote a generic alphabet of cardinality k, while Δ will denote the quaternary alphabet $Δ = {A, C, T, G}$ , referred to as the genetic alphabet. Symbols A and T (C and G, resp.) will be called complementary symbols, in analogy to the Watson-Crick complementary bases they represent. The alphabet Δ will be identified with $Z_{4}$ , in such a way that A, C, T, and G will be identified with 0, 1, 2, and 3, respectively. Therefore, pairs of complementary symbols have Lee distance 2, whereas pairs of distinct non-complementary symbols have Lee distance 1.

Let us now define Ham-isometric words on a generic k-ary alphabet with $k ⩾ 2$ . The definitions are based on the process of transforming a word in another one of equal length, changing one symbol at a time.

Definition 1.
Let Σ be a k-ary alphabet, $f \in Σ^{n}$ , and $u, v \in Σ^{d}$ .

A Ham-transformation of length h from u to v is a sequence of words $w_{0}, w_{1}, \dots, w_{h}$ such that $w_{0} = u$ , $w_{h} = v$ , and for any $i = 0, 1, \dots, h - 1$ , ${dist}_{H} (w_{i}, w_{i + 1}) = 1$ .

The Ham-transformation is f-free if for any $i = 0, 1, \dots, h$ , the word $w_{i}$ is f-free.

The word f is Ham-isometric if for all $d ⩾ n$ and f-free words u, $v \in Σ^{d}$ , there is an f-free Ham-transformation from u to v of length equal to ${dist}_{H} (u, v)$ . A word is Ham-non-isometric if it is not Ham-isometric.

A pair $(u, v)$ of words u, v $\in Σ^{d}$ is referred to as a pair of Ham-witnesses for f, if u and v are f-free words and there does not exist an f-free Ham-transformation from u to v of length equal to ${dist}_{H} (u, v)$ .

If f is Ham-non-isometric then its Ham-index, denoted by $I_{H} (f)$ , is the shortest length d of u, v such that $(u, v)$ is a pair of Ham-witnesses for f. The Ham-index of a Ham-isometric word is defined ∞.
Example 1.
Let $f = 010$ , $u = 0000$ , $v = 0110$ be words in ${0, 1}^{}$ . The distance ${dist}_{H} (u, v) = 2$ , since u and v differ in positions 2 and 3. Hence, there are only two possible Ham-transformations from u to v of length 2. They are the following ones, $w_{0} = 0000$ , $w_{1} = 0100$ , $w_{2} = 0110$ , and $w_{0}^{'} = 0000$ , $w_{1}^{'} = 0010$ , $w_{2}^{'} = 0110$ . Neither transformation is f-free. Therefore f is Ham-non-isometric and $(u, v)$ is a pair of Ham-witnesses for $f = 010$ .

Analogous definitions can be given by considering the Lee distance (cf. [3,4]). They can be essentially obtained by substituting “Ham” with “Lee” in Definition 1. Nevertheless, the definitions are stated here below for the sake of completeness.
Definition 2.
Let Σ be a k-ary alphabet, $f \in Σ^{n}$ , and $u, v \in Σ^{d}$ .

A Lee-transformation* of length h from u to v is a sequence of words $w_{0}, w_{1}, \dots, w_{h}$ such that $w_{0} = u$ , $w_{h} = v$ , and for any $i = 0, 1, \dots, h - 1$ , ${dist}_{L} (w_{i}, w_{i + 1}) = 1$ .

The Lee-transformation is f-free if for any $i = 0, 1, \dots, h$ , the word $w_{i}$ is f-free.

The word f is Lee-isometric if for all $d ⩾ n$ and f-free words u, $v \in Σ^{d}$ , there is an f-free Lee-transformation from u to v of length equal to ${dist}_{L} (u, v)$ . A word is Lee-non-isometric if it is not Lee-isometric.

A pair $(u, v)$ of words u, v $\in Σ^{d}$ is referred to as a pair of Lee-witnesses for f, if u and v are f-free words and there does not exist an f-free Lee-transformation from u to v of length equal to ${dist}_{L} (u, v)$ .

If f is Lee-non-isometric then its Lee-index, denoted by $I_{L} (f)$ , is the shortest length d of u, v such that $(u, v)$ is a pair of Lee-witnesses for f. The Lee-index of a Lee-isometric word is defined ∞.

Note that, for any $f \in Σ^{n}$ and $u, v \in Σ^{d}$ , there exists an f-free Ham-transformation (Lee-transformation, resp.) from u to v if and only if there exists an f-free Ham-transformation (Lee-transformation, resp.) from v to u.
Example 2.
Let Δ be the quaternary genetic alphabet, $f = ACT$ , $u = ACCCT$ , and $v = ACGCT$ . Observe that ${dist}_{L} (u, v) = 2$ , since u and v differ in their third position only and ${dist}_{L} (C, G) = 2$ . The sequences $ACCCT$ , $ACACT$ , $ACGCT$ and $ACCCT$ , $ACTCT$ , $ACGCT$ are two Lee-transformations from u to v of length equal to ${dist}_{L} (u, v) = 2$ ; they are not f-free. Actually, no f-free Lee-transformation exists from u to v. This shows that $ACT$ is Lee-non-isometric and that $(u, v)$ is a pair of Lee-witnesses for $ACT$ .
Remark 1.
Let $f \in Σ^{}$ and let $u, v \in Σ^{}$ be two f-free words. Consider any f-free Ham- (Lee-, resp.) transformation from u to v of length equal to ${dist}_{H} (u, v)$ ( ${dist}_{L} (u, v)$ , resp.). Then, only symbols in the positions where u and v differ are modified in this transformation. Moreover, at each step of the Ham- (Lee-, resp.) transformation, a symbol x can be replaced by y only if ${dist}_{H} (x, y) = 1$ ( ${dist}_{L} (x, y) = 1$ , resp.). Furthermore, in a Lee-transformation, each position i such that ${dist}_{L} (u [i], v [i]) = h$ is replaced exactly h times.
Remark 2.
Let Σ be a k-ary alphabet and consider the case $k = 2, 3$ . In this case, for any $u, v \in Σ^{}$ words of the same length, ${dist}_{L} (u, v) = {dist}_{H} (u, v)$ and any Lee-transformation from u to v is itself a Ham-transformation, and vice versa, thus preserving length and f-freeness. Hence, a word f is Ham-non-isometric if and only if f is Lee-non-isometric and $I_{H} (f) = I_{L} (f)$ .

For the next definition refer to Fig. 1 showing a q-Ham-error overlap of f of length l and shift r with $q = 2$ , $m = 2$ , i and j error positions, $x, \overline{x}, y, \overline{y} \in Σ$ such that ${dist}_{H} (x, \overline{x}) = 1$ and ${dist}_{H} (y, \overline{y}) = 1$ .
Definition 3.
Let Σ be a k-ary alphabet, $f \in Σ^{n}$ , and q be an integer, $1 ⩽ q ⩽ n - 1$ . The word f has a q-Ham-error (q-Lee-error, resp.) overlap* of length l, $1 ⩽ l ⩽ n - 1$ , if ${dist}_{H} ({pre}_{l} (f), {suf}_{l} (f)) = q$ ( ${dist}_{L} ({pre}_{l} (f), {suf}_{l} (f)) = q$ , resp.). Its shift is $r = n - l$ ; its error positions are the m positions in ${pre}_{l} (f)$ , $1 ⩽ m ⩽ q$ , where ${pre}_{l} (f)$ differs from ${suf}_{l} (f)$ .

Figure 1.
The word f and its 2-Ham-error overlap of length l and shift r.
Example 3.
Let $f = 0101111$ in ${0, 1}^{*}$ ; the reader can refer to Fig. 2. The word f has two 2-Ham-error overlaps. The first one has length $l = 4$ , shift $r = 3$ , number of error positions $m = 2$ and error positions $i = 1$ , $j = 3$ . The second one has length $l^{'} = 3$ , shift $r^{'} = 4$ , number of error positions $m = 2$ and error positions $i = 1$ , $j = 3$ .

Figure 2.
The word $f = 0101111$ and its 2-Ham-error overlaps in Example 3.
Remark 3.
Using the notations in the previous definition, if f has a q-Ham-error overlap of length l, then $m = q$ . Otherwise, if f has a q-Lee-error overlap of length l, then $1 ⩽ m ⩽ l, q$ . In particular, when $k = 4$ and $q = 2$ , then $m = 1$ or $m = 2$ . The case $m = 1$ holds if ${pre}_{l} (f)$ and ${suf}_{l} (f)$ differ in exactly one position and the error is given by a pair of complementary symbols. For example, $f = AGAC \in Δ^{4}$ has a 2-Lee-error overlap of length $l = 2$ . Indeed, $m = 1$ and ${dist}_{L} (AG, AC) = 2$ .

If $m = 2$ then ${pre}_{l} (f)$ and ${suf}_{l} (f)$ differ in two different positions i and j and the errors are given by pairs of non-complementary symbols. For example, $f = CAAC \in Δ^{4}$ has a 2-Lee-error overlap of length $l = 2$ . Indeed, $m = 2$ and ${dist}_{L} (CA, AC) = 2$ .

Next theorem, proved in the binary case in [16] and in [3,4] for the general case, provides a characterization of Ham- and Lee-isometric words, which is fundamental to test whether a word is Ham- or Lee-isometric. Furthermore, it allows us to restrict the investigation on Lee-isometric words to k-ary alphabets with $k = 2, 3, 4$ .
Theorem 1 ([3,4,16]).

Let Σ be a k-ary alphabet and $f \in Σ^{*}$ .

f is Ham-isometric if and only if it has no 2-Ham-error overlap.

f is Lee-isometric if and only if it has no 2-Lee-error overlap, when $k = 2, 3, 4$ .

f is never Lee-isometric, when $k > 4$ .

The proof of Theorem 1 is constructive. Indeed, if f has a 2-Ham-error overlap, the proof explicitly provides a pair of Ham-witnesses for f, while if $k = 4$ and f has a 2-Lee-error overlap, the proof suggests a pair of Lee-witnesses for f going through its binary representation.

3. Computing the Ham- and the Lee-index

The index of a non-isometric word has been introduced as the threshold on the length of words that witness the “non-isometricity” of the word. In this section, we are going to show some results on how computing the index and some “minimal” pairs of witnesses for a non-isometric word. The investigation is carried on isometricity defined in terms of both the Hamming distance and the Lee distance, and on k-ary alphabets with any $k ⩾ 2$ . The results prove the correctness of the algorithms in Section 5.

The computation of the index is based on the construction of some pairs of witnesses for f, as given in [3,4] to show Theorem 1. The construction generalizes the one given in [18] for binary words with Hamming distance. It will turn out that the index is the minimal length of such witnesses. Let us revisit the construction, while highlighting some valuable features and adding some new results. First, let us state the following definitions. Refer to Figs 3 and 4 for the construction of $α_{r} (f)$ , $β_{r} (f)$ , $η_{r} (f)$ , and $γ_{r} (f)$ , where $x, \overline{x}, y, \overline{y}, z \in Σ$ are symbols such that ${dist}_{H} (x, \overline{x}) = 1$ and ${dist}_{H} (y, \overline{y}) = 1$ .

Definition 4.
Let Σ be a k-ary alphabet and $f \in Σ^{n}$ have a 2-Ham-error (2-Lee-error, resp.) overlap of shift r and error positions i, j, with $1 ⩽ i < j ⩽ n - r$ . Then,
$f^{(i)}$ is the word obtained from f replacing $f [i]$ by $f [r + i]$ .

if r is even and $t = j + r / 2$ , then $f^{(j, t)}$ is the word obtained from f replacing $f [j]$ with $f [r + j]$ , and $f [t]$ by $f [i]$ .
The words $α_{r} (f)$ , $β_{r} (f)$ , $η_{r} (f)$ , and $γ_{r} (f)$ corresponding to the 2-Ham-error (2-Lee-error, resp.) overlap of f of shift r are
$α_{r} (f) = {pre}_{r} (f) f^{(i)}$ and $β_{r} (f) = {pre}_{r} (f) f^{(j)}$ .

if r is even, $η_{r} (f) = {pre}_{r} (f) f^{(i)} {suf}_{r / 2} (f)$ and $γ_{r} (f) = {pre}_{r} (f) f^{(j, t)} {suf}_{r / 2} (f)$ .

Figure 3.
The words $α_{r} (f)$ and $β_{r} (f)$ corresponding to the 2-Ham-error overlap of shift r in Fig. 1.
Definition 5.
Let Σ be a k-ary alphabet and $f \in Σ^{n}$ have a 2-Lee-error overlap of shift r and error positions i, j, with $1 ⩽ i = j ⩽ n - r$ . Then,
$f^{(i, -)}$ is the word obtained from f replacing $f [i]$ with $(f [i] - 1) mod k$

$f^{(i, +)}$ is the word obtained from f replacing $f [i]$ with $(f [i] + 1) mod k$ .
The words $φ_{r} (f)$ and $ψ_{r} (f)$ corresponding to the 2-Lee-error overlap of f of shift r are
$φ_{r} (f) = {pre}_{r} (f) f^{(i, -)}$ and $ψ_{r} (f) = {pre}_{r} (f) f^{(i, +)}$

Figure 4.
The words $η_{r} (f)$ and $γ_{r} (f)$ where $f [i] = x$ , $f [j] = y$ and $f [t] = z$ .

The words introduced in the previous definitions will be useful to determine some pairs of witnesses for a non-isometric word f (cf. Propositions 2 and 3). In fact, if f has a 2-Ham-error overlap or a 2-Lee-error overlap with two (distinct) error positions, then the “standard” pair of witnesses for f is $(α_{r} (f), β_{r} (f))$ . However, $β_{r} (f)$ may not be f-free; in this case, it becomes necessary to consider the pair $(η_{r} (f), γ_{r} (f))$ . More exactly, it turns out that $β_{r} (f)$ contains f as a factor if and only if the following ${Condition}^{+}$ holds [3]. On the contrary, the pair ( $φ_{r} (f)$ , $ψ_{r} (f)$ ) is used when the 2-Lee-error overlap has two coincident error positions.
Definition 6.
Let Σ be a k-ary alphabet and $f \in Σ^{n}$ have a 2-Ham-error overlap (2-Lee-error overlap, resp.) of shift r and error positions i, j, with $1 ⩽ i < j ⩽ n - r$ . The 2-Ham-error overlap (2-Lee-error overlap, resp.) satisfies ${Condition}^{+}$ if $\begin{matrix} \{\begin{array}{l} r is even \\ j - i = r / 2 \\ f [r + i] = f [r + j] \\ f [i \dots i + r / 2 - 1] = f [j \dots j + r / 2 - 1] \end{array} ({Condition}^{+}) \end{matrix}$
Proposition 1.
Let Σ be a k-ary alphabet and $f \in Σ^{n}$ have a 2-Ham-error overlap (2-Lee-error overlap, resp.) of shift r and error positions i, j, with $1 ⩽ i < j ⩽ n - r$ .

The following statements are equivalent
$β_{r} (f)$ is not f-free

the 2-Ham-error overlap (2-Lee-error overlap, resp.) of shift r satisfies ${Condition}^{+}$

$f = ρ {(x w)}^{k_{1}} x w x w \overline{x} w \overline{x} {(w \overline{x})}^{k_{2}} σ$ for some word $w \in Σ^{r / 2 - 1}$ , ρ suffix of w and σ prefix of w, symbols $x, \overline{x} \in Σ$ , with ${dist}_{H} (x, \overline{x}) = 1$ ( ${dist}_{L} (x, \overline{x}) = 1$ , resp.), and integers $k_{1}, k_{2} ⩾ 0$ .

Proof.
The proof is given only for 2-Ham-error overlaps. The case of 2-Lee-error overlaps is analogous; just replace the Hamming distance with the Lee distance.

(1. ⇒ 2.)

The proof goes analogously to the proof of Claim 2 of Lemma 2.2 in [18]. Assume that $β_{r} (f)$ is not f-free and denote the copy of f that occurs in $β_{r} (f)$ as $f^{b}$ . Suppose $f^{b}$ occurs at position $r_{1} + 1$ and let $r_{2} = r - r_{1}$ . Let $f [i] = x$ , $f [i + r] = \overline{x}$ , $f [j] = y$ and $f [j + r] = \overline{y}$ with ${dist}_{H} (x, \overline{x}) = 1$ and ${dist}_{H} (y, \overline{y}) = 1$ .

Suppose $j - i \neq r_{1}$ . One has $x = f [i] = f^{b} [i] = β_{r} (f) [r_{1} + i] = f [r_{1} + i]$ . And $\overline{x} = f [i + r] = f^{b} [i + r_{1} + r_{2}] = f^{(j)} [i + r_{1}] = f [i + r_{1}]$ , this last equality holding since $i + r_{1} \neq j$ .

Suppose, now, $j - i \neq r_{2}$ . One has $y = f [j] = f^{b} [j] = β_{r} (f) [r_{1} + j] = f [r_{1} + j]$ , this last equality holding since $i + r_{2} \neq j$ . And $\overline{y} = f [j + r] = f [j + r_{1} + r_{2}] = [j + f^{(j)} r_{1}] = f [j + r_{1}]$ .

Hence $j - i = r_{1}$ and $j - i = r_{2}$ , that is $j - i = r_{1} = r_{2}$ , $r = 2 r_{1}$ is even and $j - i = r / 2$ . Therefore, $f [i + t] = f^{b} [i + t] = f [i + t + r / 2] = f [j + t]$ , for $t = r$ and $0 ⩽ t ⩽ r / 2$ .

(2. ⇒ 3.)

The proof goes analogously to the proof of Lemma 2.1 in [19]. Suppose that the 2-Ham-error overlap of length l, shift $r = n - l$ and error positions i, j, with $1 ⩽ i < j ⩽ l$ satisfies ${Condition}^{+}$ . Let $f [i] = f [j] = x$ and $f [i + r] = f [j + r] = \overline{x}$ . Since $1 ⩽ r ⩽ n - 2$ , then $n - j ⩾ r$ . Let us divide $i - 1$ and $n - j$ by $r / 2$ . Assume that $i - 1 = k_{1} r / 2 + q$ and $n - j = (k_{2} + 2) r / 2 + p$ , where $k_{1}, k_{2} ⩾ 0$ , $0 ⩽ q < r / 2$ and $0 ⩽ p < r / 2$ . Then $n = (k_{1} + k_{2} + 3) r / 2 + q + p + 1$ , $l = n - r = (k_{1} + k_{2} + 1) r / 2 + q + p + 1$ , and by the equalities in ${Condition}^{+}$ it holds: $\begin{array}{c} f [h] = f [h + r / 2] for h \in {1, \dots, n - r / 2} ∖ {i - k_{1} r / 2, \dots, i, j, j + r / 2, \dots, j + (k_{2} + 2) r / 2}, \\ f [h] = x for h \in {i - k_{1} r / 2, \dots, i, j} and \\ f [h] = \overline{x} for h \in {j + r / 2, \dots, j + (k_{2} + 2) r / 2)} . \end{array}$ Denote by w the factor of f from position $(i + 1)$ to position $(j - 1)$ (if $j - 1 = 1$ then w is empty), $ρ = {suf}_{q} (w)$ and $σ = {pre}_{p} (w)$ . Then $| w | = r / 2 - 1$ and $f = ρ {(x w)}^{k_{1}} x w x w \overline{x} w \overline{x} {(w \overline{x})}^{k_{2}} σ$ .

(3. ⇒ 1.)

Suppose that $f = ρ {(x w)}^{k_{1}} x w x w \overline{x} w \overline{x} {(w \overline{x})}^{k_{2}} σ$ for some word $w \in Σ^{r / 2 - 1}$ , ρ suffix of w and σ prefix of w, symbols $x, \overline{x} \in Σ$ , with ${dist}_{H} (x, \overline{x}) = 1$ and integers $k_{1}, k_{2} ⩾ 0$ . The structure of f implies that f has a 2-Ham-error overlap of shift $r = 2 (| w | + 1)$ with error positions $i = | ρ | + k_{1} r / 2 + 1$ and $j = i + r / 2 = | ρ | + (k_{1} + 1) r / 2 + 1$ .

Consider the corresponding word $β_{r} (f)$ . From Definition 4, $β_{r} (f) = {pre}_{r} (f) f^{(j)}$ and, hence, $β_{r} (f) = ρ (x w) (x w) {(x w)}^{k_{1}} x w \overline{x} w \overline{x} w \overline{x} {(w \overline{x})}^{k_{2}} σ$ . Therefore, f occurs in $β_{r} (f)$ starting from position $r / 2 + 1$ and $β_{r} (f)$ is not f-free. □

The following lemma states an upper bound on the number of 2-error overlaps that satisfy ${Condition}^{+}$ for a non-isometric word. It will be useful in some subsequent proofs.
Lemma 1.
Let Σ be a k-ary alphabet with $k ⩾ 2$ and let $f \in Σ^{}$ be a Ham-non-isometric word (Lee-non-isometric, resp.). Then f has at most one* 2-Ham-error (2-Lee-error, resp.) overlap that satisfies ${Condition}^{+}$ .
Proof.
Assume by contradiction that f has two different 2-Ham-error (2-Lee-error, resp.) overlaps that satisfy ${Condition}^{+}$ . Then, by Proposition 1, there exist $w_{i}, ρ_{i}, σ_{i} \in Σ^{*}$ , $k_{i}, h_{i} ⩾ 0$ ( $i = 1, 2$ ), $x, \overline{x}, y, \overline{y} \in Σ$ , ${dist}_{H} (x, \overline{x}) = 1$ ( ${dist}_{L} (x, \overline{x}) = 1$ , resp.) and ${dist}_{H} (y, \overline{y}) = 1$ ( ${dist}_{L} (y, \overline{y}) = 1$ , resp.), such that f has two different representation forms: $\begin{array}{c} f^{'} = ρ_{1} {(x w_{1})}^{k_{1}} x w_{1} x w_{1} \overline{x} w_{1} \overline{x} {(w_{1} \overline{x})}^{k_{2}} σ_{1} and f^{″} = ρ_{2} {(y w_{2})}^{h_{1}} y w_{2} y w_{2} \overline{y} w_{2} \overline{y} {(w_{2} \overline{y})}^{h_{2}} σ_{2} \end{array}$ where $ρ_{i}$ ( $σ_{i}$ , resp.) ( $i = 1, 2$ ) is a suffix (a prefix, resp.) of $w_{i}$ .

Some considerations analogous to the ones used in the proof of Lemma 4.2 in [19], show that necessarily $| ρ_{1} | = | ρ_{2} |$ and $| w_{1} | = | w_{2} |$ . Hence, it holds $ρ_{1} = ρ_{2}$ , $w_{1} = w_{2}$ , $x = y$ , and $f^{'}$ and $f^{″}$ are the same representation form of f. □

Consider a Ham-non-isometric word $f \in Σ^{n}$ . Then, f has a 2-Ham-error overlap. Actually, it may have several 2-Ham-error overlaps. Next proposition shows that for any 2-Ham-error overlap of f there is a corresponding pair of Ham-witnesses for f.
Proposition 2 ([3]).

Let f be a Ham-non-isometric k-ary word. Consider a 2-Ham-error overlap of f, of shift r, and error positions i, j, with $1 ⩽ i < j ⩽ n - r$ .

If the 2-Ham-error overlap does not satisfy ${Condition}^{+}$ then $(α_{r} (f), β_{r} (f))$ is a pair of witnesses for f

If the 2-Ham-error overlap satisfies ${Condition}^{+}$ and $1 ⩽ i ⩽ r / 2$ then $(η_{r} (f), γ_{r} (f))$ is a pair of witnesses for f

If the 2-Ham-error overlap satisfies ${Condition}^{+}$ and $i > r / 2$ then f has a 2-Ham-error overlap of shift $r^{'} > r$ , which does not satisfy ${Condition}^{+}$ and $(α_{r^{'}} (f), β_{r^{'}} (f))$ is a pair of witnesses for f.

Remark 4.
Let us explicit the value of the shift $r^{'}$ , as stated in item 3 of Proposition 2. Referring to the proof of 2. ⇒ 3. in Proposition 1, $r^{'}$ is given by $r^{'} = (k_{1} + k_{2} + 2) r / 2$ .

Let us show some examples of the construction in Proposition 2 for a ternary and a binary alphabet, respectively.
Example 4.
Consider the ternary alphabet $Σ = {0, 1, 2}$ . Let $f = 021 \in Σ^{3}$ . The word f has a 2-Ham-error overlap of shift $r = 1$ . Hence, $f = 021$ is Ham-non-isometric from Theorem 1. Following Proposition 2, let us exhibit a pair $(α_{r} (f), β_{r} (f))$ of Ham-witnesses for f. We have that ${pre}_{2} (f)$ disagrees from ${suf}_{2} (f)$ in positions $i = 1$ and $j = 2$ , and $f [i] = 0$ , $f [j] = 2$ , $f [r + i] = 2$ and $f [r + j] = 1$ . Then, $α_{r} (f) = {pre}_{r} (f) f^{(i)} = 0221$ and $β_{r} (f) = {pre}_{r} (f) f^{(j)} = 0011$ . The words $α_{r} (f)$ and $β_{r} (f)$ are f-free words and ${dist}_{H} (α_{r} (f), β_{r} (f)) = 2$ . Moreover, there is no f-free Ham-transformation from $α_{r} (f)$ to $β_{r} (f)$ of length ${dist}_{H} (α_{r} (f), β_{r} (f)) = 2$ . Indeed, if $α_{r} (f) [2]$ is replaced by $β_{r} (f) [2] = 0$ then f occurs in $α_{r} (f)$ at position 2; if $α_{r} (f) [3]$ is replaced by $β_{r} (f) [3] = 1$ then f occurs at position 1.
Example 5.
Consider the binary alphabet $B = {0, 1}$ . Let $f = 0011 \in B^{4}$ . The word f has a 2-Ham-error overlap of shift $r = 2$ . Hence, $f = 0011$ is Ham-non-isometric from Theorem 1. Note that the 2-Ham-error overlap of f satisfies ${Condition}^{+}$ . Indeed, we have $i = 1$ , $j = 2$ , $r = 2$ , $f [r + i] = f [3] = 1 = f [4] = f [r + j]$ and $f [i] = 0 = f [j]$ . Therefore, following Proposition 2, item 2., set $t = (r / 2) + j = 3$ and consider the two words $η_{r} (f) = {pre}_{r} (f) f^{(i)} {suf}_{r / 2} (f) = 0010111$ and $γ_{r} (f) = {pre}_{r} (f) f^{(j, t)} {suf}_{r / 2} (f) = 0001011$ . The words $η_{r} (f)$ and $γ_{r} (f)$ are f-free words and ${dist}_{H} (η_{r} (f), γ_{r} (f)) = 3$ . Moreover, there is no f-free Ham-transformation from $η_{r} (f)$ to $γ_{r} (f)$ of length ${dist}_{H} (η_{r} (f), γ_{r} (f)) = 3$ . Indeed, if $η_{r} (f) [3]$ is replaced by $γ_{r} (f) [3] = 0$ then f occurs in $η_{r} (f)$ at position 3; if $η_{r} (f) [4]$ is replaced by $γ_{r} (f) [4] = 1$ then f occurs at position 1 and if $η_{r} (f) [5]$ is replaced by $γ_{r} (f) [5] = 0$ then f occurs at position 4.

Let us now consider Lee-non-isometric words.
Remark 5.
Consider the case $k = 2, 3$ . According to Remark 2, for any $u, v \in Σ^{}$ words of same length, ${dist}_{L} (u, v) = {dist}_{H} (u, v)$ and any Lee-transformation from u to v is itself a Ham-transformation, and vice versa, thus preserving length and f-freeness. Hence, Proposition 2 allows also to construct some pairs of Lee-witnesses for a Lee-non-isometric binary or ternary word f. Namely, it is possible to associate a pair of Lee-witnesses for f with any 2-Lee-error overlap of f. Note that, in this case, any 2-Lee-error overlap of f is given by two distinct error positions. This is no more true when $k = 4$ . The case $k = 4$ is considered in what follows.

Consider the case of $k = 4$ and the quaternary alphabet $Δ = {A, C, T, G}$ . The construction of a pair of Lee-witnesses for a Lee-non-isometric quaternary word f is obtained in [3] referring to the binary representation of f. Actually, there is an isomorphism between quaternary words and binary words of even length. It is given by the map which associates to A, C, T, G, the binary words 00, 01, 11, 10, respectively. Hence, a word $f \in Δ^{n}$ will be possibly denoted as ${(f)}_{4}$ to stress its belonging to the quaternary alphabet, while its binary representation in ${0, 1}^{2 n}$ will be denoted as ${(f)}_{2}$ . The correspondence preserves the Lee distance.

Let ${(f)}_{4} \in Δ^{n}$ be a Lee-non-isometric word, r be the shift of a 2-Lee-error overlap of ${(f)}_{4}$ and m the number of its error positions. Recall that $m = 1$ or $m = 2$ ; see Remark 3. Note that ${(f)}_{2}$ has a 2-Lee-error overlap of shift $2 r$ . A pair of Lee-witnesses for ${(f)}_{4}$ is obtained in [3,4] considering a pair of Lee-witnesses for ${(f)}_{2}$ , constructed as in Proposition 2, and representing it in quaternary. Recall that ${(A)}_{2} = 00$ , ${(C)}_{2} = 01$ , ${(T)}_{2} = 11$ , and ${(G)}_{2} = 10$ . For example, if the 2-Lee-error overlap of shift $2 r$ of ${(f)}_{2}$ fills case 1 of Proposition 2 then $(α_{2 r} ({(f)}_{2}), β_{2 r} ({(f)}_{2}))$ is a pair of witnesses for ${(f)}_{2}$ . Thus, the quaternary representation of this pair of witnesses for ${(f)}_{2}$ , that is $({(α_{2 r} ({(f)}_{2}))}_{4}, {(β_{2 r} ({(f)}_{2}))}_{4})$ , is a pair of Lee-witnesses for ${(f)}_{4}$ .

Next proposition shows that, indeed, the pair of Lee-witnesses for ${(f)}_{4}$ as just obtained from a 2-Lee-error overlap can be directly constructed from ${(f)}_{4}$ , without going through its binary representation. Therefore, let us simply denote by f the quaternary word. Example 6 shows both constructions.
Proposition 3.
Let f be a Lee-non-isometric k-ary word,* $k = 4$ . Consider a 2-Lee-error overlap of f of shift r and m error positions i, j, with $1 ⩽ i ⩽ j ⩽ n - r$ ( $i = j$ iff $m = 1$ ).
If $m = 1$ , then $(φ_{r} (f), ψ_{r} (f))$ is a pair of Lee-witnesses for f.

If $m = 2$ then

if the 2-Lee-error overlap does not satisfy ${Condition}^{+}$ , then $(α_{r} (f), β_{r} (f))$ is a pair of Lee-witnesses for f

if the 2-Lee-error overlap satisfies ${Condition}^{+}$ and $i ⩽ r / 2$ , then $(η_{r} (f), γ_{r} (f))$ is a pair of Lee-witnesses for f

if the 2-Lee-error overlap satisfies ${Condition}^{+}$ and $i > r / 2$ , then f has a 2-Lee-error overlap of shift $r^{'} > r$ , which does not satisfy ${Condition}^{+}$ and $(α_{r^{'}} (f), β_{r^{'}} (f))$ is a pair of Lee-witnesses for f.

Proof.
Consider ${(f)}_{2}$ , the binary representation of f. Since f has a 2-Lee-error overlap of shift r, then ${(f)}_{2}$ has a 2-Lee-error overlap of shift $2 r$ with error positions s, z and $s < z$ .

In the case $m = 1$ , we have that $i = j$ and that $f [i]$ and $f [r + i]$ are two complementary symbols. Moreover, we have $s = 2 i - 1$ and $z = s + 1 = 2 i$ . Suppose $f [i] = A$ and $f [r + i] = T$ ; the other cases can be treated analogously. We have ${(f)}_{2} [s] = 0$ , ${(f)}_{2} [2 r + s] = 1$ , ${(f)}_{2} [z] = 0$ , ${(f)}_{2} [2 r + z] = 1$ . Therefore, the quaternary representation of ${(f)}_{2}^{(s)}$ ( ${(f)}_{2}^{(z)}$ , resp.) coincides with the word obtained from f by replacing the symbol A in position i with the symbol G (C, resp.), that is ${({(f)}_{2}^{(s)})}_{4} = f^{(i, -)}$ ( ${({(f)}_{2}^{(z)})}_{4} = f^{(i, +)}$ ), resp.). Moreover, ${pre}_{2 r} ({(f)}_{2})$ , represented in the quaternary alphabet, coincides with ${pre}_{r} (f)$ . Hence, ${(α_{2 r} ({(f)}_{2}))}_{4} = {pre}_{r} (f) f^{(i, -)}$ and ${(β_{2 r} ({(f)}_{2}))}_{4} = {pre}_{r} (f) f^{(i, +)}$ . In [3], it is proved that the quaternary representation of $(α_{2 r} ({(f)}_{2}), β_{2 r} ({(f)}_{2}))$ is a pair of Lee-witnesses for f. Hence, the thesis follows.

In the case $m = 2$ , we have that $i < j$ , $f [i]$ and $f [r + i]$ ( $f [j]$ and $f [r + j]$ , resp.) differ because of two non-complementary symbols.
If the 2-Lee-error overlap does not satisfy ${Condition}^{+}$ then the quaternary representation of ( $α_{2 r} ({(f)}_{2})$ , $β_{2 r} ({(f)}_{2})$ ) is a pair of Lee-witnesses for f; see [4]. Suppose $f [i] = T$ , $f [r + i] = C$ , $f [j] = G$ and $f [r + j] = A$ ; the other cases can be treated analogously. We have $s = 2 i - 1$ and $z = 2 j - 1$ , ${(f)}_{2} [s] = 1$ , ${(f)}_{2} [2 r + s] = 0$ , ${(f)}_{2} [z] = 1$ , ${(f)}_{2} [2 r + z] = 0$ . Therefore, ${(f)}_{2}^{(s)}$ ( ${(f)}_{2}^{(z)}$ , resp.), represented in the quaternary alphabet, coincides with the word obtained from f by replacing T (G, resp.) in position i (j, resp.) with C (A, resp.), that is ${({(f)}_{2}^{(s)})}_{4} = f^{(i)}$ ( ${({(f)}_{2}^{(z)})}_{4} = f^{(j)}$ , resp.). Moreover, ${pre}_{2 r} ({(f)}_{2})$ , represented in the quaternary alphabet, coincides with ${pre}_{r} (f)$ and the thesis follows.

If the 2-Lee-error overlap of f of shift r satisfies ${Condition}^{+}$ and $i ⩽ r / 2$ then the 2-Lee-error overlap of ${(f)}_{2}$ of shift $2 r$ satisfies ${Condition}^{+}$ . The proof is given for $f [i] = f [j] = A$ and $f [r + i] = f [r + j] = C$ ; the other cases can be treated analogously. Then, $s = 2 i$ and $z = 2 j$ . Since the 2-Lee-error overlap of f of shift r satisfies ${Condition}^{+}$ , then r is even, $j - i = r / 2$ . Therefore, $z - s = 2 (j - i) = r$ is even and it is equal to the half of $2 r$ , the shift of the 2-Lee-error overlap of ${(f)}_{2}$ . Moreover, from $f [r + i] = f [r + j]$ and $f [i \dots i + r / 2 - 1] = f [j \dots j + r / 2 - 1]$ , it follows $f [2 r + s] = f [2 r + z]$ and $f [s \dots s + r - 1] = f [z \dots z + r - 1]$ . At last, $i ⩽ r / 2$ , implies $s ⩽ r$ . In this case, from [4], $η_{2 r} ({(f)}_{2})$ , $γ_{2 r} ({(f)}_{2})$ , represented in the quaternary alphabet, is a pair of Lee-witnesses for f. Recall that $η_{2 r} ({(f)}_{2}) = {pre}_{2 r} ({(f)}_{2}) {(f_{2})}^{(s)} {suf}_{r / 2} ({(f)}_{2})$ and $γ_{2 r} ({(f)}_{2}) = {pre}_{2 r} ({(f)}_{2}) {(f_{2})}^{(z, t)} {suf}_{r / 2} ({(f)}_{2})$ . Then, ${({(f)}_{2})}^{(s)}$ will be obtained from ${(f)}_{2}$ by replacing ${(f)}_{2} [s] = 0$ with ${(f)}_{2} [2 r + s] = 1$ . Therefore, its quaternary representation coincides with the word obtained from f by replacing A in position i with C, that is ${({(f)}_{2}^{(s)})}_{4} = f^{(i)}$ . Analogous considerations show that ${(η_{2 r} ({(f)}_{2}))}_{4} = {pre}_{r} (f) f^{(i)} {suf}_{r / 2} (f)$ and ${(γ_{2 r} ({(f)}_{2}))}_{4} = {pre}_{r} (f) f^{(j, t)} {suf}_{r / 2} (f)$ and the thesis follows.

This case can be treated as case a. Indeed, if the 2-Lee-error overlap of f of shift r satisfies ${Condition}^{+}$ and $i > r / 2$ , it can be shown that f has another 2-Lee-error overlap, of shift $r^{'} > r$ , that does not satisfy ${Condition}^{+}$ . In particular, $r^{'} = (k_{1} + k_{2} + 2) r / 2$ where $k_{1}, k_{2} ⩾ 0$ are such that $i - 1 = k_{1} r / 2 + q$ and $n - j = (k_{2} + 2) r / 2 + p$ , for some $0 ⩽ q < r / 2$ and $0 ⩽ p < r / 2$ . □

Example 6.
Let ${(f)}_{4} = AGCT \in Δ^{}$ and, hence, ${(f)}_{2} = 00100111 \in {(B^{2})}^{}$ . Then, ${(f)}_{4}$ has a 2-Lee-error overlap of length $l = 1$ and shift $r = 3$ . In this case $m = 1$ and $i = 1$ is the unique error position with ${(f)}_{4} [1] = A$ and ${(f)}_{4} [4] = T$ , that is the error is caused by two complementary symbols. A pair of witnesses for ${(f)}_{4}$ can be constructed from a pair of witnesses for ${(f)}_{2}$ , as follows. Consider the 2-Lee-error overlap of ${(f)}_{2}$ of even length $2 l = 2$ and shift $2 r = 6$ . It is caused by two different error positions, $s = 1$ and $z = 2$ , since ${(f)}_{2} [1] = {(f)}_{2} [2] = 0$ , while ${(f)}_{2} [7] = {(f)}_{2} [8] = 1$ . Starting from this 2-Lee-error overlap of ${(f)}_{2}$ , the pair $(α_{6} ({(f)}_{2}), β_{6} ({(f)}_{2}))$ of Lee-witnesses for ${(f)}_{2}$ can be obtained. The pair is composed of $α_{6} ({(f)}_{2}) = 00100110100111$ and $β_{6} ({(f)}_{2}) = 00100101100111$ . In this case, the 2-Lee-error overlap of ${(f)}_{2}$ does not satisfy ${Condition}^{+}$ , since $z - s = 1$ is different from $r = 3$ . Therefore, coming back to the quaternary representation, $({(α_{6} ({(f)}_{2}))}_{4}, {(β_{6} ({(f)}_{2}))}_{4}) = (AGCGGCT, AGCCGCT)$ is a pair of Lee-witnesses for ${(f)}_{4}$ .

On the other hand, this pair of witnesses for $AGCT$ can be directly constructed from $AGCT$ , without going through the binary representation. Following Proposition 3 in the case $m = 1$ , $φ_{3} (f) = {pre}_{3} (f) f^{(1, -)}$ , $ψ_{3} (f) = {pre}_{3} (f) f^{(1, +)}$ . Observe that $f^{(1, -)} = GGCT$ and $f^{(1, +)} = CGCT$ . Hence, $φ_{3} (f) = {pre}_{3} (f) f^{(1, -)} = AGC GGCT$ and $ψ_{3} (f) = {pre}_{3} (f) f^{(1, +)} = AGC CGCT$ . Finally, $(φ_{3} (AGCT), ψ_{3} (AGCT)) = (AGCGGCT, AGCCGCT)$ is the same pair of Lee-witnesses for ${(f)}_{4}$ , as previously computed using the binary representation.

Let us come back to the computation of the index of a non-isometric word f. Propositions 2 and 3 show how to construct some pairs of witnesses for f, referring to the Hamming distance and to the Lee distance, respectively. Next Theorems 2 and 3 prove that such pairs of witnesses are in some sense the minimal ones and that the index can be obtained as the minimum length of such witnesses.

First, observe that Proposition 2 (Proposition 3, resp.) allows to restate in the next corollary some bounds on the Ham-index (Lee-index, resp.) of a Ham-non-isometric (Lee-non-isometric, resp.) word f, already given in [20] for the binary case and in [3] for the general case. Just observe that $| α_{r} (f) | = | β_{r} (f) | = | φ_{r} (f) | = | ψ_{r} (f) | = n + r$ , $| η_{r} (f) | = | γ_{r} (f) | = n + 3 r / 2$ , $1 ⩽ r ⩽ n - 1$ and $r = n - 1$ can hold only in case of a 2-Lee-error overlap of a quaternary word with an error caused by two complementary symbols.
Corollary 1.
Let Σ be a k-ary alphabet and let $f \in Σ^{n}$ . If f is a Ham-non-isometric word, then the Ham-index of f satisfies $n + 1 ⩽ I_{H} (f) ⩽ 2 n - 1$ . If $k = 2, 3, 4$ and f is a Lee-non-isometric word, then the Lee-index of f satisfies $n + 1 ⩽ I_{L} (f) ⩽ 2 n - 1$ .
Lemma 2.
Let Σ be a k-ary alphabet, $f \in Σ^{n}$ be a Ham-non-isometric word and $(u, v)$ be a pair of Ham-witnesses for f of minimal ${dist}_{H} (u, v)$ among all Ham-witnesses for f of minimum length. Let V be the set of all the positions where u and v differ and, for any $i \in V$ , let $R_{i} (u)$ be the word obtained from u by replacing $u [i]$ with $v [i]$ .

Then, for any $i \in V$ , f is a factor of $R_{i} (u)$ .

Moreover, denoted by ${Int}_{i}$ the interval of positions covered by f in $R_{i} (u)$ , there exist $s, t \in V$ , such that both ${Int}_{s}$ and ${Int}_{t}$ contain s and t.
Proof.
Let $(u, v)$ be a pair of Ham-witnesses for f of minimal length $d = | u | = | v |$ . Let $h = {dist}_{H} (u, v)$ and suppose $(u, v)$ are chosen so that h is minimal among all pairs of Ham-witnesses for f of length d. Let $V = {i_{1}, i_{2}, \dots, i_{h}}$ , with $1 ⩽ i_{1} < i_{2} < \dots < i_{h} ⩽ d$ , be the set of all the positions where u and v differ. Let us show that for any $i \in V$ , f is a factor of $R_{i} (u)$ . In fact, if $R_{i} (u)$ were f-free then the pair $(R_{i} (u), v)$ would be a pair of Ham-witnesses for f of length d and ${dist}_{H} (R_{i} (u), v) < h$ contradicts the minimality of h.

Observe that ${Int}_{i}$ contains i, because u is f-free. Moreover, it must contain at least another position in V, so that v could be f-free; let $p (i)$ denote the smallest of such positions in ${Int}_{i}$ . Note that $p (i)$ can be smaller or greater than i. However, for the first and the last error positions, one necessarily has that $p (i_{1}) > i_{1}$ whereas $p (i_{h}) < i_{h}$ . Let $i_{m}$ be the smallest position in V, such that $p (i_{m}) < i_{m}$ ; then $p (i_{m - 1}) > i_{m - 1}$ , with $2 ⩽ m ⩽ h$ .

Since ${Int}_{i_{m}}$ contains $i_{m}$ and $p (i_{m})$ , with $p (i_{m}) < i_{m}$ , then ${Int}_{i_{m}}$ also contains $i_{m - 1}$ because $p (i_{m}) ⩽ i_{m - 1} < i_{m}$ ; recall that $i_{m - 1}$ and $i_{m}$ are consecutive error positions, no other error position can lay in between. Similarly, $i_{m - 1} < i_{m} ⩽ p_{i_{m - 1}}$ . Finally, ${Int}_{i_{m}}$ and ${Int}_{i_{m - 1}}$ both contain $i_{m - 1}$ and $i_{m}$ and therefore they can play the role of ${Int}_{s}$ and ${Int}_{t}$ in the statement. □
Theorem 2.
Let f be a Ham-non-isometric k-ary word and $(u, v)$ be a pair of Ham-witnesses for f of minimal distance ${dist}_{H} (u, v)$ among all Ham-witnesses for f of minimal length. Then $(u, v)$ , or $(v, u)$ , is equal to $(α_{r} (f), β_{r} (f))$ or to $(η_{r} (f), γ_{r} (f))$ , for some r that is the shift of a 2-Ham-error overlap of f.
Proof.
Let f be a Ham-non-isometric k-ary word and $| f | = n$ . Let $(u, v)$ be a pair of Ham-witnesses of minimal distance ${dist}_{H} (u, v)$ among all Ham-witnesses of minimal length. By definition, $I_{H} (f) = | u |$ . Let V be the set of all error positions between u and v. For any position $i \in V$ let $R_{i} (u)$ be the word obtained from u replacing $u [i]$ with $v [i]$ . Lemma 2 states that f is a factor of $R_{i} (u)$ ; let ${Int}_{i}$ be the interval of positions covered by f in $R_{i} (u)$ . The minimality of the length of u implies that the union of all intervals ${Int}_{i}$ , for $i \in V$ , gives $[1 \dots n]$ . Let ${Int}_{i_{1}}$ be the interval that contains position 1 and ${Int}_{i_{2}}$ be the interval that contains position n. Note that positions $i_{1}$ , $i_{2}$ are not supposed to be in increasing order.

If ${Int}_{i_{1}}$ and ${Int}_{i_{2}}$ both contain positions $i_{1}$ and $i_{2}$ of u, then f has a 2-Ham-error overlap of shift $r = | u | - n$ and error positions $i_{1} - r$ and $i_{2} - r$ . Then, $| V | = 2$ , $u = {pre}_{r} (f) f^{(i_{1} - r)} = α_{r} (f)$ and $v = β_{r} (f)$ , or vice versa, and the claim is proved.

Otherwise, $| V | ⩾ 3$ . From Lemma 2, there exist $s, t \in V$ , such that ${Int}_{s}$ and ${Int}_{t}$ both contain s and t. This provides a 2-Ham-error overlap of f; let z be its shift. Consider the pair $(α_{z} (f), β_{z} (f))$ . Note that in this case ${s, t} \neq {i_{1}, i_{2}}$ and then position 1, or n, does not belong neither to ${Int}_{s}$ nor to ${Int}_{t}$ ; suppose it is n. Therefore, the length of $α_{z} (f)$ is strictly less than $| u |$ . The minimality of the length of u implies that $(α_{z} (f), β_{z} (f))$ cannot be a pair of Ham-witnesses for f. This can happen only if $β_{z} (f)$ is not f-free. Hence, $f = ρ {(x w)}^{k_{1}} x w x w \overline{x} w \overline{x} {(w \overline{x})}^{k_{2}} σ$ as stated in item 3. of Proposition 1, i.e. f shows a sort of “periodic decomposition”; furthermore, such a decomposition of f is unique (see Lemma 1). Consider now ${Int}_{s}$ , ${Int}_{t}$ , and ${Int}_{i_{2}}$ and suppose that ${Int}_{s}$ occurs before ${Int}_{t}$ . Interval ${Int}_{i_{2}}$ necessarily overlaps ${Int}_{s}$ (and ${Int}_{t}$ ) because $| u | = I_{H} (f) ⩽ 2 | f | - 1$ (see Corollary 1) and they overlap each other with the largest possible intersection since $| u |$ is minimal. Looking in detail at the periodic decomposition of f stated in Proposition 1, such largest intersection has length $n - 3 z / 2$ and finally $u = η_{s} (f)$ and $v = γ_{s} (f)$ . □
Corollary 2.
Let f be a Ham-non-isometric k-ary word. Then, the Ham-index of f, $I_{H} (f)$ , is the minimum length of words $α_{r} (f)$ or $η_{r} (f)$ , as appropriate, where r is taken over the shifts of all 2-Ham-error overlaps of f.
Theorem 3.
Let f be a Lee-non-isometric k-ary word, $k = 2, 3, 4$ , and $(u, v)$ be a pair of Lee-witnesses for f of minimal distance ${dist}_{L} (u, v)$ among all Lee-witnesses for f of minimal length. Then $(u, v)$ , or $(v, u)$ , is equal to $(α_{r} (f), β_{r} (f))$ , $(η_{r} (f), γ_{r} (f))$ , or to $(φ_{r} (f), ψ_{r} (f))$ .
Proof.
If $k = 2, 3$ , then the Lee-index equals the Ham-index (Remark 2) and Theorem 2 applies. Let $k = 4$ and f be a Lee-non-isometric k-ary word. Let $(u, v)$ be the pair of Lee-witnesses for f of minimal distance ${dist}_{L} (u, v)$ among all Lee-witnesses for f of minimal length. Then, $I_{L} (f) = | u |$ . Let V be the set of all error positions. If all errors are due to non-complementary symbols, then the proof follows as in the Ham-index case (Theorem 2).

Suppose now that there exists $i \in V$ such that $u [i]$ and $v [i]$ are complementary symbols. Then, $u [i]$ can be replaced in two different ways in a Lee-transformation from u to v, since there are two symbols at Lee-distance 1 from $u [i]$ . The minimality of the distance of u and v implies that the word obtained from u replacing $u [i]$ with any of the two symbols at Lee-distance 1, contains f as a factor. Then, position i is contained in two overlapping occurrences of f. Hence, f has a 2-Lee-error overlap with a unique error position; let r be its shift. Consider the words $φ_{r} (f)$ and $ψ_{r} (f)$ . Proposition 3 states that $(φ_{r} (f), ψ_{r} (f))$ is a pair of Lee-witnesses for f. Finally, $u = φ_{r} (f)$ and $v = ψ_{r} (f)$ , or vice versa. □
Corollary 3.
Let f be a Lee-non-isometric k-ary word, $k = 2, 3, 4$ . Then, the Lee-index of f, $I_{L} (f)$ , is the minimum length of words $α_{r} (f)$ , $η_{r} (f)$ , or $φ_{r} (f)$ , as appropriate, where r is taken over the shifts of all 2-Lee-error overlaps of f.

Corollaries 2 and 3 suggest to compute the index of a word considering all its 2-error overlaps, obtaining for each one the corresponding pair of witnesses as in Propositions 2 and 3, and then computing the minimal length of the so obtained witnesses. The algorithms in next section will look for all possible 2-error overlaps in increasing order of their shift. Nevertheless, note that it is not possible to stop at the first found 2-error overlap. The 2-error overlap which corresponds to the witnesses of minimal length can be a subsequent one, as shown in Example 7.
Example 7.
Consider the ternary alphabet $Σ = {0, 1, 2}$ . Recall that in this case the Hamming and the Lee distance coincide (cf. Remark 2). For any $h ⩾ 1$ , let $w = 2^{h}$ and $f = 0 w 0 w 1 w 1$ , with $| f | = n = 3 h + 4$ . It can be observed that, for any $h ⩾ 1$ , f has two 2-error overlaps, one of length $h + 2$ , for which ${dist}_{L} (0 w 0, 1 w 1) = 2$ and one of length $h + 1$ , for which ${dist}_{L} (0 w, w 1) = 2$ . Then, for any $h ⩾ 1$ , f is non-isometric applying Theorem 1. The first pair of witnesses for f, in increasing order of shift, can be constructed starting from the 2-error overlap of length $l = h + 2$ and shift $r = n - l = 2 h + 2$ . This overlap satisfies ${Condition}^{+}$ and the corresponding pair of witnesses for f is $(η_{r} (f), γ_{r} (f))$ , with $η_{r} (f) = 0 w 0 w (1 w 0 w 1 w 1) w 1$ and $γ_{r} (f) = 0 w 0 w (0 w 1 w 0 w 1) w 1$ . The length of this pair of witnesses is $| η_{r} (f) | = | γ_{r} (f) | = 6 h + 7$ . The second pair of witnesses for f can be constructed starting from the 2-error overlap of length $h + 1$ . This overlap does not satisfies ${Condition}^{+}$ and the corresponding pair of Lee-witnesses for f is $(α_{r} (f), β_{r} (f))$ , with $α_{r} (f) = 0 w 0 w 1 (2 w 0 w 1 w 1)$ and $β_{r} (f) = 0 w 0 w 1 (02^{h - 1} 10 w 1 w 1)$ . The length of this pair of witnesses is $| α_{r} (f) | = | β_{r} (f) | = 5 h + 7$ . Thus, the 2-error overlap that corresponds to the witnesses of minimal length is the second one in increasing order of shift, and then it provides the index $I_{L} (f) = 5 h + 7$ .
Remark 6.
Let $f \in Σ^{*}$ be a non-isometric word. Consider a pair $(u, v)$ of witnesses for f and suppose that $(u, v)$ is a pair of minimum length among all witnesses for f. This does not imply that $(u, v)$ , is a pair of witnesses for f of minimum distance. Also the converse holds. In fact, minimality in length does not coincide with minimality in distance, as shown in the following example.
Example 8.
Let Δ be the quaternary alphabet and $f = AACCC \in Δ^{5}$ . The word f has a 2-Ham-error overlap of shift $r = 2$ and a 2-Ham-error overlap of shift $r^{'} = 3$ .

Consider the 2-Ham-error overlap of shift $r^{'} = 3$ ; this 2-Ham-error does not satisfy ${Condition}^{+}$ and, following Proposition 2, we have that $(α_{r^{'}} (f), β_{r^{'}} (f)) = (AACCACCC, AACACCCC)$ is a pair of Ham-witnesses for f. Note that $| α_{r^{'}} (f) | = | β_{r^{'}} (f) | = 8$ .

Now, consider the 2-Ham-error overlap of shift $r = 2$ ; we have that ${pre}_{3} (f)$ disagrees from ${suf}_{3} (f)$ in positions $i = 1$ and $j = 2$ , with $j - i = r / 2 = 1$ , $f [i] = A$ , $f [j] = A$ , $f [r + i] = C$ and $f [r + j] = C$ . Therefore, this 2-Ham-error overlap satisfies ${Condition}^{+}$ and, following Proposition 2 in the case $i ⩽ r / 2$ , we have that $(η_{r} (f), γ_{r} (f)) = (AACACCCC, AAACACCC)$ is a pair of Ham-witnesses for f. Note that $| η_{r} (f) | = | γ_{r} (f) | = | α_{r^{'}} (f) | = | β_{r^{'}} (f) | = 8$ and $I_{H} (f) = 8$ .

Since f has no other 2-Ham-error overlap it follows that $(η_{r} (f), γ_{r} (f))$ is a pair of Ham-witnesses of minimum length 8 for f, but it is not of minimum Hamming distance, since ${dist}_{H} (α_{r^{'}} (f), β_{r^{'}} (f)) = 2 < {dist}_{H} (η_{r} (f), γ_{r} (f)) = 3$ . It can be shown that the same result holds for $(η_{r} (f), γ_{r} (f))$ when the Lee distance is considered.

Furthermore, in [19], it is shown the example of a binary word $f^{'}$ for which there is a unique pair of Ham-witnesses of minimum length, whose distance is not minimum, while the pair of Ham-witnesses of minimum distance is not of minimum length. The word is $f^{'} = 010010110110$ . It has two 2-Ham-error overlaps, the one of shift 6 that satisfies ${Condition}^{+}$ and the one of shift 10 that does not satisfy ${Condition}^{+}$ . Then, $| η_{6} (f^{'}) | = | γ_{6} (f^{'}) | = 21$ , while $| α_{10} (f^{'}) | = | β_{10} (f^{'}) | = 22$ , and thus $I_{H} (f^{'}) = 21$ . On the other hand, ${dist}_{H} (α_{10} (f), β_{10} (f)) = 2 < {dist}_{H} (η_{6} (f), γ_{6} (f)) = 3$ .
4. Characterization of words of minimum/maximum index

Corollary 1 provides some bounds on the index of non-isometric words. Indeed, the Ham-index of a Ham-non-isometric word f satisfies $| f | + 1 ⩽ I_{H} (f) ⩽ 2 | f | - 1$ and the Lee-index of a Lee-non-isometric word f satisfies the same bounds $| f | + 1 ⩽ I_{L} (f) ⩽ 2 | f | - 1$ . In this section, we show that the bounds are tight and explicitly characterize the words of minimum and maximum index.

Let us start with the characterization of the k-ary Ham-non-isometric words f with minimum Ham-index equal to $| f | + 1$ .

Proposition 4.
Let Σ be a k-ary alphabet with $k ⩾ 2$ and let $f \in Σ^{n}$ be a Ham-non-isometric word. Then, $I_{H} (f) = n + 1$ if and only if $f = x^{h} y^{s} z^{t}$ , for some $h, s, t ⩾ 1$ , $x, y, z \in Σ$ with ${dist}_{H} (x, y) = {dist}_{H} (y, z) = 1$ .
Proof.
Suppose $I_{H} (f) = n + 1$ . Theorem 2 implies that $n + 1 = | α_{r} (f) |$ or $n + 1 = | η_{r} (f) |$ , for some 2-Ham-error overlap of shift r. Recall that $| η_{r} (f) | = 3 r / 2 + n$ and thus it cannot be $| η_{r} (f) | = n + 1$ since r is an integer. Therefore, $n + 1 = I_{H} (f) = | α_{r} (f) |$ holds. Since $| α_{r} (f) | = r + n$ , $r = 1$ and f has a 2-Ham-error overlap of length $n - 1$ with error positions i, j, $i < j$ . This implies that $f [i] = x$ while $f [i + 1] = y$ for some symbols x, y with ${dist}_{H} (x, y) = 1$ , and that $f [j] = y$ while $f [j + 1] = z$ for some symbol z with ${dist}_{H} (y, z) = 1$ . Therefore, $f = x^{i} y^{j - i} z^{n - j}$ .

Suppose now that $f = x^{h} y^{s} z^{t}$ , for some $h, s, t ⩾ 1$ , $x, y, z \in Σ$ with ${dist}_{H} (x, y) = 1$ and ${dist}_{H} (y, z) = 1$ . Then, f has a 2-Ham-error overlap of length $n - 1$ and shift $r = 1$ . This 2-Ham-error overlap does not satisfy ${Condition}^{+}$ , because $r = 1$ is not even. From Proposition 2, $(α_{r} (f), β_{r} (f))$ is a pair of Ham-witnesses for f. Note that $| α_{r} (f) | = n + 1$ and $I_{H} (f) = n + 1$ since, from Corollary 1, $n + 1 ⩽ I_{H} (f)$ . □

The following proposition characterizes Ham-non-isometric words with maximum Ham-index.
Proposition 5.
Let Σ be a k-ary alphabet with $k ⩾ 2$ and let $f \in Σ^{n}$ be a Ham-non-isometric word. Then, $I_{H} (f) = 2 n - 1$ if and only if
f has exactly one 2-Ham-error overlap and it satisfies ${Condition}^{+}$
and
$f = x w x w \overline{x} w \overline{x}$ , for some $w \in Σ^{}$ and* $x, \overline{x} \in Σ$ , ${dist}_{H} (x, \overline{x}) = 1$ .

Proof.
Suppose, first, that $I_{H} (f) = 2 n - 1$ . From Theorem 2, $I_{H} (f) = | α_{r} (f) |$ or $I_{H} (f) = | η_{r} (f) |$ , for some 2-Ham-error overlap of shift r. In fact $I_{H} (f) = | α_{r} (f) |$ cannot hold since $r ⩽ n - 2$ and, then, $| α_{r} (f) | = n + r < 2 n - 1$ . Recall that any pair of Ham-witnesses $(α_{r} (f), β_{r} (f))$ corresponds to a 2-Ham-error overlap that does not satisfy ${Condition}^{+}$ . Therefore, f has no such 2-Ham-error overlaps, that is f has only 2-Ham-error overlaps that satisfy ${Condition}^{+}$ . From Lemma 1, f has exactly one 2-Ham-error overlap that satisfies ${Condition}^{+}$ and the corresponding pair of Ham-witnesses, $(η_{r} (f), γ_{r} (f))$ , is such that $2 n - 1 = I_{H} (f) = | η_{r} (f) |$ . Let i, j be the error positions of this 2-Ham-error overlap. From Proposition 1, $f = ρ {(x w)}^{k_{1}} x w x w \overline{x} w \overline{x} {(w \overline{x})}^{k_{2}} σ$ , with $w, ρ, σ \in Σ^{}$ , $k_{1}, k_{2} ⩾ 0$ , $x, \overline{x} \in Σ$ , ${dist}_{H} (x, \overline{x}) = 1$ , $| w | = r / 2 - 1$ and ρ (σ, resp.) a suffix (a prefix, resp.) of w. Moreover, if $k_{1} > 0$ (i.e. $i ⩾ r / 2$ ) then f would have a 2-Ham-error overlap that does not satisfy ${Condition}^{+}$ (cf. Remark 4), against the hypotheses. Therefore, $k_{1} = 0$ and $f = ρ x w x w \overline{x} w \overline{x} {(w \overline{x})}^{k_{2}} σ$ . Moreover, $| η_{r} (f) | = 3 r / 2 + n$ and then $2 n - 1 = I_{H} (f) = | η_{r} (f) | = 3 r / 2 + n$ . Therefore, $n = 3 r / 2 + 1 = 3 | w | + 4$ and this implies $| ρ | = | σ | = 0$ and $k_{2} = 0$ , i.e. $f = x w x w \overline{x} w \overline{x}$ .

Suppose, now, that $f = x w x w \overline{x} w \overline{x}$ , for some $w \in Σ^{}$ and $x, \overline{x} \in Σ$ , ${dist}_{H} (x, \overline{x}) = 1$ and that f has only 2-Ham-error overlaps that satisfy ${Condition}^{+}$ . From Lemma 1, f has exactly one 2-Ham-error overlap that satisfies ${Condition}^{+}$ . Since $f = x w x w \overline{x} w \overline{x}$ , this is the 2-Ham-error overlap with shift $r = 2 (| w | + 1)$ and error positions $i = 1$ and $j = | w | + 2$ . From Proposition 2, the pair $(η_{r} (f), γ_{r} (f))$ is a pair of Ham-witnesses for f. Note that $| η_{r} (f) | = 3 r / 2 + | f | = 3 (| w | + 1) + | f | = 2 | f | - 1 = 2 n - 1$ . Since f has no other 2-Ham-error overlap, from Theorem 2, $I_{H} (f) = | η_{r} (f) | = 2 n - 1$ . □

Let us now consider the Lee-index. Recall that the Lee-index is equal to the Ham-index, when $k = 2, 3$ (Remark 2). On the other hand, the Lee-index of a word is always equal to its length, when $k > 4$ . Hence, consider the case $k = 4$ and $Σ = Δ$ . The following proposition characterizes the Lee-non-isometric words with minimum Lee-index.
Proposition 6.
Let $f \in Δ^{n}$ be a Lee-non-isometric word. Then, $I_{L} (f) = n + 1$ if and only if
$f = x^{h} y^{s} z^{t}$ , for some $h, s, t ⩾ 1$ , $x, y, z \in Σ$ with ${dist}_{L} (x, y) = {dist}_{L} (y, z) = 1$
or
$f = x^{h} y^{s}$ , for some $h, s ⩾ 1$ , $x, y \in Δ$ with ${dist}_{L} (x, y) = 2$ .

Proof.
Suppose $I_{L} (f) = n + 1$ . Propositions 3 states that $n + 1 = I_{L} (f) = | α_{r} (f) |$ or $n + 1 = I_{L} (f) = | η_{r} (f) |$ or $n + 1 = I_{L} (f) = | φ_{r} (f) |$ , for some 2-Lee-error overlap of shift r and error positions i, j, with $1 ⩽ i ⩽ j ⩽ l$ ( $i = j$ iff $m = 1$ ).

Recall that $| η_{r} (f) | = n + 3 r / 2$ and thus it cannot be $I_{L} (f) = | η_{r} (f) | = n + 1$ , since r is an integer.

If $n + 1 = I_{L} (f) = | α_{r} (f) |$ , then the 2-Lee-error overlap of shift r has two different error positions (i.e. $m = 2$ ). Moreover, since $| α_{r} (f) | = r + n$ then $r = 1$ and f has a 2-Lee-error overlap of length $n - 1$ with two different error positions $i < j$ . This implies that $f [i] = x$ while $f [i + 1] = y$ for some symbols x, y with ${dist}_{L} (x, y) = 1$ , and that $f [j] = y$ while $f [j + 1] = z$ for some symbol z with ${dist}_{L} (y, z) = 1$ . Therefore, $f = x^{i} y^{j - i} z^{n - j}$ .

On the contrary, if $n + 1 = I_{L} (f) = | φ_{r} (f) |$ , then the 2-Lee-error overlap of shift r has only one error position (i.e. $m = 1$ ). Moreover, since $| φ_{r} (f) | = r + n$ , then $r = 1$ and f has a 2-Lee-error overlap of length $n - 1$ with only one error position i. This implies $f = x^{i} y^{n - i}$ , for some $x, y \in Δ$ with ${dist}_{L} (x, y) = 2$ .

Suppose now that $f = x^{h} y^{s} z^{t}$ , for some $h, s, t ⩾ 1$ , $x, y, z \in Δ$ with ${dist}_{L} (x, y) = {dist}_{L} (y, z) = 1$ . Then, f has a 2-Lee-error overlap of length $n - 1$ and shift $r = 1$ . This 2-Lee-error overlap does not satisfy ${Condition}^{+}$ , because $r = 1$ is not even. From Proposition 3, case $m = 2$ , $(α_{r} (f), β_{r} (f))$ is a pair of Lee-witnesses for f. Note that $| α_{r} (f) | = n + 1$ and $I_{L} (f) = | α_{r} (f) | = n + 1$ , since, from Corollary 1, $n + 1 ⩽ I_{L} (f)$ .

Suppose now that $f = x^{h} y^{s}$ , for some $h, s ⩾ 1$ , $x, y \in Δ$ with ${dist}_{L} (x, y) = 2$ . Then f has a 2-Lee-error overlap of length $n - 1$ and shift $r = 1$ , with only one error position. From Proposition 3, case $m = 1$ , $(φ_{r} (f), ψ_{r} (f))$ is a pair of Lee-witnesses for f. Note that $| φ_{r} (f) | = n + 1$ and $I_{L} (f) = | φ_{r} (f) | = n + 1$ , since, from Corollary 1, $n + 1 ⩽ I_{L} (f)$ . □

Next proposition characterizes Lee-non-isometric words over Δ which have maximum Lee-index. Proposition 7.
Let $f \in Δ^{n}$ be a Lee-non-isometric word. Then $I_{L} (f) = 2 n - 1$ if and only if
f has exactly one 2-Lee-error overlap and it satisfies ${Condition}^{+}$
and
$f = x w x w \overline{x} w \overline{x}$ , for some $w \in Δ^{}$ and* $x, \overline{x} \in Δ$ , ${dist}_{L} (x, \overline{x}) = 1$ or $f = y w \overline{y}$ , for some $w \in Δ^{}$ and* $y, \overline{y} \in Δ$ , with ${dist}_{L} (y, \overline{y}) = 2$ .

Proof.
Suppose, first, that $I_{L} (f) = 2 n - 1$ . Theorem 3 implies that $I_{L} (f) = | α_{r} (f) |$ or $I_{L} (f) = | η_{r} (f) |$ or $I_{L} (f) = | φ_{r} (f) |$ , for some 2-Lee-error overlap of shift r, and error positions i, j, with $1 ⩽ i ⩽ j ⩽ n - r$ ( $i = j$ iff $m = 1$ ).

In fact, $I_{L} (f) = | α_{r} (f) | = 2 n - 1$ cannot hold since $r ⩽ n - 2$ and, then, $| α_{r} (f) | = n + r < 2 n - 1$ .

If $I_{L} (f) = | φ_{r} (f) |$ then the 2-Lee-error overlap of shift r has only one error position (i.e. $m = 1$ ). Moreover, since $| φ_{r} (f) | = r + n$ , if $r + n = 2 n - 1$ then $r = n - 1$ and f has a 2-Lee-error overlap of length 1 with only one error position. This implies $f = y w \overline{y}$ , for some $w \in Δ^{}$ and $y, \overline{y} \in Δ$ , with ${dist}_{L} (y, \overline{y}) = 2$

If, instead, $I_{L} (f) = | η_{r} (f) |$ , then the 2-Lee-error overlap of shift r has two different error positions (i.e. $m = 2$ ) and it satisfies ${Condition}^{+}$ . A reasoning analogous to the one used in the proof of Proposition 5 shows that $f = x w x w \overline{x} w \overline{x}$ , for some $w \in Δ^{}$ and $x, \overline{x} \in Δ$ , ${dist}_{L} (x, \overline{x}) = 1$ .

Note that the case $I_{L} (f) = | φ_{r} (f) |$ rules out the case $I_{L} (f) = | η_{r} (f) |$ and vice versa. In fact if $I_{L} (f) = | φ_{r} (f) |$ , then the first and the last symbol of f have Lee-distance equal to 2 whereas, if $I_{L} (f) = | η_{r} (f) |$ , then they have Lee-distance equal to 1.

Moreover, in both cases, f has exactly one 2-Lee-error overlap, either the one that allows the construction of $(φ_{r} (f), ψ_{r} (f))$ or the one that allows the construction of $(η_{r} (f), γ_{r} (f))$ . If f would have another different 2-Lee-error overlap, this would give a pair of Lee-witnesses for f of length less than $2 n - 1$ , contradicting $I_{L} (f) = 2 n - 1$ .

Suppose now that f has exactly one 2-Lee-error overlap and that $f = x w \overline{x}$ , for some $w \in Δ^{}$ and $x, \overline{x} \in Δ$ , with ${dist}_{L} (x, \overline{x}) = 2$ . Then, the unique 2-Lee-error overlap of f is the one length 1 and shift $r = n - 1$ . From Proposition 3, case $m = 1$ , $(φ_{r} (f), ψ_{r} (f))$ is a pair of Lee-witnesses for f. Note that $| φ_{r} (f) | = 2 n - 1$ and, since f has no other 2-Lee-error overlap, it follows $I_{L} (f) = | φ_{r} (f) | = 2 n - 1$ (cf. Theorem 3).

If $f = x w x w \overline{x} w \overline{x}$ , for some $w \in Δ^{}$ and $x, \overline{x} \in Δ$ , ${dist}_{L} (x, \overline{x}) = 1$ , then f has the 2-Lee-error overlap of shift $r = 2 (| w | + 1)$ and error positions $i = 1$ and $j = | w | + 2$ which satisfies ${Condition}^{+}$ . Since f has exactly one 2-Lee-error overlap, $I_{L} (f) = | η_{r} (f) |$ . Note that $| η_{r} (f) | = 3 r / 2 + | f | = 3 (| w | + 1) + | f | = 2 | f | - 1 = 2 n - 1$ and finally $I_{L} (f) = 2 n - 1$ . □

5. Algorithms for computing index and witnesses

The results given in Section 3 are now applied to design an algorithm that computes the Ham-index of a word and yields a pair of Ham-witnesses of minimal length, when the word is Ham-non-isometric. An analogous algorithm is then provided when the Lee-distance is concerned instead of the Hamming one. Recall that if f is isometric then its index is ∞; otherwise, it is the minimal length of two words u, v, such that $(u, v)$ is a pair of witnesses for f.

Assume that Σ is a k-ary alphabet with $k ⩾ 2$ and $f \in Σ^{*}$ is a word $f [0] f [1] \dots f [n - 1]$ of symbols in Σ, where n is the length of f and $f [i]$ ’s are its symbols. Note that in this section the positions of f start from 0, and not from 1, according to usual notation in programming languages. Following the definitions in Section 2, the suffix of f starting at position i, is denoted by ${suf}_{n - i} (f) = f [i \dots n - 1]$ , where the subscript $n - i$ refers to its length.

5.1. The algorithm for computing Ham-index and Ham-witnesses

Let us sketch an algorithm which inputs a k-ary non-empty word f of length n and outputs an integer I, that is the Ham-index of f, and, when the word is Ham-non-isometric, a pair $(u, v)$ of Ham-witnesses for f of length I. Its pseudo-code is given in Algorithm 1 and an example follows.

5.1.1. Description

Algorithm 1 starts with a call to function TwoErrorOverlaps that looks for all 2-Ham-error overlaps of f, using the Kangaroo method [12,17]. The Kangaroo method finds the mismatches in a given alignment of two words by “jumping” from one error to the next, as here explained.

Recall that a 2-Ham-error overlap of f is a suffix of f that differs from the prefix of the same length in exactly 2 positions. For each position i, with $i = 1, \dots, n - 2$ , TwoErrorOverlaps compares the suffix ${suf}_{n - i} (f)$ starting at i with ${suf}_{n} (f) = f$ . Note that the first position $p_{1}$ where the suffixes ${suf}_{n - i} (f)$ and ${suf}_{n} (f)$ (possibly) differ is the position just after the longest common prefix of the two suffixes. More precisely, $p_{1} = llcp (0, i)$ , where for any $0 ⩽ j ⩽ j^{'} ⩽ n - 1$ , a call to $llcp (j, j^{'})$ returns the length of the longest common prefix of suffixes ${suf}_{n - j} (f)$ and ${suf}_{n - j^{'}} (f)$ . Then, the second position $p_{2}$ where the suffixes ${suf}_{n - i} (f)$ and ${suf}_{n} (f)$ (possibly) differ can be obtained as the position just after the longest common prefix of the suffixes ${suf}_{n - i - p_{1} - 1} (f)$ and ${suf}_{n - p_{1} - 1} (f)$ .

The function TwoErrorOverlaps uses a variable l which gives the length of the current overlap of ${suf}_{n - i} (f)$ and ${suf}_{n} (f)$ and a variable d which contains their current Hamming distance. Variable d is increased when a mismatch has been found, until $l = n - i$ and $d = 2$ , meaning that ${suf}_{n - i} (f)$ has been entirely compared with ${pre}_{n - i} (f)$ and exactly 2 mismatches have been found. More precisely, TwoErrorOverlaps with input f finds all 2-Ham-error overlaps of f and stores their lengths in the list $2 eolens$ . At the same time, for each 2-Ham-error overlap found, the corresponding error positions are kept in the list $allerrpos$ , which is, therefore, a list of lists. The function works similarly as the first algorithm in [8], which instead stops when a 2-Ham-error overlap is detected.

If no 2-Ham-error overlap of f is found, then Algorithm 1 sets the Ham-index I to ∞ and returns I and the pair $(u, v) = (empty, empty)$ .

Otherwise, f is Ham-non-isometric and I is initialized as $I = 2 n$ (in Line 1), since the Ham-index of f is upper bounded by $I_{H} (f) ⩽ 2 n - 1$ in Corollary 1. Then, for each 2-Ham-error overlap, the algorithm constructs a pair of Ham-witnesses calling the function WitnessesConstructor and possibly update i and $(u, v)$ . According to Proposition 2 and Theorem 2, the construction depends on whether the ${Condition}^{+}$ is satisfied (see Definition 6). If it is not satisfied, the pair $(u, v)$ may be constructed according to case 1. of Proposition 2. When ${Condition}^{+}$ is satisfied, if $i ⩽ r / 2$ , the pair $(u, v)$ will be constructed as in case 2. Otherwise, it is case 3. and there is nothing else to do because it is proved that f always has another 2-Ham-error overlap of shift bigger than r, and thus the pair $(u, v)$ will be constructed in a subsequent call of the function.

The function CondPlus inputs the word f, the integers r, i and j, where i and j are the error positions in the 2-Ham-error overlap of shift r, and outputs $True$ if ${Condition}^{+}$ is verified, $False$ otherwise. Note that ${Condition}^{+}$ can hold only if r is even. If r is even, then the function checks the other conditions in $cond 1$ , $cond 2$ , and $cond 3$ . In particular, $cond 3$ is $True$ iff $f [i \dots i + r / 2 - 1] = f [j \dots j + r / 2 - 1]$ . This check is done testing if $llcp (i, j) ⩾ r / 2$ , rather than by comparing all the $r / 2$ symbols.

Algorithm 1 computes step by step I as the minimal length of all the Ham-witnesses considered, and it stores in $(u, v)$ a pair of Ham-witnesses of such length. At the end, I is the Ham-index of f, according to Theorem 2, and Algorithm 1 outputs I and a corresponding pair $(u, v)$ of Ham-witnesses.

Algorithm 1:

Computing the Ham-index and Ham-witnesses for f

5.1.2. Analysis

The efficiency of Algorithm 1 mostly depends on the computation of $llcp (i, j)$ , i.e., the length of the longest common prefix of the suffixes of f starting at position i and j, respectively. Recall that $llcp (i, j)$ gives the next error position in an alignment of the two suffixes, following the Kangaroo method. Let us sketch how $llcp (i, j)$ can be computed in constant time, using some additional data structure for f and its suffixes taking $O (n)$ space and $O (n)$ time to be constructed. This allows to check, for a given position i in f, whether f has a 2-Ham-error overlap of length $n - i$ in time $O (1)$ .

Suffix trees are a well-known data structure to manage the suffixes of a given word. The suffix tree of a word $f = f [0 \dots n - 1]$ has n leaves labelled 0, 1,…, $n - 1$ . For $0 ⩽ i ⩽ n - 1$ , the leaf i represents the suffix ${suf}_{n - i} (f)$ which is the label of the path from the root to leaf i. Actually, for $0 ⩽ i ⩽ j ⩽ n - 1$ , $llcp (i, j) = LCA (i, j)$ , where $LCA (i, j)$ is the depth of the lowest common ancestor of leaves i and j in the suffix tree of f. To improve the efficiency of the algorithm, the information about the suffixes of f will not be handled by a suffix tree, but by some linear space data structures, namely, the Suffix Array ( $SA$ ), its inverse ( ${SA}^{- 1}$ ) and the Longest Common Prefix ( $LCP$ ) array (see [10] for the definitions). J. Fischer and V. Heun have shown that $llcp (i, j)$ (or $LCA (i, j)$ , equivalently) can be computed in constant time, using such data structures and a constant time algorithm to ask Range Minimum Queries ( $RMQ$ ) [11]. In fact, the following formula holds: $\begin{matrix} LCA (i, j) = LCP [{RMQ}_{LCP} ({SA}^{- 1} [i] + 1, {SA}^{- 1} [j])] \end{matrix}$

Theorem 4.
Let Σ be a k-ary alphabet, $k ⩾ 2$ , and $f \in Σ^{n}$ be a non-empty word of length n.

Algorithm 1 with input f computes the Ham-index of f and (possibly) a pair of Ham-witnesses of minimal length for f in $O (n)$ time with additional $O (n)$ space.
Proof.
Let us analyse Algorithm 1, starting from its functions.
TwoErrorOverlaps inputs the word f and outputs all lengths of its 2-Ham-error overlaps in the list $2 eolens$ and all corresponding error positions in the list $allerrpos$ . Applying the Kangaroo method, a call to $llcp (i, j)$ can be done in $O (1)$ time, with additional $O (n)$ space. For a fixed i, TwoErrorOverlaps makes at most two calls to $llcp$ and hence, it can check whether f has a 2-Ham-error overlap of length $n - i$ in time $O (1)$ . Finally, TwoErrorOverlaps runs in $O (n)$ time and space.

CondPlus inputs the word f, the integers r, i and j, where i and j are the error positions in the 2-Ham-error overlap of shift r. It verifies if r is even and if conditions $cond 1$ , $cond 2$ , and $cond 3$ hold true. Note that conditions $cond 1$ , $cond 2$ , and $cond 3$ can all be checked in $O (1)$ time. In particular, $cond 3$ , i.e., $f [i \dots i + r / 2 - 1] = f [j \dots j + r / 2 - 1]$ , is verified by a single call to $llcp$ , that can be executed in $O (1)$ time, with the aforementioned data structures for f. Hence, the overall time complexity of CondPlus is $O (1)$ .

WitnessesConstructor inputs the word f, the length l of a 2-Ham-error overlap of f, its corresponding error positions in the list $errpos$ and outputs a pair $(u, v)$ of Ham-witnesses for f. According to Proposition 2, the function constructs the pair $(u, v)$ in two different ways, following that CondPlus returns $False$ or $True$ with $i ⩽ r / 2$ . Since CondPlus runs in $O (1)$ time and all the other instructions can be executed in constant time, the time complexity of WitnessesConstructor is $O (1)$ .
Let us now complete the analysis of Algorithm 1. The main algorithm contains one call to TwoErrorOverlaps and at most $n - 2$ calls to WitnessesConstructor, since the 2-Ham-error overlaps of f are at most $n - 2$ . Therefore, the overall time complexity of Algorithm 1 can be obtained as the sum of the cost of TwoErrorOverlaps and $O (n)$ times the cost of WitnessesConstructor. Thus, it is $O (n)$ .

The space complexity of Algorithm 1 is due to the data structures needed to run $llcp (i, j)$ in constant time, both in TwoErrorOverlaps and in CondPlus; thus it is $O (n)$ . □
Example 9.
Let us run Algorithm 1 to compute the Ham-index and a pair of Ham-witnesses for $f = f [0] f [1] \dots f [6] = 0101111$ (as in Example 3). It starts calling the function TwoErrorOverlaps with input $f = 0101111$ . This function finds two 2-Ham-error overlaps. The first one is of length 4, where the errors are in positions 0, 2; in fact, $f [0] = 0 \neq f [3] = 1$ and $f [2] = 0 \neq f [5] = 1$ . The second one is of length 3, where the errors are still in positions 0, 2; in fact, $f [0] = 0 \neq f [4] = 1$ and $f [2] = 0 \neq f [6] = 1$ . Thus, TwoErrorOverlaps outputs $2 eolens = [4, 3]$ and $allerrpos = [[0, 2], [0, 2]]$ . Then, coming back to Line 1 of the main algorithm, because $2 eolens$ is not empty, the algorithm initializes the output variable $I = 14$ . For $i = 0$ to 1 the algorithm calls the function WitnessesConstructor.

The first call takes as input $(0101111, 4, [0, 2])$ and sets $n = 7$ , $r = 3$ , $i = 0$ , $j = 2$ and $cplus = False$ after calling CondPlus $(0101111, 3, 0, 2)$ . Thus, the function WitnessesConstructor computes and outputs $u = 0101101111$ and $v = 0100111111$ , obtained as $α_{r} (f)$ and $β_{r} (f)$ . Since $len (u) = 10 < I = 14$ , the algorithm updates $I = 10$ and $(u, v) = (0101101111, 0100111111)$ . The second call to WitnessesConstructor takes as input $(0101111, 3, [0, 2])$ and sets $n = 7$ , $r = 4$ , $i = 0$ , $j = 2$ and $cplus = True$ after calling CondPlus $(0101111, 4, 0, 2)$ . Indeed, r is even and the conditions $cond 1$ , $cond 2$ , and $cond 3$ are $True$ . Thus, the function outputs $u = 0101110111111$ and $v = 0101011101111$ , obtained as $η_{r} (f)$ and $γ_{r} (f)$ . Since $len (u) = 13$ is greater than $I = 10$ the algorithm does not update neither I nor $(u, v)$ . Therefore, the main algorithm outputs the Ham-index $I = 10$ and the pair of Ham-witnesses $(u, v) = (0101101111, 0100111111)$ .

5.2. The algorithm for computing Lee-index and Lee-witnesses

This section shows an algorithm which inputs a quaternary non-empty word f of length n; it outputs an integer I, the Lee-index of f, and a pair $(u, v)$ of Lee-witnesses for f of length I, when the word is Lee-non-isometric. Recall that in the case $k = 2, 3$ , the Lee-distance and the Lee-index coincide with the Hamming ones; hence Algorithm 1 applies. Furthermore, for $k > 4$ , every word f is Lee-non-isometric and its Lee-index is equal to its length. Algorithm 2 is a slight variation of Algorithm 1 made to work with the Lee distance, instead of the Hamming one, while keeping the same complexity.

5.2.1. Description

Algorithm 2 is a slight variation of Algorithm 1. It is presented in its complete form for the sake of completeness. Let us focus on the differences existing between the two algorithms.

Algorithm 2 still starts with a call to function TwoErrorOverlaps to compute all 2-Lee-error overlaps of f, using the Kangaroo method. Function TwoErrorOverlaps compares the suffix ${suf}_{n - i} (f)$ starting at i with ${suf}_{n} (f) = f$ ; this is done in Line 2 for each position i, with $i = 1, \dots, n - 1$ , and not for $i = 1, \dots, n - 2$ as in Algorithm 1, since the length of a 2-Lee-error overlap can be 1, too, differently from the 2-Ham-error overlaps whose length is at least 2. Then, in Line 2 the considered distance is the Lee one, instead of the Hamming one.

Subsequently, if some 2-Lee-error overlap of f was found, Algorithm 2 constructs a pair of Lee-witnesses calling the function WitnessesConstructor for each 2-Lee-error overlap. According to Proposition 3 and Theorem 3, the function constructs the pair $(u, v)$ in two different ways, following that the 2-Lee-error overlap is caused by two complementary symbols (i.e., $m = 1$ and the list $errpos$ has only one element) or by two non-complementary symbols (i.e., $m = 2$ and the list $errpos$ has two elements). The case $m = 1$ was not possible with the Hamming distance, therefore, Lines 2-2 must be added. If $m = 1$ , the function constructs u as $φ_{r} (f)$ by appending to the prefix of f of length $r = n - l$ the word $f^{(i, -)}$ obtained as specified in Definition 5. Similarly, it constructs v as $ψ_{r} (f)$ , this time appending $f^{(i, +)}$ . The case $m = 2$ goes as for the Hamming distance and no change need to be done.

Algorithm 2:

Computing the Lee-index and Lee-witnesses for f

5.2.2. Analysis

Theorem 5.
Let Σ be a k-ary alphabet, $k = 4$ , and $f \in Σ^{n}$ be a non-empty word of length n.

Algorithm 2 with input f computes the Lee-index of f and a pair of Lee-witnesses of minimal length for f in $O (n)$ time with additional $O (n)$ space.
Proof.
Algorithm 2 is a slight variation of Algorithm 1 and it keeps the same time and space complexity. Indeed, the changes made to Algorithm 1 concern: one more repetition of the loop in Line 2, the evaluation of the Lee distance, instead of the Hamming one in Line 2, and the computation of a further pair of Lee-witnesses when $m = 1$ in Lines 2-2. All these modifications add only some extra constant time. □
Example 10.
Let us run Algorithm 2 on $f = f [0] f [1] \dots f [5] = AGATAC$ . The call to function TwoErrorOverlaps finds two 2-Lee-error overlaps. The first one is of length 4, where the errors are in positions 1, 3 and are caused by non-complementary symbols; in fact, $f [1] = G \neq f [3] = T$ and $f [3] = T \neq f [5] = C$ . The second one is of length 2, and has a unique error position 1; in fact, $f [1] = G \neq f [5] = C$ and ${dist}_{L} (G, C) = 2$ , since G and C are complementary symbols. Thus, TwoErrorOverlaps outputs $2 eolens = [4, 2]$ and $allerrpos = [[1, 3], [1]]$ .

Then, coming back to Line 3 of the main algorithm, because $2 eolens$ is not empty, the algorithm initializes the output variable $I = 12$ . For $i = 0$ to 1 the algorithm calls the function WitnessesConstructor.

The first call takes as input $(AGATAC, 4, [1, 3])$ and sets $n = 6$ , $r = 2$ , $i = 1$ . Because $len (errpos) = 2$ , then $j = 3$ and $cplus = False$ after calling CondPlus $(AGATAC, 2, 1, 3)$ . Thus, the function WitnessesConstructor computes and outputs $u = AGATATAC$ and $v = AGAGACAC$ , obtained as $α_{r} (f)$ and $β_{r} (f)$ . Since $len (u) = 8 < I = 12$ , the algorithm updates $I = 8$ and $(u, v) = (AGATATAC, AGAGACAC)$ .

The second call to WitnessesConstructor takes as input $(AGATAC, 2, [1])$ and sets $n = 6$ , $r = 4$ , $i = 1$ . Because $len (errpos) = 1$ , then the function outputs $u = AGATAAATAC$ and $v = AGATATATAC$ , obtained as $φ_{r} (f)$ and $ψ_{r} (f)$ . Since $len (u) = 10$ is greater than $I = 8$ the algorithm does not update neither I nor $(u, v)$ .

Hence, Algorithm 2 outputs the Lee-index $I = 8$ and the pair of Lee-witnesses $(u, v) = (AGATATAC, AGAGACAC)$ .
6. Conclusion

The goal of this paper was to investigate the notion of k-ary isometric word, with $k ⩾ 2$ , when the isometricity is defined in terms of the Hamming distance and of the Lee distance. Deciding whether a word is isometric can be efficiently done using a characterization of non-isometric words as the ones showing a particular overlap with errors. The evidence that a given word f is non-isometric can be given by exhibiting a pair of f-free words whose transformations cannot avoid the factor f. Such pair of words is called a pair of Ham-witnesses (Lee-witnesses, resp.) and the minimal length of the witnesses is called the Ham-index (Lee-index, resp.) of f. With the aim of laying the foundations for an efficient computation of the index and the pairs of witnesses of non-isometric k-ary words, first, the necessary theoretical results have been provided. The results allowed to design Algorithm 1 and Algorithm 2 which take a word and, in linear time and space, outputs its index and a minimal pair of witnesses when the word is non-isometric.

Table 1

Lee-non-isometric words in ${A, C, T, G}^{3}$ starting with A

Word (f)	2eo-length (l)	2eo-shift (r)	m	Type	Witness1 (u)	Witness2 (v)	Index ( $I_{L}$ (f))
AAT	2	1	1	FP	AAGT	AACT	4
AAT	1	2	1	FP	AAGAT	AACAT
ACA	2	1	2	AB	ACCA	AAAA	4
ACT	2	1	2	AB	ACCT	AATT	4
ACT	1	2	1	FP	ACGCT	ACCCT
ATT	2	1	1	FP	AGTT	ACTT	4
ATT	1	2	1	FP	ATGTT	ATCTT
AGA	2	1	2	AB	AGGA	AAAA	4

Algorithms 1 and Algorithm 2 have been implemented in C $+ +$ . Let us conclude by showing in the following tables some data obtained running Algorithm 2. The tables list the Lee-non-isometric words f in $Δ^{*}$ that starts with A, of length 3 in Table 1, and of length 4 in Table 2. For each word f, the second and the third columns report all the 2-Lee-error overlaps by their length, 2eo-length (l), and shift, 2eo-shift (r), respectively. For each 2-Lee-error overlap, m gives the number of error positions (1 or 2), while Type denotes which construction of the Lee-witnesses has been used, according to Proposition 3; namely, AB refers to case 2.a. when a pair $(α_{r} (f), β_{r} (f))$ is constructed, EG refers to case 2.b. when a pair $(η_{r} (f), γ_{r} (f))$ is constructed, and FP refers to case 1. when a pair $(φ_{r} (f), ψ_{r} (f))$ is constructed. The corresponding pair $(u, v)$ of Lee-witnesses is given by $(Witness1, Witness2)$ as reported in the sixth and seventh columns. The last column contains the Lee-index of word f, that is the minimum length of its witnesses.

Table 2

Lee-non-isometric words in ${A, C, T, G}^{4}$ starting with A

Word (f)	2eo-length (l)	2eo-shift (r)	m	Type	Witness1 (u)	Witness2 (v)	Index ( $I_{L}$ (f))
AAAT	3	1	1	FP	AAAGT	AAACT	5
	2	2	1	FP	AAAGAT	AAACAT
	1	3	1	FP	AAAGAAT	AAACAAT
AACA	3	1	2	AB	AACCA	AAAAA	5
AACC	2	2	2	EG	AACACCC	AAACACC	7
AACT	3	1	2	AB	AACCT	AAATT	5
AACT	1	3	1	FP	AACGACT	AACCACT
AACG	2	2	2	AB	AACACG	AAAGCG	6
AATA	2	2	1	FP	AAGATA	AACATA	6
AATT	3	1	1	FP	AAGTT	AACTT	5
AATT	1	3	1	FP	AATGATT	AATCATT
AAGA	3	1	2	AB	AAGGA	AAAAA	5
AAGC	2	2	2	AB	AAGAGC	AAACGC	6
AAGT	3	1	2	AB	AAGGT	AAATT	5
AAGT	1	3	1	FP	AAGGAGT	AAGCAGT
AAGG	2	2	2	EG	AAGAGGG	AAAGAGG	7
ACAA	3	1	2	AB	ACCAA	AAAAA	5
ACAT	1	3	1	FP	ACAGCAT	ACACCAT	7
ACAG	2	2	1	FP	ACATAG	ACAAAG	6
ACCA	3	1	2	AB	ACCCA	AACAA	5
ACCA	2	2	2	AB	ACCCCA	ACAACA
ACCT	3	1	2	AB	ACCCT	AACTT	5
	2	2	2	AB	ACCCCT	ACATCT
	1	3	1	FP	ACCGCCT	ACCCCCT
ACTC	2	2	1	FP	ACGCTC	ACCCTC	6
ACTT	3	1	2	AB	ACCTT	AATTT	5
ACTT	1	3	1	FP	ACTGCTT	ACTCCTT
ACGA	2	2	2	AB	ACGCGA	ACAAGA	6
ACGT	2	2	2	AB	ACGCGT	ACATGT	6
ACGT	1	3	1	FP	ACGGCGT	ACGCCGT
ATAA	2	2	1	FP	ATACAA	ATAGAA	6
ATAT	1	3	1	FP	ATAGTAT	ATACTAT	7
ATCC	2	2	2	AB	ATCTCC	ATACCC	6
ATCT	1	3	1	FP	ATCGTCT	ATCCTCT	7
ATCG	2	2	2	AB	ATCTCG	ATAGCG	6
ATTT	3	1	1	FP	AGTTT	ACTTT	5
	2	2	1	FP	ATGTTT	ATCTTT
	1	3	1	FP	ATTGTTT	ATTCTTT
ATGC	2	2	2	AB	ATGTGC	ATACGC	6
ATGT	1	3	1	FP	ATGGTGT	ATGCTGT	7
ATGG	2	2	2	AB	ATGTGG	ATAGGG	6
AGAA	3	1	2	AB	AGGAA	AAAAA	5
AGAC	2	2	1	FP	AGAAAC	AGATAC	6
AGAT	1	3	1	FP	AGAGGAT	AGACGAT	7
AGCA	2	2	2	AB	AGCGCA	AGAACA	6

Table 2

(Continued)

Word (f)	2eo-length (l)	2eo-shift (r)	m	Type	Witness1 (u)	Witness2 (v)	Index ( $I_{L}$ (f))
AGCT	2	2	2	AB	AGCGCT	AGATCT	6
AGCT	1	3	1	FP	AGCGGCT	AGCCGCT
AGTT	3	1	2	AB	AGGTT	AATTT	5
AGTT	1	3	1	FP	AGTGGTT	AGTCGTT
AGTG	2	2	1	FP	AGGGTG	AGCGTG	6
AGGA	3	1	2	AB	AGGGA	AAGAA	5
AGGA	2	2	2	AB	AGGGGA	AGAAGA
AGGT	3	1	2	AB	AGGGT	AAGTT	5
	2	2	2	AB	AGGGGT	AGATGT
	1	3	1	FP	AGGGGGT	AGGCGGT

For example, referring to Table 2, there are three 2-Lee-error overlaps for $f = AAAT$ ; the first one has length 3 and shift 1, the second one has length 2 and shift 2, and the third one has length 1 and shift 3. Each one has a single error position ( $m = 1$ ) due to the occurrence of complementary symbols A and T. The corresponding pairs of Lee-witnesses are all of type FP; they are constructed as $(φ_{r} (f), ψ_{r} (f))$ following case 1. of Proposition 3. They are $(AAAGT, AAACT)$ , $(AAAGAT, AAACAT)$ , and $(AAAGAAT, AAACAAT)$ . The Lee-index is given by the length of the shortest witnesses, $I_{L} (f) = | AAAGT | = | AAACT | = 5$ .

Summing up, there are 38 Lee-non-isometric words f in $Δ^{*}$ that starts with A and have length 4. From these, 15 words have minimum Lee-index $| f | + 1 = 5$ , whereas 7 words have maximum Lee-index $2 | f | - 1 = 7$ ; the remaining 16 words have Lee-index 6. Moreover, there are 25 words with a single 2-Lee-error overlap, 9 words with two 2-Lee-error overlaps, and 4 with three 2-Lee-error overlaps. Overall, there are 152 Lee-non-isometric words of length 4 among all 256 words in $Δ^{4}$ . The asymptotic behaviour of the density of Ham-non-isometric binary words was determined in [16]. Recently, the density of Ham- and Lee-non-isometric k-ary words has been evaluated in [6].

Footnotes

Acknowledgements

The authors acknowledge support by INdAM-GNCS Project 2023, FARB Project ORSA229894 of University of Salerno, FFR and PNRR MUR Project ITSERR CUP B53C22001770006 of University of Palermo, TEAMS Project and PNRR MUR Project PE0000013-FAIR of University of Catania.

References

Anselmo ,

Castiglione ,

Flores ,

Giammarresi ,

Madonia and

Mantaci , Hypercubes and isometric words based on swap and mismatch distance, in: Descriptional Complexity of Formal Systems. DCFS 2023, Lect. Notes Comput. Sci., Vol. 13918, Springer, 2023, pp. 21–35. doi:10.1007/978-3-031-34326-1_2.

Anselmo ,

Castiglione ,

Flores ,

Giammarresi ,

Madonia and

Mantaci , Isometric words based on swap and mismatch distance, in: Developments in Language Theory. DLT23, Lect. Notes Comput. Sci., Vol. 13911, Springer, 2023, pp. 23–35. doi:10.1007/978-3-031-33264-7_3.

Anselmo ,

Flores and

Madonia , Quaternary n-cubes and isometric words, in: Combinatorics on Words,

Lecroq and

Puzynina , eds, Lect. Notes Comput. Sci., Vol. 12842, Springer International Publishing, 2021, pp. 27–39. doi:10.1007/978-3-030-85088-3_3.

Anselmo ,

Flores and

Madonia , On k-ary n-cubes and isometric words, Theor. Comput. Sci.938(6–7) (2022), 50–64. doi:10.1016/j.tcs.2022.10.007.

Anselmo ,

Flores and

Madonia , Fun slot machines and transformations of words avoiding factors, in: FUN with Algorithms 2022,

Fraigniaud and

Uno , eds, LIPIcs, Vol. 226, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 4–1415.

Anselmo ,

Flores and

Madonia , Density of Ham- and Lee- non-isometric k-ary words, in: ICTCS’23 Italian Conference on Theoretical Computer Science,

Castiglione and

Sciortino , eds, CEUR Workshop Proceedings, Vol. 3587, CEUR-WS.org, 2023, pp. 116–128.

Anselmo ,

Giammarresi ,

Madonia and

Selmi , Bad pictures: Some structural properties related to overlaps, in: DCFS 2020,

Jirásková and

Pighizzini , eds, Lect. Notes Comput. Sci., Vol. 12442, Springer, 2020, pp. 13–25. doi:10.1007/978-3-030-62536-8_2.

M.-P.

Béal and

Crochemore , Checking whether a word is Hamming-isometric in linear time, Theor. Comput. Sci.933(6–7) (2022), 55–59. doi:10.1016/j.tcs.2022.08.032.

Castiglione ,

Flores and

Giammarresi , Isometric words and edit distance: Main notions and new variations, in: Cellular Automata and Discrete Complex Systems. AUTOMATA 2023, Lect. Notes Comput. Sci., Vol. 14152, Springer, 2023, pp. 6–13.

10.

Crochemore and

Rytter , Jewels of Stringology, World Scientific, 2002. ISBN 978-981-02-4782-9.

11.

Fischer and

Heun, Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE, in: Combinatorial Pattern Matching, 17th Annual Symposium,

Lewenstein and

Valiente, eds, Lect. Notes Comput. Sci., Vol. 4009, Springer, 2006, pp. 36–48. doi:10.1007/11780441_5.

12.

Galil and

Giancarlo , Improved string matching with k mismatches, SIGACT News17(4) (1986), 52–54. doi:10.1145/8307.8309.

13.

Hsu , Fibonacci cubes-a new interconnection topology, IEEE Transactions on Parallel and Distributed Systems4(1) (1993), 3–12. doi:10.1109/71.205649.

14.

Ilić ,

Klavžar and

Rho , Generalized Fibonacci cubes, Discrete Math.312(1) (2012), 2–11. doi:10.1016/j.disc.2011.02.015.

15.

Klavžar , Structure of Fibonacci cubes: A survey, J. Comb. Optim.25(4) (2013), 505–522. doi:10.1007/s10878-011-9433-z.

16.

Klavžar and

S.V.

Shpectorov , Asymptotic number of isometric generalized Fibonacci cubes, Eur. J. Comb.33(2) (2012), 220–226. doi:10.1016/j.ejc.2011.10.001.

17.

G.M.

Landau and

Vishkin , Efficient string matching in the presence of errors, in: 26th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 1985, pp. 126–136. doi:10.1109/SFCS.1985.22.

18.

Wei , The structures of bad words, Eur. J. Comb.59 (2017), 204–214. doi:10.1016/j.ejc.2016.05.003.

19.

Wei ,

Yang and

Zhu , A characterization of non-isometric binary words, Eur. J. Comb.78 (2019), 121–133. doi:10.1016/j.ejc.2019.02.001.

20.

Wei and

Zhang , Proofs of two conjectures on generalized Fibonacci cubes, Eur. J. Comb.51 (2016), 419–432, ISSN 0195-6698. doi:10.1016/j.ejc.2015.07.018.