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 [ 162 ], [ 163 ], [ 164 ] and Fogg's books [ 77 ]. 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 [ 51 ] appeared in a handbook on formal languages.

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

The power word, lower/upper maximal/total complexities are defined in Ferenczi, Kása [ 74 ]. 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 [ 6 ]. The total complexity of finite words is described in Kása [ 141 ], where the results of the Theorem 26.22 is conjectured too, and proved later by Levé and Séébold [ 160 ].

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

The results on palindrome complexity are described in M.-C. Anisiu, V. Anisiu, Kása [ 5 ] for finite words, and in Droubay, Pirillo [ 65 ] 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 [ 69 ], [ 68 ], and in biology in Troyanskaya et al. [ 278 ]. It is worth to consult other papers too, such as [ 9 ], [ 45 ], [ 62 ], [ 73 ], [ 251 ] (on complexity problems) and [ 2 ], [ 13 ], [ 29 ], [ 33 ], [ 38 ], [ 59 ], [ 273 ] (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.