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.
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 .
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 .
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 , .)
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 .
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 , .
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 .
We give similar results for the case of alphabets with letters.
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 .
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.
The number of palindromes in the infinite Sturmian words is given by the following theorem.
Let us recall the power word as being
Case . Palindrome subwords are:
for , so .
Case . Palindrome subwords are:
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:
The Champernowne word is defined as the concatenation of consecutive binary written natural numbers:
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.
IFis even 2
THEN3 let be the least value for which and are both of odd length 4 let define the morphism: and 5 6
DO8 9 10 11
DO13 14 15
UNTILand 19 20
DO22 23 24
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
, , , ,
, , , ,
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 ,
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.)
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.)
Compute the window complexity of the infinite Fibonacci word.
Circuits in De Bruijn graphs
Prove that in the De Bruijn graph there exist circuits (directed cycles) of any length from 1 to .
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 ].
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.