## 26.3. 26.3 Palindrome complexity

The palindrome complexity function of a finite or infinite word attaches to each the number of palindrome subwords of length in , denoted by .

The total palindrome complexity of a finite word is equal to the number of all nonempty palindrome subwords of , i.e.:

This is similar to the total complexity of words.

### 26.3.1. 26.3.1 Palindromes in finite words

Theorem 26.28 The total palindrome complexity of any finite word satisfies .

Proof. We proceed by induction on the length of the word . For we have .

We consider and suppose that the assertion holds for all words of length . Let be a word of length and its prefix of length . By the induction hypothesis it is true that .

If for each , the only palindrome in which is not in is , hence .

If there is an index , such that , then if and only if has suffixes which are palindromes. Let us suppose that there are at least two such suffixes and , , which are palindromes. It follows that

hence . The last palindrome appears in (because of ) and has been already counted in . It follows that .

This result shows that the total number of palindromes in a word cannot be larger than the length of that word. We examine now if there are words which are `poor' in palindromes. In the next lemma we construct finite words of arbitrary length , which contain precisely 8 palindromes.

Let us denote by the fractional power of the word of length , which is the prefix of length of .

Lemma 26.29 If , , then .

Proof. In there are the following palindromes: 0, 1, 00, 11, 010, 101, 0110, 1001. Because 010 and 101 are situated in between 0 on the left and 1 on the right, these cannot be continued to obtain any palindromes. The same is true for 1001 and 0110, which are situated between 1 on the left and 0 on the right, excepting the cases when 1001 is a suffix. So, there are no other palindromes in .

Remark 26.30 If is a circular permutation of and then too. Because we can interchange with , for any there will be at least words of length with total complexity equal to .

We shall give now, beside the upper delimitation from Theorem 26.28, lower bounds for the number of palindromes contained in finite binary words. (In the trivial case of a -letter alphabet it is obvious that, for any word , .)

Theorem 26.31 If is a finite word of length on a -letter alphabet, then

Proof. Up to 8 the computation can be made by a computer program. For , Lemma 26.29 gives words for which . The maximum value is obtained for words of the form .

Remark 26.32 For all the short binary words (up to ), the palindrome complexity takes the maximum possible value given in Theorem 26.28; from the words with , only four (out of ) have , namely , and their complemented words.

In the following lemmas we construct binary words which have a given total palindrome complexity greater than or equal to .

Lemma 26.33 If for and , then .

Proof. In the prefix of length of there are always palindromes (). The other palindromes different from these are , , , , and (for ), respectively (for ). In each case .

Lemma 26.34 If for and , then .

Proof. Since , the prefix of is at least , which includes the palindromes , , , , , and , hence . The palindromes and are situated between and , while and are between and (excepting the cases when they are suffixes), no matter how large is . It follows that contains no other palindromes, hence .

Remark 26.35 If , then the word is equal to , with defined in Lemma 26.29.

We can determine now precisely the image of the restriction of the palindrome complexity function to , .

Theorem 26.36 Let be a binary alphabet. Then

Proof. Having in mind the result in Theorem 26.31, we have to prove only that for each and so that , there exists always a binary word of length for which the total palindrome complexity is . Let and be given so that . We denote and .

If , we take (from Lemma 26.33); if , (from Lemma 26.34). It follows that and .

Example 26.2 Let us consider and . Then , . Because , we use , whose total palindrome complexity is .

We give similar results for the case of alphabets with letters.

Theorem 26.37 If is a finite word of length over a -letter () alphabet, then

Proof. For it can be checked directly. Let us consider now and a word of length at least . If this is a trivial word (containing only one letter times), its total palindrome complexity is . If in the word there appear exactly two letters and , it will have as palindromes those two letters and at least one of , , or , hence again . If the word contains a third letter, then obviously . So, the total complexity cannot be less then .

Theorem 26.38 Let be a -letter () alphabet. Then for

Proof. It remains to prove that for each and so that , there exists always a word of length , for which the total palindrome complexity is . Such a word is , which has palindromes in its prefix of length , and other two palindromes and in what follows.

### 26.3.2. 26.3.2 Palindromes in infinite words

#### 26.3.2.1.  Sturmian words

The number of palindromes in the infinite Sturmian words is given by the following theorem.

Theorem 26.39 If is an infinite Sturmian word, then

#### 26.3.2.2.  Power word

Let us recall the power word as being

.

Theorem 26.40 The palindrome complexity of the power word is

where

Proof. There exist the following cases:

Case . Palindrome subwords are:

for ,

for ,    so .

Case . Palindrome subwords are:

for ,

for ,    so .

Case . Palindrome subwords are:

for ,     for ,    so .

The palindrome subwords of the power word have the following properties:

Every palindrome subword which contains both 0's and 1's occurs only once in the power word.

If we use the notations and then there are the unique decompositions:

#### 26.3.2.3.  Champernowne word

The Champernowne word is defined as the concatenation of consecutive binary written natural numbers:

.

Theorem 26.41 The palindrome complexity of the Champernowne word is

where

Proof. Any palindrome of length can be continued as and to obtain palindromes of length . This theorem results from the following: , and for we have

,

.

The following algorithm generates all palindromes up to a given length of a Sturmian word beginning with the letter , and generated by the morphism .

The idea is the following. If is the least value for which and are both of odd length (such a always exists), we consider conjugates of these words, which are palindromes (such conjugates always exists), and we define the following morphism:

Footnote. If then is a conjugate of .

,

,

where conj() produces a conjugate of , which is a palindrome.

The sequences and generate all odd length palindromes, and the sequence all even length palindromes.

If is a word, then represents the word which is obtained from by erasing its first and last letter. More generally, is obtained from by erasing its first and last letters.

`Sturmian-Palindromes(` `)`

```  1
`IF`

is even   2
`THEN`

3  let  be the least value for which  and  are both of odd length   4  let define the morphism:  and    5     6
`WHILE`

7
`DO`

8     9    10    11
`WHILE`

12
`DO`

13    14    15
`REPEAT`

`PRINT`

Printing odd length palindromes.  16      17      18
`UNTIL`

and   19    20
`WHILE`

22
`DO`

22    23    24
`REPEAT`

`PRINT`

Printing even length palindromes.  25      26
`UNTIL`

```

Because any substitution requires no more than steps, where is a constant, the algorithm is a linear one.

In the case of the Fibonacci word the morphism is defined by

, ,

and because

, , , ,

, , , ,

both being odd numbers, will be equal to 3. The word is not a palindrome, and for the morphism we will use the adequate conjugate , which is a palindrome. In this case the morphism is defined by

,

.

For example, if , the following are obtained:

, and then ,

, and ,

, and

.

 `PROBLEMS`

`26-1` `Generating function 1`

Let denote the number of sequences of length of zeros and ones, in which the first and last position is 1, and the number of adjacent zeros is at most . Prove that the generating function corresponding to is

Hint. See Subsection 26.2.1.)

`26-2` `Generating function 2`

Prove that the generating function of , the number of all -subwords of a rainbow word of length , is

(Hint. (See Subsection 26.2.1.)

`26-3` `Window complexity`

Compute the window complexity of the infinite Fibonacci word.

`26-4` `Circuits in De Bruijn graphs`

Prove that in the De Bruijn graph there exist circuits (directed cycles) of any length from 1 to .

 `CHAPTER NOTES`

The basic notions and results on combinatorics of words are given in Lothaire's [], [], [] and Fogg's books []. Neither Lothaire nor Fogg is a single author, they are pseudonyms of groups of authors. A chapter on combinatorics of words written by Choffrut and Karhumäki [] appeared in a handbook on formal languages.

The different complexities are defined as follows: total complexity in Iványi [], maximal and total maximal complexity in Anisiu, Blázsik, Kása [], -complexity in Iványi [] (called -complexity) and used also in Kása [], -complexity (called super- -complexity) in Kása [], scattered complexity in Kása [], factorization complexity in Ilie [] and window complexity in Cassaigne, Kaboré, Tapsoba [].

The power word, lower/upper maximal/total complexities are defined in Ferenczi, Kása []. In this paper a characterization of Sturmian words by upper maximal and upper total complexities (Theorem 26.11) is also given. The maximal complexity of finite words is studied in Anisiu, Blázsik, Kása []. The total complexity of finite words is described in Kása [], where the results of the Theorem 26.22 is conjectured too, and proved later by Levé and Séébold [].

Different generalized complexity measures of words are defined and studied by Iványi [] and Kása [], [], [].

The results on palindrome complexity are described in M.-C. Anisiu, V. Anisiu, Kása [] for finite words, and in Droubay, Pirillo [] for infinite words. The algorithm for palindrome generation in Sturmian words is from this paper too. Applications of complexities in social sciences are given in Elzinga [], [], and in biology in Troyanskaya et al. []. It is worth to consult other papers too, such as [], [], [], [], [] (on complexity problems) and [], [], [], [], [], [], [] (on palindromes).

The European Union and the European Social Fund under the grant agreement no. TÁMOP 4.2.1/B-09/1/KMR-2010-0003.