Crucial Words and the Complexity of Some Extremal Problems for Sets of Prohibited Words

Evdokimov A., Kitaev S.

September 30, 2001

Abstract

We introduced the notation of a set of prohibitions and give definitions of a complete set and a crucial word with respect to a given set of prohibitions. We consider 3 particular sets which appear in different areas of mathematics and for each of them examine the length of a crucial word. One of these sets is proved to be incomplete. The problem of determining lengths of words that are free from a set of prohibitions is shown to be NP-complete, although the related problem of whether or not a given set of prohibitions is complete is known to be effectively solvable.

1 Introduction and Background

In defining or characterising sets of objects in discrete mathematics, ”languages of prohibitions” are often used to define a class of objects by listing those prohibited subobjects that are not contained in the objects of the class. To this end the notion of a subobject is defined in different ways. The notion depends on the set under consideration. These sets are subwords for partially bounded languages, subgraphs for families of graphs and so on. One of the classes of interest that have appeared and are considered in different areas of mathematics is the class of nonrecurrent symbolic sequences defined by prohibiting strong periodicity in them, or, to be more exact, by prohibiting the repetition of subwords in these symbolic sequences, for example of type XX.

In this paper we consider 3 types of ”prohibitions” connected with a generalisation of the notion of nonrecurrent symbolic sequences, and for each of these sets we consider the structure of crucial words and find their lengths. In Section 5 we investigate the problem of determining lengths of words that are free from any given set of prohibitions. We show that this problem is NP-complete although the related problem whether or not a given set of prohibitions is complete is known to be effectively solvable.

Let A = {a_{1}, …, a_{n}} be an alphabet of n letters. A word in the alphabet A is a finite sequence of letters of the alphabet. Any i consecutive letters of a word X generate a subword of length i. If X is a subword of a word Y, we write X ⊆ Y.

The set A^{∗} is the set of all the words in the alphabet A. Let S ⊆ A^{∗}. Then S is called a set of prohibited words or a set of prohibitions. A word that does not contain any words from S as its subwords is said to be free from S. The set of all words that are free from S is denoted by Ŝ.

Example 1. Let A = {a, b}. The set of prohibitions is S = {aa, ba}. The word abbb is in Ŝ.

If there exists a k ∈ N such that the length of any word in Ŝ is less than k, then S is called a complete set.

Example 2. A = {1, 2, 3, 4}. The set of prohibitions is

S = {123, 13, 14, 11, 22, 33, 44 }.

Then S is incomplete, since the word \underbrace{124124 … 124}_{3k} is in Ŝ for any k.

Example 3. A = {1, 2, 3}. The set of prohibitions is

S = {12, 23, 31, 32, 11, 22, 33}.

It is easy to check that S is complete.

A word X ∈ Ŝ is called a crucial word (with respect to S), if the word Xa_{i} contains a prohibited subword for any letter a_{i} ∈ A. This means that Xa_{i} has the structure BB_{i}a_{i}, where B is some word and B_{i}a_{i} ∈ S. The subword B_{i} is called the i-ending of crucial word X. If for each letter of the alphabet we consider minimal i-ending (with respect to inclusion) we obtain a system of included i-endings, which we will use to investigate crucial words.

Example 4. A = {a, b, c}. The set of prohibitions is S = {aa, cab, acac}. The word abaca is crucial with respect to S.

A crucial word of minimal (maximal) length, if it exists, is called a minimal (maximal) crucial word.

Example 5. A = {a, b, c}. The set of prohibitions is S = {aa, cab, acac}. The word aca is a minimal crucial word with respect to S. There do not exist any maximal crucial words, since the word \underbrace{b … b}_{k} aca is crucial for all k ∈ N.

Let L_{min}(S) (L_{max}(S)) denote of the length of a minimal (maximal) crucial word with respect to S.

In this paper we consider three sets of prohibitions denoted S_{1}^{n}, S_{2}^{n}, S_{3}^{n,k}. Here we use n for indicating the number of letters of the alphabet under consideration and k is a natural number.

We now give the definitions of these sets:

S_{1}^{n} = {XX | X ∈ A^{∗}}, that is, we prohibit the repetition of two equal consecutive subwords.

S_{2}^{n} = \{XY | \overline{ν}(X) = \overline{ν}(Y)\}, where \overline{ν}(X) = (ν_{1}(X), …, ν_{n}(X)) is the content vector of X, in which ν_{i}(X) is the number of occurrences of the letter a_{i} in X. That is, we prohibit the repetition of two consecutive subwords of the same content.

S_{3}^{n,k} = {XY | d(X, Y) ≤ k, |X| = |Y | ≥ k + 1, k ∈ N}, where d(X, Y) is the number of letters in which the words X and Y differ (Hamming metric) and |X| is the length of the word X. That is we prohibit any two consecutive subwords of the length greater then k such that the number of positions in which these words differ is less then or equal to k.

The proofs of Theorems 1–5 consist of the constructions of extremal crucial words and of the proofs of their optimality, i. e. the lower bound for L_{min}(S) and the upper bound for L_{max}(S).

2 The Set of Prohibitions S_{1}^{n}

Theorem 1. We have

L_{min}(S_{1}^{n}) = 2^{n} − 1.

Proof.

We define a crucial word X by induction:

X_{1} = a_{1}, X_{i} = X_{i−1}a_{i}X_{i−1}, X = X_{n}.

From this construction it follows that |X| = 2^{n} − 1. We will prove that X is a minimal crucial word with respect to S_{1}^{n}.

Let U be an arbitrary minimal crucial word. We show that U coincides with the word X up to a permutation of letters in A.

From the definition of a crucial word it follows that in the word Ua_{i} there is a prohibited word of the form B_{i}a_{i}B_{i}a_{i}, where B_{i} is a certain word and B_{i}a_{i}B_{i}a_{i} is the ending of the word Ua_{i} (the ending may coincide with Ua_{i}). In this case the i-ending is the subword B_{i}a_{i}B_{i}. Let ℓ_{i} = B_{i}a_{i}B_{i}.

We assume that ℓ_{1} ⊂ ℓ_{2} ⊂ … ⊂ ℓ_{n}, since we can make such ordering by permuting the letters of the alphabet, which obviously does not affect the cruciality and minimality of a word.

Note that the minimal crucial word U has the form

U = B_{n}a_{n}B_{n} = B_{n}a_{n}Y_{n}a_{1},

where Y_{n} is a certain word. Actually, if on the right of B_{n}a_{n}B_{n} there is a certain word, then it contradicts the minimality of a crucial word, and if instead of a_{1} there stands a_{k} (k > 1) then it contradicts ℓ_{1} ⊂ ℓ_{k}.

We show that ℓ_{n−1} coincides with B_{n}. We have ℓ_{n−1} = B_{n−1}a_{n−1}B_{n−1} and let a_{n}B_{n} be a subword of ℓ_{n−1}. Now ℓ_{n−1} has the form Ka_{n}P a_{n−1}Ka_{n}P, where Ka_{n}P = B_{n−1}), but then

ℓ_{n} = P a_{n−1}Ka_{n}P a_{n−1}Ka_{n}P, where P a_{n−1}Ka_{n}P = B_{n},

and the word U contains the prohibited subword a_{n}P a_{n}P. This can not be the case. It means that ℓ_{n−1} is a subword of the word B_{n}, and the word U has the form:

U = ℓ_{n} = Z_{n}ℓ_{n−1}a_{n}Z_{n}ℓ_{n−1},

where Z_{n} is a certain word. Since we explore a minimal crucial word, we have Z_{n} = ∅, and then B_{n} = ℓ_{n−1}. In the same way we can show that B_{i} = ℓ_{i−1} for each i = 2, …, n − 1 and B_{1} = ∅.

Hence the structure of a minimal crucial word U coincides with that of the word X as required.

Remark. From the proof of Theorem 1 it follows that the word X is the unique minimal crucial word to within a transposition of the letters of the alphabet A.

3 The Set of Prohibitions S_{2}^{n}

Proposition 1.

A minimal crucial (with respect to S_{2}^{n}) word can not have three letters, each of which appears twice in the word.

Proof.

Since the proposition is obviously true for |A| = 1, 2, 3, we will consider the case |A| ≥ 4.

Let X be a minimal crucial word, and suppose the system of included i-endings for it is ℓ_{1} ⊂ ℓ_{2} ⊂ … ⊂ ℓ_{n} = X. Suppose the letters a_{i_{1}}, a_{i_{2}}, a_{i_{3}} occur twice in X and that i_{1} < i_{2} < i_{3} < n (the fact that i_{1}, i_{2}, i_{3} do not equal n follows from the fact that a_{n} must occur an odd number of times).

When we pass from ℓ_{i_{3}−1} to ℓ_{i_{3}} (ℓ_{i_{3}−1} is determined, since there are i_{1}, i_{2} < i_{3}) there must appear a letter a_{i_{3}}, and when we pass from ℓ_{i_{3}} to ℓ_{i_{3}+1} (ℓ_{i_{3}+1} is determined, since i_{3} < n) there must appear one more letter a_{i_{3}}; Hence, since there are two letters a_{i_{3}} in X, there are no letters a_{i_{3}} for 2 < j < i_{3} in ℓ_{j} whence there are no letters a_{i_{3}} in the X to the left of ℓ_{i_{2}} (both letters a_{i_{3}} lie to the left respecting of ℓ_{i_{2}}).

Obviously, the letter a_{i_{1}} must be in ℓ_{i_{1}}. The second letter a_{i_{1}} appears when we pass from ℓ_{i_{1}} to ℓ_{i_{2}}. Since there are only two letters a_{i_{1}}, there are no letters a_{i_{1}} in the word X to the left of ℓ_{i_{2}}.

If we write the letter a_{i_{3}+1} to the right of the word X we obtain a prohibited word (a word from S_{2}^{n}). Words from S_{2}^{n} are divided into two parts which have the same content. Obviously, the letters a_{i_{3}} must be in different parts of the prohibited word, and letters a_{i_{1}} must be in different parts of the same word which is impossible, since the letters a_{i_{3}} lie strictly to the left of a_{i_{1}}, and this contradicts the assumption.

Remark. From the proof of proposition 1 we have that if letters a_{i} and a_{j} occur twice in a word X (in which ℓ_{1} ⊂ ℓ_{2} ⊂ … ⊂ ℓ_{n} = X), then either i = j + 1 or j = i + 1.

Theorem 2. For any n > 2 we have

L_{min}(S_{2}^{n}) = 4n − 7.

Proof.

Note that a natural approach to the construction of a crucial word is possible. It consists of an algorithm of step-by-step optimisation: We ascribe to a crucial word of an n-letter alphabet a minimum number of letters to obtain a crucial word of an (n + 1)-letter alphabet.

The algorithm can be written recursively in the following way:

X_{n} = B_{n−1}a_{n}B_{n−1}

B_{n−1} = B_{n−3}a_{n−1}B_{n−3}

B_{1} = a_{1}, B_{2} = a_{2}, B_{−1} = B_{0} = X_{0} = ∅.

Some initial values when implementing the algorithm are:

X_{1} = a_{1},

X_{2} = a_{1}a_{2}a_{1},

X_{3} = a_{2}a_{3}a_{1}a_{2}a_{1},

X_{4} = a_{1}a_{3}a_{1}a_{4}a_{2}a_{3}a_{1}a_{2}a_{1},

X_{5} = a_{2}a_{4}a_{2}a_{5}a_{1}a_{3}a_{1}a_{4}a_{2}a_{3}a_{1}a_{2}a_{1}.

This is an algorithm by which the minimal crucial word X_{n} for the set of prohibitions S_{1}^{n} can be built. For S_{2}^{n} such a construction gives an upper bound of the form exp(n/2), or, to be more exact,

(3 − (n mod 2))2^{⌊ \frac{n+1}{2} ⌋} − 3.

We now give an upper bound that is a linear function.

We introduce, as before, a system of included i-endings: ℓ_{1} ⊂ ℓ_{2} ⊂ … ⊂ ℓ_{n} (we permute the letters of the alphabet if it is necessary). We show that the passage from ℓ_{i−1} to ℓ_{i} is possible by adding only two symbols (letters of alphabet A).

When we passed from ℓ_{i−1} to ℓ_{i} let there appear symbols y and z. ℓ_{i−1} may be denoted by AB, where A is a certain word, B consists of the letters of the word A (which are somehow mixed) and B contains one letter a_{i−1} less than A does. Let x be the last letter of the word A on the right. Then ℓ_{i} may be denoted by yzKxB, where A = Kx. From the definition of ℓ_{i} we have the equation

y ∪ z ∪ K = B ∪ x ∪ a_{i}.

which from the definition of K and B is equivalent to

2x ∪ a_{i} = y ∪ z ∪ a_{i}.

It follows necessarily that x = a_{i−1} and either y = a_{i−1}, z = a_{i} or y = a_{i}, z = a_{i−1}. Suppose y = a_{i−1}, z = a_{i}. For example, we have the following crucial word for a 6-letter alphabet:

a_{4}a_{5}a_{3}a_{4}a_{2}a_{3}a_{1}a_{2}|a_{6}a_{4}a_{3}a_{2}a_{1}a_{2}a_{3}a_{4}a_{6},

(the vertical line was drawn for a more convenient visual perception of the word). This word is crucial and its length is equal to 17. We consider a case of an arbitrary n ≥ 3 defining the word W as

W = a_{n−2}a_{n−1}a_{n−3}a_{n−2} … a_{1}a_{2}|a_{n}a_{n−2}a_{n−3} … a_{2}a_{1}a_{2} … a_{n−3}a_{n−2}a_{n}.

Then |W | = 2(n − 2) + n − 1 + n − 2 = 4n − 7.

Let us verify that the word W is crucial.

If we write the letters a_{1}, a_{2}, a_{n} to the right of the word W we will obviously have prohibited subwords. Let 2 < i < n. Then if we write the letters a_{i} we will have the prohibition

a_{i−1}a_{i} … a_{1}a_{2}a_{n}a_{n−2} … a_{i}|a_{i−1} … a_{2}a_{1}a_{2} … a_{n−2}a_{n}a_{i},

since the composition vectors of the left and right subwords with respect to the vertical line are equal.

Before proving that W ∈ Ŝ_{2}^{n} we make the following remark.

In the word W we have ℓ_{n} ⊂ ℓ_{1} ⊂ … ⊂ ℓ_{n−2} ⊂ ℓ_{n−1}. Substituting a_{1} for a_{n}, a_{2} for a_{1}, …, a_{n} for a_{n−1} we obtain another word

U = a_{n−1}a_{n} … a_{2}a_{3}|a_{1}a_{n−1} … a_{3}a_{2}a_{3} … a_{n−1}a_{1},

for which ℓ_{1} ⊂ ℓ_{2} ⊂ … ⊂ ℓ_{n}.

In both cases (before and after substitution of letters of the alphabet) we have the construction of a crucial word (which will be proved below) hence the same upper bound of the length of a minimal crucial word.

For W it is more convenient to show further that W ∈ Ŝ_{2}^{n}.

We rewrite W making in it the marks (1),(2), …,(2n-4), which number the gaps between letters of a word like this:

(2n − 4)a_{n−2}(2n − 5)a_{n−1} … (2)a_{1}(1)a_{2}|a_{n}a_{n−2} … a_{2}a_{1}a_{2} … a_{n−2}a_{n}.

In a possible prohibition we mark the left and right bounds. Note that the length of a prohibition is an even number, and each letter must occur an even number of times in a prohibition. The left bound of the prohibition must lie to the right of the mark (2n-5), since the letter a_{n−1} enters W once;

It must lie to the left of the mark (1), since to the right of the mark (1) there is one letter a_{1}.

Note that if m is even then (m) is not the left bound of the possible prohibition. Actually in this case two variants are possible:

1) the prohibition does not cover the left letter a_{n}.

2) the prohibition covers the left letter a_{n}.

In the second case we have not a prohibition, since if the prohibition begins from the even mark, then it can not cover the second a_{n}.

In the first case the right bound of the prohibition lies to the left of a_{n}, hence the letter a_{\frac{m}{2} +1} enters the prohibition only once.

Suppose the prohibition begins from the mark (m) and m is odd.

There are two possible cases.

1) The prohibition does not cover the left letter a_{n} (this case is impossible since the letter a_{⌊ \frac{m}{2} ⌋} occurs the prohibition once).

2) The prohibition covers the left a_{n}. Then it covers the right a_{n} too, and the letter a_{⌊ \frac{m}{2} ⌋} occurs an odd number of times in the prohibition. So W ∈ Ŝ_{2}^{n} and hence L_{min}(S_{2}^{n}) ≤ 4n − 7 for n > 2.

We give now a lower bound.

Since the length of a minimal crucial word must be odd, and the passage from ℓ_{i} to ℓ_{i+1} requires at least two letters, we have that a trivial lower bound of the length of a minimal crucial word is 2n − 1.

Let us now improve the lower bound. Obviously a minimal crucial word in which ℓ_{1} ⊂ ℓ_{2} ⊂ … ⊂ ℓ_{n} has an even number of occurrences of the letter a_{i} for i = 1, …, n − 1 and an odd number of occurrences of the letter a_{n}. The word U has two letters a_{1}, two letters a_{2}, one letter a_{n} and four of any other letter. From proposition 1 we know that there does not exist a crucial word that has the fewer number of letters, hence the word U gives us the lower bound of the length of a minimal crucial word.

4 The Set of Prohibitions S_{3}^{n,k}

Theorem 3. We have

L_{min}(S_{3}^{n,k}) = 2k + 1.

Proof.

For the set of prohibitions S_{3}^{n,k} we must have |A| = |B| ≥ k + 1, where AB is an arbitrary prohibition. So we have

L_{min}(S_{3}^{n,k}) ≥ 2k + 1.

An upper bound is given by the construction p_{1}p_{2} … p_{k}xp_{1}p_{2} … p_{k}, where x, p_{i} ∈ A, i = 1, …, k and x ≠ p_{i}.

Remark. The crucial word with respect to S_{3}^{1,k} is unique and its length is 2k+1.

Theorem 4. We have

L_{max}(S_{3}^{2,k}) = 3k + 3.

Proof.

Let

ā = \{ \begin{matrix}1, & if a = 2, \\ 2, & if a = 1. \end{matrix}

Moreover, let us consider an arbitrary crucial word A, with respect to S_{3}^{2,k}, of length greater then 3k + 3. It is easy to see that if a_{1}a_{2} … a_{k+1} are the first k + 1 letters of A then the next k + 1 letters of A must be ā_{1}ā_{2} … ā_{k+1}, because otherwise the first 2k + 2 letters of A will form a prohibited subword. By the same argument, we can show that

A = a_{1}a_{2} … a_{k+1}ā_{1}ā_{2} … ā_{k+1}a_{1}a_{2} … a_{k+1}ā_{1} ….

Let us consider the subwords A_{i} of A of the length 2k + 4 which start from the ith letter, where 1 ≤ i ≤ k:

A_{i} = \underbrace{a_{i}a_{i+1} … a_{k+1}ā_{1} … ā_{i}}_{k+2} \underbrace{ā_{i+1} … ā_{k+1}a_{1} … a_{i+1}}_{k+2}

If a_{i} = ā_{i+1} then the underbraced subwords of A_{i} are the same in the first and in the last positions, so they differ in at most k positions, hence A_{i} is prohibited. So we must have a_{i} = a_{i+1} for i = 1, …, k.

Without loss of generality we can assume that a_{1} = 1, so

A = \underbrace{11 … 1}_{k+1} \underbrace{22 … 2}_{k+1} \underbrace{11 … 1}_{k+1} 2 ….

It is easy to see that if the length of A is greater then 3k + 3 then A has a prohibited subword of length 2k + 4:

A = \underbrace{11 … 1}_{k} \overbrace{1 \underbrace{22 … 2}_{k+1}} \overbrace{\underbrace{11 … 1}_{k+1} 2} 2 ….

(here and then two braces above an word show us a disposition of a prohibited subword and, in particular, a disposition of parts of this subword that correspond to X and Y from the definition of the set of prohibitions S_{3}^{n,k}).

So L_{max}(S_{3}^{2,k}) ≤ 3k + 3.

To prove the theorem it is sufficient to check that there are no prohibited sub-

words in the word A = \underbrace{11 … 1}_{k+1} \underbrace{22 … 2}_{k+1} \underbrace{11 … 1}_{k+1}.

Obviously the left end of a possible prohibition can be only in the left block

\underbrace{1 … 1}_{k+1}:

\overbrace{\underbrace{1 … 1}_{j} \underbrace{2 … 2}_{i}} \overbrace{\underbrace{2 … 2}_{k−i+1} \underbrace{1 … 1}_{2i+j−k−1}}

with

j + i ≥ k + 1  (1)

Two cases are possible:

1. j ≥ k − i + 1
2. j < k − i + 1

In the first case there is non-coincidence between the left and right parts of the prohibition in the first k−i+1 letters and in the last i letters that is non-coincidence in k + 1 letters. So this case is impossible.

In the second case we have non-coincidence in the first j letters and in the last 2i + j − k − 1 letters. Hence we have non-coincidence in 2(i + j) − k − 1 letters, that according to (1) is greater than or equal to k + 1.

It follows that the word \underbrace{1 … 1}_{k+1} \underbrace{2 … 2}_{k+1} \underbrace{1 … 1}_{k+1} does not contain a prohibition and

thus the theorem is proved.

Theorem 5. [Incompleteness] The set of prohibitions S_{3}^{n,k} for n ≥ 3 is incomplete.

Proof.

Since the alphabet A is finite, there is no trivial solution of the problem (such as taking all letters of A and obtaining an infinite sequence with the properties needed). So to prove the incompleteness of the set S_{3}^{n,k} we have to show the existence of an infinite word which is free from the set of prohibitions S_{3}^{n,k}.

We consider the case n = 3 and the alphabet A = {1, 2, 3}, since the incompleteness of the set of prohibitions S_{3}^{n,k} for the case n > 3 will follow from the incompleteness of the set of prohibitions for the case n = 3.

Let B = {a, b, c} be an alphabet. B^{∗} is the set of all words of the alphabet B. We define the mapping f as follows:

\underbrace{1 … 1}_{k+1} → a, \underbrace{2 … 2}_{k+1} → b, \underbrace{3 … 3}_{k+1} → c.

The domain of the mapping f is the set of words of the alphabet

C = \{ \underbrace{1 … 1}_{k+1}, \underbrace{2 … 2}_{k+1}, \underbrace{3 … 3}_{k+1} \}.

The image of the mapping f is the set B^{∗}.

Let the set of prohibitions S′ = {XX|X ∈ B^{∗}}. Obviously, the set S′ coincides with the set S_{2}^{n} whenever A = B.

It is known [1] that for the alphabet B there exists the infinite sequence L′ which is free from the set of prohibitions S′. L′ is built by iteration of morphisms:

a → abc
b → ac
c → b

The morphism iteration procedure is as follows.

We start from the letter a. Then we substitute this letter with abc. Then we substitute each letter in abc by the rule above. We obtain after this step abcacb. And so on. Executing this procedure an infinite number of times gives us the sequence L′.

Let us prove that the sequence L = f^{−1}(L′) does not contain words prohibited by S_{3}^{3,k}.

We are going to prove the statement by considering L and all possible dispositions of words prohibited by S_{3}^{3,k}.

The sequence L is built up from the letters of the alphabet C or in other words from the blocks \underbrace{x … x}_{k+1}, where x ∈ \{1, 2, 3\}. It means that there are only three

different cases for a disposition of a possible prohibition in L.

Case 1. \overbrace{\underbrace{x … x}_{k+1} … \underbrace{y … y}_{k+1}} \overbrace{\underbrace{z … z}_{k+1} … \underbrace{t … t}_{k+1}} ;

Case 2. \underbrace{x … x}_{i} \overbrace{\underbrace{x … x}_{k−i+1} … \underbrace{y … y}_{k+1}} \overbrace{\underbrace{z … z}_{k+1} … \underbrace{t … t}_{k−i+1}} \underbrace{t … t}_{i} , where 0 < i < k + 1;

Case 3. \underbrace{x … x}_{i} \overbrace{\underbrace{x … x}_{k−i+1} … \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} … \underbrace{t … t}_{k−j+1}} \underbrace{t … t}_{j} , where 0 ≤ i, j, l ≤ k + 1.

Now we will consider these cases and show that each of them is impossible.

Case 1. Let P denote the prohibited subword (prohibition) under consideration, R and L denote the right and the left parts of P respectively.

It is obvious that L and R have the same number of blocks. Moreover, the ith block of L (from the left to the right) is equal to the ith block of R, because otherwise we have non-coincidence of L and R in at least k + 1 letters which contradicts the fact that P ∈ S_{3}^{3,k}. So we have that P = W W for some W ∈ C^{∗}.

Now, f(P) = f(W)f(W) is a subword of L′. But f(W)f(W) ∈ S′ which is impossible by the properties of L′. So Case 1 is impossible.

Note. As an important consequence of Case 1 we have the following. If

\underbrace{x … x}_{k+1} \underbrace{y … y}_{k+1} is a subword of L then x ≠ y.

Case 2. If there are no letters between \underbrace{x … x}_{k+1} and \underbrace{y … y}_{k+1}, that is

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{y … y}_{k+1}} \overbrace{\underbrace{z … z}_{k+1} \underbrace{t … t}_{k−i+1}} ,

then we must have x = z, because otherwise we have x ≠ z and y ≠ z which gives us that L and R differ in the first k + 1 positions, but this contradicts P ∈ S_{3}^{3,k}.

By the same argument we have y = t, so

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{y … y}_{k+1}} \overbrace{\underbrace{x … x}_{k+1} \underbrace{y … y}_{k−i+1}} .

But if we consider now f(L) = L′ then it has

P′ = \overbrace{f(\underbrace{x … x}_{k+1})f(\underbrace{y … y}_{k+1})} \overbrace{f(\underbrace{x … x}_{k+1})f(\underbrace{y … y}_{k+1})} .

as a subword, which is impossible since P′ ∈ S′.

So there is some non-empty subword in L between \underbrace{x … x}_{k+1} and \underbrace{y … y}_{k+1}, and P can

be written as

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{x_{1} … x_{1}}_{k+1} … \underbrace{x_{p} … x_{p}}_{k+1} \underbrace{y … y}_{k+1}} \overbrace{\underbrace{z … z}_{k+1} \underbrace{z_{1} … z_{1}}_{k+1} … \underbrace{z_{p} … z_{p}}_{k+1} \underbrace{t … t}_{k−i+1}} .

There are two possible subcases here.

1. x = z. Since x ≠ x_{1} we have x_{1} ≠ z. If x_{1} ≠ z_{1} then L and R differ in k + 1 position

starting from the (k − i + 2)th position, which is impossible since P ∈ S_{3}^{3,k}. So x_{1} = z_{1}.

In the same way, for each of x_{2}, x_{3}, … x_{p}, y, we can obtain that

P = \overbrace{\underbrace{z … z}_{k−i+1} \underbrace{z_{1} … z_{1}}_{k+1} … \underbrace{z_{p} … z_{p}}_{k+1} \underbrace{t … t}_{k+1}} \overbrace{\underbrace{z … z}_{k+1} \underbrace{z_{1} … z_{1}}_{k+1} … \underbrace{z_{p} … z_{p}}_{k+1} \underbrace{t … t}_{k−i+1}}

which leads us to the fact that L has a subword W W for some W ∈ C^{∗}, hence L′ has a subword f(W)f(W) which is impossible.

So the subcase 1 is impossible.

2. x ≠ z. If x_{1} ≠ z then L and R differ in k + 1 position starting from the first position,

which is impossible since P ∈ S_{3}^{3,k}. So x_{1} = z.

If x_{2} ≠ z_{1} then L and R differ in k + 1 position starting from the (k + 2)th position, what is impossible by the same arguments as above. So x_{2} = z_{1}. And so on.

We have

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{z … z}_{k+1} \underbrace{z_{1} … z_{1}}_{k+1} … \underbrace{z_{p} … z_{p}}_{k+1}} \overbrace{\underbrace{z … z}_{k+1} \underbrace{z_{1} … z_{1}}_{k+1} … \underbrace{z_{p} … z_{p}}_{k+1} \underbrace{t … t}_{k−i+1}} .

Applying f to L gives us a subword P′ of L′,

P′ = \overbrace{f(\underbrace{z … z}_{k+1})f(\underbrace{z_{1} … z_{1}}_{k+1}) … f(\underbrace{z_{p} … z_{p}}_{k+1})} \overbrace{f(\underbrace{z … z}_{k+1})f(\underbrace{z_{1} … z_{1}}_{k+1}) … f(\underbrace{z_{p} … z_{p}}_{k+1})},

which is prohibited in L′ by S′.

We have got that subcase 2 is impossible and hence Case 2 is impossible.

Case 3. We can assume that ℓ ≠ 0 and ℓ ≠ k + 1, because otherwise we deal with either Case 1 or Case 2 which are impossible.

We suppose that i ≥ ℓ (the case i < ℓ can be considered in the same way). If there are no letters between \underbrace{y … y}_{k−ℓ+1} and \underbrace{t … t}_{k−j+1}, then we have either

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} \underbrace{t … t}_{k−j+1}}

or

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{z … z}_{k+1} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} \underbrace{t … t}_{k−j+1}} .

In the first of these cases we have that x ≠ y and y ≠ t which gives us that L and R have non-coincidence in at least k + 1 letters, but this contradicts P ∈ S_{3}^{3,k}.

In the second case we must have z = t, because otherwise since z ≠ y and t ≠ y, L and R have non-coincidence in the last k + 1 letters which is impossible. So in the second case we have

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{t … t}_{k+1} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} \underbrace{t … t}_{k−j+1}} .

If x ≠ y then L and R have non-coincidence in the first k − ℓ + 1 positions and in the last ℓ positions, that is they have non-coincidence in at least k + 1 positions which is impossible. So x = y.

Now applying f to L gives us that L′ has a subword

P′ = \overbrace{f(\underbrace{x … x}_{k+1})f(\underbrace{t … t}_{k+1})} \overbrace{f(\underbrace{x … x}_{k+1})f(\underbrace{t … t}_{k+1})}

which is impossible.

So there is some non-empty subword in R between \underbrace{y … y}_{k−ℓ+1} and \underbrace{t … t}_{k−j+1}, and P can

be written in the form

P = \overbrace{\underbrace{x … x}_{k−i+1} L_{1} … L_{p} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p′} \underbrace{t … t}_{k−j+1}} ,

where L_{s}, R_{m} ∈ C, for 1 ≤ s ≤ p, 1 ≤ m ≤ p′, and either p = p′ or p = p′ + 1. We define △(L_{s}) = x_{s} if L_{s} = \underbrace{x_{s} … x_{s}}_{k+1}. In the same way we define △(R_{m}).

Let us consider two cases:

1. p = p′. There are two subcases here:

a) x = y; Since △(L_{1}) ≠ x we must have L_{1} = R_{1}, because otherwise L and R have non-coincidence in the k + 1 letters starting from the (k − i + 2)th position, which is impossible.

Since △(L_{2}) ≠ △(L_{1}), that is △(L_{2}) ≠ △(R_{1}), we must have L_{2} = R_{2}, because otherwise L and R have non-coincidence in the k + 1 letters starting from the (2k − i + 3)th position, which is impossible. And so on. For each of of L_{3}, …, L_{p} we have that

P = \overbrace{\underbrace{y … y}_{k−i+1} R_{1} … R_{p} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p} \underbrace{t … t}_{k−j+1}} .

So we have got that L has W W as a subword, where W = \underbrace{y … y}_{k+1} R_{1} … R_{p}, but it

means that L′ has f(W)f(W) as a subword which is impossible.

b) x ≠ y; There are two special subcases here, namely either △(L_{1}) = y or L_{1} = R_{1}.

When △(L_{1}) = y it must be that L_{2} = R_{1}, because otherwise, since △(R_{1}) ≠ y, L and R have non-coincidence in the k + 1 letters starting from the (k − l + 2)th position, which is impossible.

By similar reasoning for L_{3}, …, L_{p} we have that

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{y … y}_{k+1} R_{1} … R_{p−1} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p} \underbrace{t … t}_{k−j+1}} .

Again, L has W W as a subword, where W = \underbrace{y … y}_{k+1} R_{1} … R_{p−1}, which is impos-

sible by the same reasons as above.

So L_{1} = R_{1}.

Using the same technique of as above we can easily obtain that in this case

P = \overbrace{\underbrace{x … x}_{k−i+1} R_{1} … R_{p} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p} \underbrace{t … t}_{k−j+1}} .

If y ≠ t then L and R have non-coincidence in the first k − ℓ + 1 positions and in the last ℓ positions, so they have non-coincidence in k+1 positions which contradicts P ∈ S_{3}^{3,k}.

If y = t then

P = \overbrace{\underbrace{x … x}_{k−i+1} R_{1} … R_{p} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p} \underbrace{y … y}_{k−j+1}}

and L has W W as a subword, where W = R_{1} … R_{p} \underbrace{y … y}_{k+1} which is impossible.

2. p = p′ + 1. There are two subcases here:

a) x = y; It must be that L_{1} = R_{1}, because otherwise L and R differ in k + 1 positions starting from the (k − i + 2)th position. Then we consider L_{2}, L_{3}, …,L_{p}.

We can see that in this subcase

P = \overbrace{\underbrace{y … y}_{k−i+1} R_{1} … R_{p′} \underbrace{t … t}_{k+1} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p′} \underbrace{t … t}_{k−j+1}} ,

and L has W W as a subword, where W = \underbrace{y … y}_{k+1} R_{1} … R_{p′} \underbrace{t … t}_{k+1} which is impossible.

b) x ≠ y; There are two special subcases here, namely either △(L_{1}) = y or L_{1} = R_{1}.

If △(L_{1}) = y then

P = \overbrace{\underbrace{x … x}_{k−i+1} \underbrace{y … y}_{k+1} R_{1} … R_{p′} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p′} \underbrace{t … t}_{k−j+1}} ,

and L has W W as a subword, where W = \underbrace{y … y}_{k+1} R_{1} … R_{p′} which is impossible.

So L_{1} = R_{1}. In this case we have

P = \overbrace{\underbrace{x … x}_{k−i+1} R_{1} … R_{p′} \underbrace{t … t}_{k+1} \underbrace{y … y}_{ℓ}} \overbrace{\underbrace{y … y}_{k−ℓ+1} R_{1} … R_{p′} \underbrace{t … t}_{k−j+1}} .

Since y ≠ x, y ≠ △(R_{1}) and y ≠ t, L and R have non-coincidence in the first k − l + 1 positions and in the last l positions, so they have non-coincidence in k + 1 positions which contradicts P ∈ S_{3}^{3,k}.

We have got that Case 3 is impossible.

We have proved that the infinite word L contains no word from the set S_{3}^{3,k} as a subword, therefore S_{3}^{n,k} is incomplete for n ≥ 3.

5 The Complexity of Problems on Completeness of Sets of Words

It is known [3, 4] that the complexity of deciding whether or not an arbitrary set of prohibited words S is complete (or blocking) is O(|S| · n), where n is the greatest length of a word in S.

It is interesting in its own right to be able to effectively (in polynomial time) recognise whether a set is complete, but also to give a more detailed characterisation of the set of words Ŝ, in particular to find the greatest length of a word that is free from S. The set A^{n} is the set of all the words in the alphabet A whose length is equal to n. If S ⊆ A^{n} and L(n) = max_{S} L(Ŝ), where L(Ŝ) is the greatest length of a word that is free from S, then [3] we have

L(n) = |A|^{n−1} + n − 2 = C(n) + n − 1.

Here C(n) is the greatest length of a single path in the de Bruijn graph of order n that has no chords and does not go through the vertices with loops corresponding to the constant words (x, …, x) where x ∈ A.

One can find all words that are free from S, in particular all crucial words, simply by considering all words of length less than or equal to L(Ŝ) and checking for each word, if it is free from S. Such an algorithm is not effective since it can require considering |A|^{L(n)} words.

The question of deciding the possible lengths of words that are free from S, in particular of crucial words, can be formulated as a problem of recognising properties of “languages of prohibitions” in the terminology of the theory of NP-completeness [6].

Problem A:

Given: An arbitrary set of words S and a natural number ℓ.

The question: Does there exist a word of length at least ℓ that is free from S?

In order to compare, we formulate the problem of completeness of a set of words S in the same form.

Problem B:

Given: An arbitrary set of words S in an alphabet A.

The question: Does there exist ℓ ∈ N such that |X| ≤ ℓ for any word X that is free from S?

Considering problems A and B as problems of recognising properties of finite sets S, we observe that problem B is a question of existence of a bound on the length of the words that are free from S. This problem, as we have already mentioned, can be solved effectively with complexity of order |S|·n. In the same time the problem A is a question of determining of this bound. We will show that problem A, as opposed to problem B, is NP-complete.

The research on the problems of completeness of sets of words and languages of prohibited subwords was begun by different authors [1, 3, 4, 5, 7, 9] in the 1970s. The interest in the general question in this area arose from considerations of different types of special problems, in particular, in coding theory, combinatorics of symbolic sequences, number theory and problems of Ramsey type (for instance the arithmetic progressions in partitions of the natural row). For algebraic problems it is more typical to study avoidance of infinite sets S that are defined by prohibitions of words (called terms) in an alphabet of variables that can themselves be words [1, 9]. Different problems on sequences without repetitions, under variation the concept of “strong” or “weak” repetition of subwords, are the typical examples of problems of this class. Finally we observe that problems A and B for infinite sets S do not make sense if one does not consider particular constructive methods for generating a set S.

Let A = {a_{1}, …, a_{n}} be an alphabet and A_{ℓ} be the set of all those words on the alphabet A whose length is less than or equal to ℓ. We assume also that the empty word belongs to A_{ℓ} and that S_{1} is an arbitrary set such that S_{1} ⊆ A_{2} \ A_{1}. We define S_{2} by

S_{2} = {xXx| x ∈ A, X ∈ A^{n−1}}.

So the set S_{2} contains all possible words of length less than or equal to n + 1 whose first letter coincides with their last letter. Suppose S = S_{1} ∪ S_{2}.

We now consider an “auxiliary” problem A′.

Problem A′:

Given: A set S of the type described above and a natural number ℓ, ℓ ≤ n. The question: Does there exist a word of length at least ℓ that is free from S?

In case of the problem A′, the restriction on ℓ is natural, because any word free from S is free from S_{2} and therefore consists of different letters of the alphabet, whence its length is less than or equal to n.

Checking whether a given word of length ℓ (a solution of A′ that we “guessed”) is free from S can be done in polynomial time. Indeed, the freeness from S_{2} of the word is equivalent to the absence of identical letters in the word (which can be checked in linear time) and the freeness from S_{1} is recognised by considering all subwords of length 2 (there are ℓ − 1 such subwords) and by checking for each of them whether it belongs to S_{1} (polynomial checking time).

We now introduce the problem of “the longest path in a graph”, which is known to be NP-complete (see [6]).

Problem “path”:

Given: A directed graph G⃗(V, E) and a natural number ℓ, ℓ ≤ |V | = n.

The question: Does there exist a simple directed path (without self-intersections in vertices) of length at least ℓ?

One can obtain a correspondence between problem A′ and problem “path” as follows. We compare vertices v_{1}, …, v_{n} from V (G⃗) to the letters a_{1}, …, a_{n} in the alphabet A. Also we compare each edge v⃗_{i}v_{j} from E(G⃗) to the word a_{i}a_{j}. We form the set S_{1} from all such words of A^{2} that correspond to the edges of the graph that is the complement of G⃗ with respect to the complete directed graph.

Now to any oriented simple path v_{i_{1}}, …, v_{i_{ℓ}} of length ℓ in G⃗ there corresponds the word a_{i_{1}} … a_{i_{ℓ}} of length ℓ, consecutive letters of which correspond to vertices in the order in which the path passed through them. This word is free from S_{1} because a_{i_{j}}a_{i_{j+1}} ∉ S_{1} for any i = 1, 2, …, ℓ − 1. The word is free from the set S_{2} as well because in the path there is no repetition of vertices (a property of a simple path) and therefore a_{i_{1}} … a_{i_{ℓ}} does not contain a subword of the form a_{i}Xa_{i} for any word X and any letter a_{i} ∈ A.

Conversely, to any word in the alphabet A that is free from S there corresponds a path in G⃗(V, E) that goes through edges from E(G⃗) since the word is free from S_{1} and that is not self-intersected since the word is free from S_{2}.

Now NP-completeness of problem A′ and the more general problem A follows from NP-completeness of the problem “path”.

References

[1] Bean D. R., Ehrenfeucht A., McNulty G. F., Avoidable patterns in strings of symbols, Pacific J. Math., Vol. 85, No. 2, (1979), 261-294.

[2] Choffrut C., Karhumäki J., Handbook of formal languages, Vol. 1: Word, language, grammar, Berlin, Springer, (1997), 329-438.

[3] Evdokimov A., Complete sets of words and their numerical characteristics, Metody Diskret. Analiz., Novosibirsk, IM SB RAS, No. 39, (1983), 7-32 (in Russian). Also 86e:68087 in the Mathematical Reviews on the Web.

[4] Evdokimov A., The completeness of sets of words, Proceedings of the All-Union seminar on discrete mathematics and its applications (Russian) (Moscow, 1984), Moskov. Gos. Univ., Mekh.-Mat. Fak., Moscow, (1986), 112-116 (in Russian). Also 89e:68066 in the Mathematical Reviews on the Web.

[5] Evdokimov A., Krainev V., Problems on completeness of sets of words, Proceedings of the 22nd regional scientific conference by the Popov association, Novosibirsk, (1979), 105-107 (in Russian).

[6] Garey M., Johnson D., Computers and intractability: a guide to the theory of NP-completeness, W. H. Freeman, (1979).

[7] Lothaire M., Combinatorics on Words, Encyclopedia of Mathematics, Vol. 17, Addison-Wesley (1986).

[8] Salomaa A., Jewels of Formal Language Theory, Computer Science Press, (1981).

[9] Zimin A. I., Blocking sets of terms, Mat. Sbornik, Vol. 119, No. 3, 363-375, (1982) (in Russian). Also 84d:20072 in the Mathematical Reviews on the Web.