Two-dimensional total palindrome complexity

Mira Anisiu
(original), paper

Abstract

We initiate a comparative study of the properties of total palindrome complexity for binary words and arrays. From this point of view, the HV-palindrome complexity for arrays seems to be more appropriate than the C-palindrome one. We prove also a theorem for the average number of HVpalindromes in arrays.

Authors

Mira-Cristiana Anisiu
Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy

Valeriu Anisiu
Faculty of Mathematics and Computer Science, Babes-Bolyai University,

Keywords

arrays; palindromes; total palindrome complexity.

Paper coordinates

M.-C. Anisiu, V. Anisiu, Two-dimensional total palindrome complexity, Annals of the Tiberiu Popoviciu Seminar of Functional Equations, Approximation and Convexity 6 (2008), 7-16

PDF

https://ictp.acad.ro/anisiu/papers/2008-Anisiu-Anisiu-TwoDim.PDF

About this paper

Journal

Annals of the Tiberiu Popoviciu Seminar
of Functional Equations, Approximation and Convexity

Publisher Name
DOI
Print ISSN

1584-4536,

Online ISSN

google scholar link

[1] J.-P. Allouche, M. Baake, J. Cassaigne and D. Damanik. Palindrome complexity, Theoret. Comput. Sci., 292 (2003) 9-31.
[2] M.-C. Anisiu, V. Anisiu and Z. K´asa. Total palindrome complexity of finite words, Preprint.
[3] M.-C. Anisiu, V. Anisiu and Z. K´asa. Properties of palindromes in finite words, Pure Math. Appl., 17 (2006) 183-195.
[4] V. Berthe and L. Vuillon. Palindromes and two-dimensional Sturmian sequences, J. Autom. Lang. Comb., 6 (2001), 121-138.
[5] J.-P. Borel and C. Reutenauer. Palindromic factors of billiard words, Theoret. Comput. Sci., 340 (2005) 334-348.
[6] E. B. Dagum and A. Luati. Asymmetric and symmetric weights of kernel smoothers and their spectral properties, Estadistica, J. Interamerican Statistical Institute, 53 (2001), 215-258.
[7] X. Droubay, J. Justin and G. Pirillo. Episturmian words and some constructions of de Luca and Rauzy, Theoret. Comput. Sci., 255 (2001), 539-553.
[8] S. Ferenczi and Z. K´asa. Complexity for finite factors of infinite sequences, Theoret. Comput. Sci., 218 (1999) 177–195.
[9] M. Giel-Pietraszuk, M. Hoffmann, S. Dolecka, J. Rychlewski and J. Barciszewski. Palindromes in proteins, J. Protein Chem., 22 (2003) 109-113.
[10] A. Ivany. On the d-complexity of words, Ann. Univ. Sci. Budapest. Sect. Comput., 8 (1987) 69–90.
[11] J. Jeuering. The derivation of on-line algorithms, with an application to finding palindromes, Algorithmica, 11 (1994), 146-184.
[12] Z. Kasa. On the d-complexity of strings, Pure Math. Appl., 9 1–2 (1998) 119–128.
[13] A. de Luca and Al. de Luca. Combinatorial properties of Sturmian palindromes, Int. J. Found. Comput. Sci., 17 (2006) 557-573.

2008-Anisiu-Anisiu-TwoDim.PDF
Annals of the Tiberiu Popoviciu Seminar of Functional Equations, Approximation and Convexity ISSN 1584-4536, vol 6, 2008, pp. 3-12.

Two-dimensional Total Palindrome Complexity

Mira-Cristiana Anisiu Valeriu Anisiu(Cluj-Napoca) (Vluj-Napoca)

Abstract

We initiate a comparative study of the properties of total palindrome complexity for binary words and arrays. From this point of view, the HV-palindrome complexity for arrays seems to be more appropriate than the C-palindrome one. We prove also a theorem for the average number of HVpalindromes in arrays.

Key Words: arrays, palindromes, total palindrome complexity
MSC 2000: 68R15

1 Introduction

Several authors have studied the palindrome complexity of infinite words (see [1], [5], [13] and the references therein). Similar problems related to the number of palindromes are important for finite words too. One of the reasons is that palindromes occur in DNA sequences (over 4 letters) as well as in protein description (over 20 letters), and their role
qquad\qquad
qquad\qquad
is under research ([9]). The values of the total palindrome complexity and the properties of the average number of palindromes have been investigated in [2], [3].
In section 2 we remind some facts related to the palindrome complexity of finite words. Section 3 contains some numerical results concerning the palindrome complexity of two-rows binary arrays, which show that these arrays have similar properties to words; a theorem for the average number of palindromes in arrays is proved.

2 Palindromes in words

Let a positive integer q ≥ 1 q ≥ 1 q >= 1q \geq 1q≥1 and an alphabet A = { 0 , 1 , … , q − 1 } A = { 0 , 1 , … , q − 1 } A={0,1,dots,q-1}A=\{0,1, \ldots, q-1\}A={0,1,…,q−1} be given. For the word w = a 1 … a n w = a 1 … a n w=a_(1)dotsa_(n)w=a_{1} \ldots a_{n}w=a1…an with a i ∈ A , 1 ≤ i ≤ n a i ∈ A , 1 ≤ i ≤ n a_(i)in A,1 <= i <= na_{i} \in A, 1 \leq i \leq nai∈A,1≤i≤n, the integer n n nnn is the length of w w www and is denoted by | w | | w | |w||w||w|. The length of the empty word ε ε epsi\varepsilonε is 0 . The set of the words of length n n nnn over A A AAA will be denoted by A n A n A^(n)A^{n}An. The word u = a i … a j , 1 ≤ i ≤ j ≤ n u = a i … a j , 1 ≤ i ≤ j ≤ n u=a_(i)dotsa_(j),1 <= i <= j <= nu=a_{i} \ldots a_{j}, 1 \leq i \leq j \leq nu=ai…aj,1≤i≤j≤n is a factor (or subword) of w w www; if i = 1 i = 1 i=1i=1i=1 it is called a prefix, and if j = n j = n j=nj=nj=n a suffix of w w www. The reversal (or the mirror image) of w w www is denoted by w ~ = a n … a 1 w ~ = a n … a 1 widetilde(w)=a_(n)dotsa_(1)\widetilde{w}=a_{n} \ldots a_{1}w~=an…a1. A word which is equal to its mirror image is called a palindrome. The empty word is considered a palindrome. We denote by a k a k a^(k)a^{k}ak the word a . . . a a . . . a a...aa . . . aa...a ( k k kkk times).
Let PAL w PAL w PAL_(w)\mathrm{PAL}_{w}PALw be the set of all factors in the word w w www which are nonempty palindromes, and PAL w ( n ) = PAL w ∩ A n PAL w ( n ) = PAL w ∩ A n PAL_(w)(n)=PAL_(w)nnA^(n)\mathrm{PAL}_{w}(n)=\mathrm{PAL}_{w} \cap A^{n}PALw(n)=PALw∩An the set of the palindromes of length n n nnn contained in w w www. The (infinite) set of all palindromes over the alphabet A A AAA is denoted by PAL A PAL A PAL_(A)\mathrm{PAL}_{A}PALA, while PAL A ( n ) = PAL A ∩ A n PAL A ( n ) = PAL A ∩ A n PAL_(A)(n)=PAL_(A)nnA^(n)\mathrm{PAL}_{A}(n)=\mathrm{PAL}_{A} \cap A^{n}PALA(n)=PALA∩An is the set of all palindromes of length n n nnn over the alphabet A A AAA. It is known that the number of all palindromes of length k k kkk is q ⌈ k / 2 ⌉ q ⌈ k / 2 ⌉ q^(|~k//2~|)q^{\lceil k / 2\rceil}q⌈k/2⌉, where ⌈ ⋅ ⌉ ⌈ ⋅ ⌉ |~*~|\lceil\cdot\rceil⌈⋅⌉ denotes the ceil function (which returns the smallest integer that is greater than or equal to a specified number).

2.1 The total palindrome complexity

The palindrome complexity function pal w pal w pal_(w)\mathrm{pal}_{w}palw of a finite or infinite word w w www attaches to each n ∈ N n ∈ N n inNn \in \mathbb{N}n∈N the number of palindrome factors of length n n nnn
in w w www, hence
(2.1) pal w ( n ) = # PAL w ( n ) (2.1) pal w ( n ) = # PAL w ( n ) {:(2.1)pal_(w)(n)=#PAL_(w)(n):}\begin{equation*} \operatorname{pal}_{w}(n)=\# \operatorname{PAL}_{w}(n) \tag{2.1} \end{equation*}(2.1)palw(n)=#PALw(n)
The total palindrome complexity of a finite word w w www is equal to the number of all nonempty palindrome factors of w w www, namely
(2.2) P ( w ) = ∑ n = 1 | w | pal w ( n ) (2.2) P ( w ) = ∑ n = 1 | w |   pal w ( n ) {:(2.2)P(w)=sum_(n=1)^(|w|)pal_(w)(n):}\begin{equation*} P(w)=\sum_{n=1}^{|w|} \operatorname{pal}_{w}(n) \tag{2.2} \end{equation*}(2.2)P(w)=∑n=1|w|palw(n)
This is similar to the total complexity of words, which was extensively studied in [10], [12] for finite words and in [8] for infinite ones.
An upper bound for P ( w ) P ( w ) P(w)P(w)P(w) was given in [7].
Theorem 2.1 The total palindrome complexity P ( w ) P ( w ) P(w)P(w)P(w) of any finite word w w www satisfies P ( w ) ≤ | w | P ( w ) ≤ | w | P(w) <= |w|P(w) \leq|w|P(w)≤|w|.
This result shows that the total number of palindromes in a word cannot be larger than the length of that word. There are words of length n n nnn with P ( w ) = n P ( w ) = n P(w)=nP(w)=nP(w)=n, e. g. 0 n 0 n 0^(n)0^{n}0n, but also some which have few palindromes.
Beside the upper delimitation from Theorem 2.1, lower bounds for the number of palindromes contained in finite binary words were found. (In the trivial case of a 1 -letter alphabet it is obvious that, for any word w , P ( w ) = | w | w , P ( w ) = | w | w,P(w)=|w|w, P(w)=|w|w,P(w)=|w|.)
Theorem 2.2 [2] If w w www is a finite word of length n n nnn on a binary alphabet then P ( w ) = n P ( w ) = n P(w)=nP(w)=nP(w)=n for 1 ≤ n ≤ 7 ; 7 ≤ P ( w ) ≤ 8 1 ≤ n ≤ 7 ; 7 ≤ P ( w ) ≤ 8 1 <= n <= 7;7 <= P(w) <= 81 \leq n \leq 7 ; 7 \leq P(w) \leq 81≤n≤7;7≤P(w)≤8 for n = 8 ; 8 ≤ P ( w ) ≤ n n = 8 ; 8 ≤ P ( w ) ≤ n n=8;8 <= P(w) <= nn=8 ; 8 \leq P(w) \leq nn=8;8≤P(w)≤n for n ≥ 9 n ≥ 9 n >= 9n \geq 9n≥9.
Remark 2.1 For all the short binary words (up to | w | = 7 | w | = 7 |w|=7|w|=7|w|=7 ), the palindrome complexity takes the maximal possible value given in Theorem 2.1; from the words with | w | = 8 | w | = 8 |w|=8|w|=8|w|=8, only four (out of 2 8 2 8 2^(8)2^{8}28 ) have P ( w ) = 7 P ( w ) = 7 P(w)=7P(w)=7P(w)=7, namely 00110100, 00101100 and their complemented words, and 252 have P ( w ) = 8 P ( w ) = 8 P(w)=8P(w)=8P(w)=8. There are 24 words of length 9 and 16 of length 10 with P ( w ) = 8 P ( w ) = 8 P(w)=8P(w)=8P(w)=8; based on several numerical results, we conjecture that there are precisely 12 words of length n ≥ 11 n ≥ 11 n >= 11n \geq 11n≥11 with P ( w ) = 8 P ( w ) = 8 P(w)=8P(w)=8P(w)=8.
qquad\qquad
qquad\qquad
It can be proved that for each n ≥ 8 n ≥ 8 n >= 8n \geq 8n≥8, the restriction of the total palindrome complexity function to A n A n A^(n)A^{n}An takes all the values between 8 and n n nnn.
Theorem 2.3 [2] For each n n nnn and i i iii so that 8 ≤ i ≤ n 8 ≤ i ≤ n 8 <= i <= n8 \leq i \leq n8≤i≤n, there exists always a binary word w n , i w n , i w_(n,i)w_{n, i}wn,i of length n n nnn for which the total palindrome complexity is P ( w n , i ) = i P w n , i = i P(w_(n,i))=iP\left(w_{n, i}\right)=iP(wn,i)=i.

2.2 The average number of palindromes

We consider an alphabet A A AAA with q ≥ 2 q ≥ 2 q >= 2q \geq 2q≥2 letters. The average number of palindromes contained in all the words of length n n nnn over A A AAA is defined by
(2.3) E q ( n ) = ∑ w ∈ A n P ( w ) q n , (2.3) E q ( n ) = ∑ w ∈ A n   P ( w ) q n , {:(2.3)E_(q)(n)=(sum_(w inA^(n))P(w))/(q^(n))",":}\begin{equation*} E_{q}(n)=\frac{\sum_{w \in A^{n}} P(w)}{q^{n}}, \tag{2.3} \end{equation*}(2.3)Eq(n)=∑w∈AnP(w)qn,
where P ( w ) P ( w ) P(w)P(w)P(w) is the total palindrome complexity of the word w w www.
The following theorems proved in [2] show that, in fact, the palindrome subwords are rather rare in long words, whatever q ≥ 2 q ≥ 2 q >= 2q \geq 2q≥2 is.
Theorem 2.4 For an alphabet A A AAA with q ≥ 2 q ≥ 2 q >= 2q \geq 2q≥2 letters, the average number of palindromes E q ( n ) E q ( n ) E_(q)(n)E_{q}(n)Eq(n) satisfies
(2.4) lim n → ∞ E q ( n ) n = 0 . (2.4) lim n → ∞   E q ( n ) n = 0 . {:(2.4)lim_(n rarr oo)(E_(q)(n))/(n)=0.:}\begin{equation*} \lim _{n \rightarrow \infty} \frac{E_{q}(n)}{n}=0 . \tag{2.4} \end{equation*}(2.4)limn→∞Eq(n)n=0.
The order of convergence for the sequence E q ( n ) / n E q ( n ) / n E_(q)(n)//nE_{q}(n) / nEq(n)/n can be obtained with the aid of a more elaborate estimation of the upper bound of E q ( n ) E q ( n ) E_(q)(n)E_{q}(n)Eq(n).
Theorem 2.5 The following inequality holds
E q ( n ) ≤ q + 1 q 1 / 2 − 1 q 1 / 4 n 1 / 2 . E q ( n ) ≤ q + 1 q 1 / 2 − 1 q 1 / 4 n 1 / 2 . E_(q)(n) <= (q+1)/(q^(1//2)-1)q^(1//4)n^(1//2).E_{q}(n) \leq \frac{q+1}{q^{1 / 2}-1} q^{1 / 4} n^{1 / 2} .Eq(n)≤q+1q1/2−1q1/4n1/2.
Remark 2.2 From Theorem 2.5 it follows that E q ( n ) = O ( n 1 / 2 ) E q ( n ) = O n 1 / 2 E_(q)(n)=O(n^(1//2))E_{q}(n)=O\left(n^{1 / 2}\right)Eq(n)=O(n1/2). For a binary alphabet ( q = 2 q = 2 q=2q=2q=2 ) we have E q ( n ) < 9 n 1 / 2 E q ( n ) < 9 n 1 / 2 E_(q)(n) < 9n^(1//2)E_{q}(n)<9 n^{1 / 2}Eq(n)<9n1/2. More generally, E q ( n ) < 6 q 3 / 4 n 1 / 2 E q ( n ) < 6 q 3 / 4 n 1 / 2 E_(q)(n) < 6q^(3//4)n^(1//2)E_{q}(n)<6 q^{3 / 4} n^{1 / 2}Eq(n)<6q3/4n1/2.

3 Palindromes in arrays

For a positive integer q ≥ 1 q ≥ 1 q >= 1q \geq 1q≥1 and an alphabet A = { 0 , 1 , … , q − 1 } A = { 0 , 1 , … , q − 1 } A={0,1,dots,q-1}A=\{0,1, \ldots, q-1\}A={0,1,…,q−1}, let A M × N A M × N A^(M xx N)A^{M \times N}AM×N denote the set of the M × N M × N M xx NM \times NM×N arrays with entries from A A AAA ( M M MMM, N ≥ 1 N ≥ 1 N >= 1N \geq 1N≥1 positive integers).
Let m m mmm and n n nnn be positive integers with 1 ≤ m ≤ M 1 ≤ m ≤ M 1 <= m <= M1 \leq m \leq M1≤m≤M and 1 ≤ n ≤ N 1 ≤ n ≤ N 1 <= n <= N1 \leq n \leq N1≤n≤N. An array V = [ v i j ] ∈ A m × n V = v i j ∈ A m × n V=[v_(ij)]inA^(m xx n)V=\left[v_{i j}\right] \in A^{m \times n}V=[vij]∈Am×n is a subarray of the array W = [ w k ℓ ] ∈ A M × N W = w k ℓ ∈ A M × N W=[w_(kℓ)]inA^(M xx N)W=\left[w_{k \ell}\right] \in A^{M \times N}W=[wkℓ]∈AM×N if there exist indices r , s r , s r,sr, sr,s such that r + m − 1 ≤ M , s + n − 1 ≤ N r + m − 1 ≤ M , s + n − 1 ≤ N r+m-1 <= M,s+n-1 <= Nr+m-1 \leq M, s+n-1 \leq Nr+m−1≤M,s+n−1≤N and v i j = w r + i − 1 , s + j − 1 v i j = w r + i − 1 , s + j − 1 v_(ij)=w_(r+i-1,s+j-1)v_{i j}=w_{r+i-1, s+j-1}vij=wr+i−1,s+j−1.
For arrays there are two definitions for palindromes, depending on the considered symmetry.
Let W = [ w k ℓ ] W = w k ℓ W=[w_(kℓ)]W=\left[w_{k \ell}\right]W=[wkℓ] with 1 ≤ k ≤ M 1 ≤ k ≤ M 1 <= k <= M1 \leq k \leq M1≤k≤M and 1 ≤ ℓ ≤ N 1 ≤ ℓ ≤ N 1 <= ℓ <= N1 \leq \ell \leq N1≤ℓ≤N. The centrosymmetric image of W W WWW is W ~ = [ w ~ k ℓ ] W ~ = w ~ k ℓ widetilde(W)=[ widetilde(w)_(kℓ)]\widetilde{W}=\left[\widetilde{w}_{k \ell}\right]W~=[w~kℓ], where w ~ k ℓ = w M − k + 1 , N − ℓ + 1 w ~ k ℓ = w M − k + 1 , N − ℓ + 1 widetilde(w)_(kℓ)=w_(M-k+1,N-ℓ+1)\widetilde{w}_{k \ell}=w_{M-k+1, N-\ell+1}w~kℓ=wM−k+1,N−ℓ+1. A C C CCC palindrome is an array for which W = W ~ W = W ~ W= widetilde(W)W=\widetilde{W}W=W~ ([4], [6]).
We define also the horizontal and vertical reverse of W W WWW as W ¯ H = [ w ¯ k ℓ H ] W ¯ H = w ¯ k ℓ H bar(W)^(H)=[ bar(w)_(kℓ)^(H)]\bar{W}^{H}= \left[\bar{w}_{k \ell}^{H}\right]W¯H=[w¯kℓH], where w ¯ k ℓ H = w M − k + 1 , ℓ w ¯ k ℓ H = w M − k + 1 , ℓ bar(w)_(kℓ)^(H)=w_(M-k+1,ℓ)\bar{w}_{k \ell}^{H}=w_{M-k+1, \ell}w¯kℓH=wM−k+1,ℓ, respectively W ¯ V = [ w ¯ k ℓ V ] W ¯ V = w ¯ k ℓ V bar(W)^(V)=[ bar(w)_(kℓ)^(V)]\bar{W}^{V}=\left[\bar{w}_{k \ell}^{V}\right]W¯V=[w¯kℓV], where w ¯ k ℓ V = w k , N − ℓ + 1 w ¯ k ℓ V = w k , N − ℓ + 1 bar(w)_(kℓ)^(V)=w_(k,N-ℓ+1)\bar{w}_{k \ell}^{V}= w_{k, N-\ell+1}w¯kℓV=wk,N−ℓ+1. An H V H V HVH VHV-palindrome is an array for which W = W ¯ H = W ¯ V W = W ¯ H = W ¯ V W= bar(W)^(H)= bar(W)^(V)W=\bar{W}^{H}=\bar{W}^{V}W=W¯H=W¯V (i. e. all its columns and rows are palindromes [11]). The number of C-palindromes is q ⌊ M N / 2 ⌋ q ⌊ M N / 2 ⌋ q^(|__ MN//2__|)q^{\lfloor M N / 2\rfloor}q⌊MN/2⌋, where ⌊ ⋅ ⌋ ⌊ ⋅ ⌋ |__*__|\lfloor\cdot\rfloor⌊⋅⌋ denotes the floor function (which returns the greatest integer that is smaller than or equal to a specified number). The number of HV-palindromes is q ⌈ M / 2 ⌉ ⋅ ⌈ N / 2 ⌉ q ⌈ M / 2 ⌉ ⋅ ⌈ N / 2 ⌉ q^(|~M//2~|*|~N//2~|)q^{\lceil M / 2\rceil \cdot\lceil N / 2\rceil}q⌈M/2⌉⋅⌈N/2⌉.
For each type of two-dimensional palindromes, let PAL W PAL W PAL_(W)\mathrm{PAL}_{W}PALW be the set of all factors in the array W W WWW which are nonempty palindromes, and PAL W ( m , n ) PAL W ( m , n ) PAL_(W)(m,n)\mathrm{PAL}_{W}(m, n)PALW(m,n) be the set of the palindromes which are m × n m × n m xx nm \times nm×n arrays contained in the array W W WWW. We shall also use the notation PAL A ( m , n ) PAL A ( m , n ) PAL_(A)(m,n)\operatorname{PAL}_{A}(m, n)PALA(m,n) for the set of all palindromes which are m × n m × n m xx nm \times nm×n arrays over the alphabet A A AAA.
Let us define the functions ( M , N ≥ 2 ) c , h , v : A M × N → A M × N ( M , N ≥ 2 ) c , h , v : A M × N → A M × N (M,N >= 2)c,h,v:A^(M xx N)rarrA^(M xx N)(M, N \geq 2) c, h, v: A^{M \times N} \rightarrow A^{M \times N}(M,N≥2)c,h,v:AM×N→AM×N, c ( W ) = W ~ , h ( W ) = W ¯ H c ( W ) = W ~ , h ( W ) = W ¯ H c(W)= widetilde(W),h(W)= bar(W)^(H)c(W)=\widetilde{W}, h(W)=\bar{W}^{H}c(W)=W~,h(W)=W¯H and v ( W ) = W ¯ V v ( W ) = W ¯ V v(W)= bar(W)^(V)v(W)=\bar{W}^{V}v(W)=W¯V.
Proposition 3.1 We have c 2 = h 2 = v 2 = id , h ∘ v = c , v ∘ c = h c 2 = h 2 = v 2 = id , h ∘ v = c , v ∘ c = h c^(2)=h^(2)=v^(2)=id,h@v=c,v@c=hc^{2}=h^{2}=v^{2}=\mathrm{id}, h \circ v=c, v \circ c=hc2=h2=v2=id,h∘v=c,v∘c=h, h ∘ c = v h ∘ c = v h@c=vh \circ c=vh∘c=v and ∘ ∘ @\circ∘ is commutative, hence the group G = { id , c , h , v } G = { id , c , h , v } G={id,c,h,v}G=\{\mathrm{id}, c, h, v\}G={id,c,h,v} is isomorphic with Klein's one. An array is a C C CCC-palindrome iff it is a fixed point of c c ccc, and is a HV-palindrome iff it is a common fixed point of h h hhh and v v vvv.
qquad\qquad
qquad\qquad

3.1 The total palindrome complexity

For each type of palindromes, we consider for W ∈ A M × N W ∈ A M × N W inA^(M xx N)W \in A^{M \times N}W∈AM×N the palindrome complexity function p W : { 1 , 2 , … , M } × { 1 , 2 , … , N } → N p W : { 1 , 2 , … , M } × { 1 , 2 , … , N } → N p_(W):{1,2,dots,M}xx{1,2,dots,N}rarrNp_{W}:\{1,2, \ldots, M\} \times\{1,2, \ldots, N\} \rightarrow \mathbb{N}pW:{1,2,…,M}×{1,2,…,N}→N of W W WWW given by
(3.1) p W ( m , n ) = # PAL W ( m , n ) , m = 1 , 2 , … , M , n = 1 , 2 , … , N , (3.1) p W ( m , n ) = # PAL W ( m , n ) , m = 1 , 2 , … , M , n = 1 , 2 , … , N , {:(3.1)p_(W)(m","n)=#PAL_(W)(m","n)","m=1","2","dots","M","n=1","2","dots","N",":}\begin{equation*} p_{W}(m, n)=\# \mathrm{PAL}_{W}(m, n), m=1,2, \ldots, M, n=1,2, \ldots, N, \tag{3.1} \end{equation*}(3.1)pW(m,n)=#PALW(m,n),m=1,2,…,M,n=1,2,…,N,
and the total palindrome complexity function P ( W ) P ( W ) P(W)P(W)P(W) of W W WWW as
(3.2) P ( W ) = ∑ m = 1 M ∑ n = 1 N p W ( m , n ) (3.2) P ( W ) = ∑ m = 1 M   ∑ n = 1 N   p W ( m , n ) {:(3.2)P(W)=sum_(m=1)^(M)sum_(n=1)^(N)p_(W)(m","n):}\begin{equation*} P(W)=\sum_{m=1}^{M} \sum_{n=1}^{N} p_{W}(m, n) \tag{3.2} \end{equation*}(3.2)P(W)=∑m=1M∑n=1NpW(m,n)
We denote by W ⋅ V W ⋅ V W*VW \cdot VW⋅V the concatenation of two arrays with the same number of rows. For a two-rows array V ∈ A 2 × N V ∈ A 2 × N V inA^(2xx N)V \in A^{2 \times N}V∈A2×N, let | V | = N | V | = N |V|=N|V|=N|V|=N denote the length of V V VVV.
Remark 3.1 We list some maximal values of the two types of total palindrome complexity, obtained by using a computer program:
M M MMM N N NNN max H V − P max H V − P max HV-P\max H V-PmaxHV−P max C − P max C − P max C-P\max C-PmaxC−P
2 4 8 9
2 5 10 11
2 6 12 14
2 7 14 16
2 8 16 19
2 9 18 21
3 4 13 15
3 5 17 19
M N max HV-P max C-P 2 4 8 9 2 5 10 11 2 6 12 14 2 7 14 16 2 8 16 19 2 9 18 21 3 4 13 15 3 5 17 19| $M$ | $N$ | $\max H V-P$ | $\max C-P$ | | :---: | :---: | :---: | :---: | | 2 | 4 | 8 | 9 | | 2 | 5 | 10 | 11 | | 2 | 6 | 12 | 14 | | 2 | 7 | 14 | 16 | | 2 | 8 | 16 | 19 | | 2 | 9 | 18 | 21 | | 3 | 4 | 13 | 15 | | 3 | 5 | 17 | 19 |
A result similar to that in Theorem 2.1 seems to hold only for arrays with two lines (or columns) and for HV-palindrome complexity (which will be denoted from now on by P ( W ) P ( W ) P(W)P(W)P(W) ).
Based on the numerical results, we state the following
Conjecture 3.1 The total HV-palindrome complexity P ( W ) P ( W ) P(W)P(W)P(W) of any finite word W ∈ A 2 × N W ∈ A 2 × N W inA^(2xx N)W \in A^{2 \times N}W∈A2×N satisfies P ( W ) ≤ 2 | W | P ( W ) ≤ 2 | W | P(W) <= 2|W|P(W) \leq 2|W|P(W)≤2|W|, where | W | = N | W | = N |W|=N|W|=N|W|=N.
We prove a result on the palindrome complexity of the concatenation of two-rows arrays.
Theorem 3.1 The following inequality holds
(3.3) P ( W ⋅ V ) ≤ P ( W ) + 3 | V | , (3.3) P ( W ⋅ V ) ≤ P ( W ) + 3 | V | , {:(3.3)P(W*V) <= P(W)+3|V|",":}\begin{equation*} P(W \cdot V) \leq P(W)+3|V|, \tag{3.3} \end{equation*}(3.3)P(W⋅V)≤P(W)+3|V|,
the constant 3 being the best possible.
Proof. When a column is added to the array W W WWW, there appear at most three new palindromes: at most one on each row, and at most one twodimensional, hence inequality (3.3) holds. For W = [ 0 0 0 1 0 0 1 0 0 0 ] W = 0 0 0 1 0 0 1 0 0 0 W=[[0,0,0,1,0],[0,1,0,0,0]]W=\left[\begin{array}{lllll}0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0\end{array}\right]W=[0001001000] and V = [ 0 0 1 0 0 1 ] V = 0 0 1 0 0 1 V=[[0,0,1],[0,0,1]]V=\left[\begin{array}{lll}0 & 0 & 1 \\ 0 & 0 & 1\end{array}\right]V=[001001], the number of palindromes in W ⋅ V W ⋅ V W*VW \cdot VW⋅V which do not appear in W W WWW is equal to 9 . These palindromes are: 0 4 , 0 5 , 0 3 10 3 , 0 2 10 2 0 4 , 0 5 , 0 3 10 3 , 0 2 10 2 0^(4),0^(5),0^(3)10^(3),0^(2)10^(2)0^{4}, 0^{5}, 0^{3} 10^{3}, 0^{2} 10^{2}04,05,03103,02102, 10 5 1 , 10 3 1 , [ 0 0 0 0 ] , [ 0 0 0 0 0 0 ] , [ 1 1 ] 10 5 1 , 10 3 1 , 0 0 0 0 , 0 0 0 0 0 0 , 1 1 10^(5)1,10^(3)1,[[0,0],[0,0]],[[0,0,0],[0,0,0]],[[1],[1]]10^{5} 1,10^{3} 1,\left[\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right],\left[\begin{array}{lll}0 & 0 & 0 \\ 0 & 0 & 0\end{array}\right],\left[\begin{array}{l}1 \\ 1\end{array}\right]1051,1031,[0000],[000000],[11].
Remark 3.2 If in (3.3) the constant would be 2 instead of 3, Conjecture 3.1 could be proved by induction, as Theorem 2.1 was.
Remark 3.3 A A AAA result as in Theorem 2.3 does not hold for two-rows arrays, because for M = 2 M = 2 M=2M=2M=2 and N = 9 N = 9 N=9N=9N=9 there are 12 arrays with 8 palindromes, but no arrays with 9 palindromes. We conjecture that this is true for M = 2 M = 2 M=2M=2M=2 and each N ≥ 9 N ≥ 9 N >= 9N \geq 9N≥9.

3.2 The average number of palindromes

The average number of HV-palindromes contained in all the arrays from A M × N , A A M × N , A A^(M xx N),AA^{M \times N}, AAM×N,A being an alphabet with q ≥ 2 q ≥ 2 q >= 2q \geq 2q≥2 letters, is defined by
E q ( M , N ) = ∑ W ∈ A M × N P ( W ) q M N E q ( M , N ) = ∑ W ∈ A M × N   P ( W ) q M N E_(q)(M,N)=(sum_(W inA^(M xx N))P(W))/(q^(MN))E_{q}(M, N)=\frac{\sum_{W \in A^{M \times N}} P(W)}{q^{M N}}Eq(M,N)=∑W∈AM×NP(W)qMN
where P ( w ) P ( w ) P(w)P(w)P(w) is the total HV-palindrome complexity of the word w w www.
qquad\qquad
qquad\qquad
Theorem 3.2 For an alphabet A A AAA with q ≥ 2 q ≥ 2 q >= 2q \geq 2q≥2 letters, the average number of palindromes E q ( M , N ) E q ( M , N ) E_(q)(M,N)E_{q}(M, N)Eq(M,N) satisfies
lim M → ∞ N → ∞ E q ( M , N ) M N = 0 . lim M → ∞ N → ∞   E q ( M , N ) M N = 0 . lim_({:[M rarr oo],[N rarr oo]:})(E_(q)(M,N))/(MN)=0.\lim _{\substack{M \rightarrow \infty \\ N \rightarrow \infty}} \frac{E_{q}(M, N)}{M N}=0 .limM→∞N→∞Eq(M,N)MN=0.
Proof. We calculate
E q ( M , N ) = E q ( M , N ) = E_(q)(M,N)=E_{q}(M, N)=Eq(M,N)=
1 q M N ∑ W ∈ A M × N ∑ Π ∈ PAL W 1 = 1 q M N ∑ W ∈ A M × N ∑ m = 1 M ∑ n = 1 N ∑ Π ∈ PAL W ( m , n ) 1 1 q M N ∑ W ∈ A M × N   ∑ Π ∈ PAL W   1 = 1 q M N ∑ W ∈ A M × N   ∑ m = 1 M   ∑ n = 1 N   ∑ Π ∈ PAL W ( m , n )   1 (1)/(q^(MN))sum_(W inA^(M xx N))sum_(Pi inPAL_(W))1=(1)/(q^(MN))sum_(W inA^(M xx N))sum_(m=1)^(M)sum_(n=1)^(N)sum_(Pi inPAL_(W)(m,n))1\frac{1}{q^{M N}} \sum_{W \in A^{M \times N}} \sum_{\Pi \in \mathrm{PAL}_{W}} 1=\frac{1}{q^{M N}} \sum_{W \in A^{M \times N}} \sum_{m=1}^{M} \sum_{n=1}^{N} \sum_{\Pi \in \mathrm{PAL}_{W}(m, n)} 11qMN∑W∈AM×N∑Π∈PALW1=1qMN∑W∈AM×N∑m=1M∑n=1N∑Π∈PALW(m,n)1.
We fix M 0 ≤ M M 0 ≤ M M_(0) <= MM_{0} \leq MM0≤M and N 0 ≤ N N 0 ≤ N N_(0) <= NN_{0} \leq NN0≤N two natural numbers. Then
E q ( M , N ) = 1 q M N ∑ W ∈ A M × N ∑ m = 1 M 0 ∑ n = 1 N 0 ∑ Π ∈ PAL W ( m , n ) 1 E q ( M , N ) = 1 q M N ∑ W ∈ A M × N   ∑ m = 1 M 0   ∑ n = 1 N 0   ∑ Π ∈ PAL W ( m , n )   1 E_(q)(M,N)=(1)/(q^(MN))sum_(W inA^(M xx N))sum_(m=1)^(M_(0))sum_(n=1)^(N_(0))sum_(Pi inPAL_(W)(m,n))1E_{q}(M, N)=\frac{1}{q^{M N}} \sum_{W \in A^{M \times N}} \sum_{m=1}^{M_{0}} \sum_{n=1}^{N_{0}} \sum_{\Pi \in \mathrm{PAL}_{W}(m, n)} 1Eq(M,N)=1qMN∑W∈AM×N∑m=1M0∑n=1N0∑Π∈PALW(m,n)1
+ 1 q M N ∑ W ∈ A M × N ∑ m > M 0 or n > N 0 ∑ Π ∈ PAL W ( m , n ) 1 = + 1 q M N ∑ W ∈ A M × N   ∑ m > M 0  or  n > N 0   ∑ Π ∈ PAL W ( m , n )   1 = +(1)/(q^(MN))sum_(W inA^(M xx N))sum_(m > M_(0)" or "n > N_(0))sum_(Pi inPAL_(W)(m,n))1=+\frac{1}{q^{M N}} \sum_{W \in A^{M \times N}} \sum_{m>M_{0} \text { or } n>N_{0}} \sum_{\Pi \in \mathrm{PAL}_{W}(m, n)} 1=+1qMN∑W∈AM×N∑m>M0 or n>N0∑Π∈PALW(m,n)1=
1 q M N ∑ m = 1 M 0 ∑ n = 1 N 0 ∑ W ∈ A M × N ∑ Π ∈ PAL W ( m , n ) 1 q M N ∑ m = 1 M 0   ∑ n = 1 N 0   ∑ W ∈ A M × N   ∑ Π ∈ PAL W ( m , n )   (1)/(q^(MN))sum_(m=1)^(M_(0))sum_(n=1)^(N_(0))sum_(W inA^(M xx N))sum_(Pi inPAL_(W)(m,n))\frac{1}{q^{M N}} \sum_{m=1}^{M_{0}} \sum_{n=1}^{N_{0}} \sum_{W \in A^{M \times N}} \sum_{\Pi \in \mathrm{PAL}_{W}(m, n)}1qMN∑m=1M0∑n=1N0∑W∈AM×N∑Π∈PALW(m,n)
+ 1 q M N ∑ m > M 0 or n > N 0 ∑ Π ∈ PAL W ( m , n ) ∑ W ∈ A M × N Π ⊆ W ≤ + 1 q M N ∑ m > M 0  or  n > N 0   ∑ Π ∈ PAL W ( m , n )   ∑ W ∈ A M × N Π ⊆ W   ≤ +(1)/(q^(MN))sum_(m > M_(0)" or "n > N_(0))sum_(Pi inPAL_(W)(m,n))sum_({:[W inA^(M xx N)],[Pi sube W]:}) <=+\frac{1}{q^{M N}} \sum_{m>M_{0} \text { or } n>N_{0}} \sum_{\Pi \in \mathrm{PAL}_{W}(m, n)} \sum_{\substack{W \in A^{M \times N} \\ \Pi \subseteq W}} \leq+1qMN∑m>M0 or n>N0∑Π∈PALW(m,n)∑W∈AM×NΠ⊆W≤
1 q M N ∑ m = 1 M 0 ∑ n = 1 N 0 q M N ⋅ q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ 1 q M N ∑ m = 1 M 0   ∑ n = 1 N 0   q M N ⋅ q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ (1)/(q^(MN))sum_(m=1)^(M_(0))sum_(n=1)^(N_(0))q^(MN)*q^(|~m//2~|*|~n//2~|)\frac{1}{q^{M N}} \sum_{m=1}^{M_{0}} \sum_{n=1}^{N_{0}} q^{M N} \cdot q^{\lceil m / 2\rceil \cdot\lceil n / 2\rceil}1qMN∑m=1M0∑n=1N0qMN⋅q⌈m/2⌉⋅⌈n/2⌉
+ 1 q M N ∑ m > M 0 or n > N 0 M , N ∑ Π ∈ PAL A ( m , n ) ( M − m + 1 ) ( N − n + 1 ) q M N − m n ≤ + 1 q M N ∑ m > M 0  or  n > N 0 M , N   ∑ Π ∈ PAL A ( m , n )   ( M − m + 1 ) ( N − n + 1 ) q M N − m n ≤ +(1)/(q^(MN))sum_(m > M_(0)" or "n > N_(0))^(M,N)sum_(Pi inPAL_(A)(m,n))(M-m+1)(N-n+1)q^(MN-mn) <=+\frac{1}{q^{M N}} \sum_{m>M_{0} \text { or } n>N_{0}}^{M, N} \sum_{\Pi \in \operatorname{PAL}_{A}(m, n)}(M-m+1)(N-n+1) q^{M N-m n} \leq+1qMN∑m>M0 or n>N0M,N∑Π∈PALA(m,n)(M−m+1)(N−n+1)qMN−mn≤
∑ m = 1 M 0 ∑ n = 1 N 0 q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ + ∑ m > M 0 or n > N 0 M , N ( M − m + 1 ) ( N − n + 1 ) q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ − m n ∑ m = 1 M 0   ∑ n = 1 N 0   q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ + ∑ m > M 0  or  n > N 0 M , N   ( M − m + 1 ) ( N − n + 1 ) q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ − m n sum_(m=1)^(M_(0))sum_(n=1)^(N_(0))q^(|~m//2~|*|~n//2~|)+sum_(m > M_(0)" or "n > N_(0))^(M,N)(M-m+1)(N-n+1)q^(|~m//2~|*|~n//2~|-mn)\sum_{m=1}^{M_{0}} \sum_{n=1}^{N_{0}} q^{\lceil m / 2\rceil \cdot\lceil n / 2\rceil}+\sum_{m>M_{0} \text { or } n>N_{0}}^{M, N}(M-m+1)(N-n+1) q^{\lceil m / 2\rceil \cdot\lceil n / 2\rceil-m n}∑m=1M0∑n=1N0q⌈m/2⌉⋅⌈n/2⌉+∑m>M0 or n>N0M,N(M−m+1)(N−n+1)q⌈m/2⌉⋅⌈n/2⌉−mn.
We obtain
E q ( M , N ) M N ≤ 1 M N ∑ m = 1 M 0 ∑ n = 1 N 0 q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ + ∑ m > M 0 or n > N 0 ∞ , ∞ q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ − m n E q ( M , N ) M N ≤ 1 M N ∑ m = 1 M 0   ∑ n = 1 N 0   q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ + ∑ m > M 0  or  n > N 0 ∞ , ∞   q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ − m n (E_(q)(M,N))/(MN) <= (1)/(MN)sum_(m=1)^(M_(0))sum_(n=1)^(N_(0))q^(|~m//2~|*|~n//2~|)+sum_(m > M_(0)" or "n > N_(0))^(oo,oo)q^(|~m//2~|*|~n//2~|-mn)\frac{E_{q}(M, N)}{M N} \leq \frac{1}{M N} \sum_{m=1}^{M_{0}} \sum_{n=1}^{N_{0}} q^{\lceil m / 2\rceil \cdot\lceil n / 2\rceil}+\sum_{m>M_{0} \text { or } n>N_{0}}^{\infty, \infty} q^{\lceil m / 2\rceil \cdot\lceil n / 2\rceil-m n}Eq(M,N)MN≤1MN∑m=1M0∑n=1N0q⌈m/2⌉⋅⌈n/2⌉+∑m>M0 or n>N0∞,∞q⌈m/2⌉⋅⌈n/2⌉−mn,
therefore lim sup M → ∞ N → ∞ E q ( M , N ) M N ≤ 0 + ∑ m > M 0 or n > N 0 ∞ , ∞ q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ − m n lim sup M → ∞ N → ∞   E q ( M , N ) M N ≤ 0 + ∑ m > M 0  or  n > N 0 ∞ , ∞   q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ − m n l i m   s u p_({:[M rarr oo],[N rarr oo]:})(E_(q)(M,N))/(MN) <= 0+sum_(m > M_(0)" or "n > N_(0))^(oo,oo)q^(|~m//2~|*|~n//2~|-mn)\limsup _{\substack{M \rightarrow \infty \\ N \rightarrow \infty}} \frac{E_{q}(M, N)}{M N} \leq 0+\sum_{m>M_{0} \text { or } n>N_{0}}^{\infty, \infty} q^{\lceil m / 2\rceil \cdot\lceil n / 2\rceil-m n}lim supM→∞N→∞Eq(M,N)MN≤0+∑m>M0 or n>N0∞,∞q⌈m/2⌉⋅⌈n/2⌉−mn.
The double series ∑ m , n q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ − m n ∑ m , n   q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ − m n sum_(m,n)q^(|~m//2~|*|~n//2~|-mn)\sum_{m, n} q^{\lceil m / 2\rceil \cdot\lceil n / 2\rceil-m n}∑m,nq⌈m/2⌉⋅⌈n/2⌉−mn is convergent (actually the inequality q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ − m n ≤ q 1 − m n 4 q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ − m n ≤ q 1 − m n 4 q^(|~m//2~|*|~n//2~|-mn) <= q^((1-mn)/(4))q^{\lceil m / 2\rceil \cdot\lceil n / 2\rceil-m n} \leq q^{\frac{1-m n}{4}}q⌈m/2⌉⋅⌈n/2⌉−mn≤q1−mn4 holds).
So, ∑ m > M 0 ∞ , ∞ ∑ m > M 0 ∞ , ∞   sum_(m > M_(0))^(oo,oo)\sum_{m>M_{0}}^{\infty, \infty}∑m>M0∞,∞ or n > N 0 q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ − m n n > N 0 q ⌈ m / 2 ⌉ ⋅ ⌈ n / 2 ⌉ − m n n > N_(0)q^(|~m//2~|*|~n//2~|-mn)n>N_{0} q^{\lceil m / 2\rceil \cdot\lceil n / 2\rceil-m n}n>N0q⌈m/2⌉⋅⌈n/2⌉−mn tends to 0 for M 0 , N 0 → ∞ M 0 , N 0 → ∞ M_(0),N_(0)rarr ooM_{0}, N_{0} \rightarrow \inftyM0,N0→∞. Hence
lim sup M → ∞ N → ∞ E q ( M , N ) M N ≤ 0 lim sup M → ∞ N → ∞   E q ( M , N ) M N ≤ 0 l i m   s u p_({:[M rarr oo],[N rarr oo]:})(E_(q)(M,N))/(MN) <= 0\limsup _{\substack{M \rightarrow \infty \\ N \rightarrow \infty}} \frac{E_{q}(M, N)}{M N} \leq 0lim supM→∞N→∞Eq(M,N)MN≤0.

References

[1] J.-P. Allouche, M. Baake, J. Cassaigne and D. Damanik. Palindrome complexity, Theoret. Comput. Sci., 292 (2003) 9-31.
[2] M.-C. Anisiu, V. Anisiu and Z. Kása. Total palindrome complexity of finite words, Preprint.
[3] M.-C. Anisiu, V. Anisiu and Z. Kása. Properties of palindromes in finite words, Pure Math. Appl., 17 (2006) 183-195.
[4] V. Berthé and L. Vuillon. Palindromes and two-dimensional Sturmian sequences, J. Autom. Lang. Comb., 6 (2001), 121-138.
[5] J.-P. Borel and C. Reutenauer. Palindromic factors of billiard words, Theoret. Comput. Sci., 340 (2005) 334-348.
[6] E. B. Dagum and A. Luati. Asymmetric and symmetric weights of kernel smoothers and their spectral properties, Estadistica, J. Interamerican Statistical Institute, 53 (2001), 215-258.
[7] X. Droubay, J. Justin and G. Pirillo. Episturmian words and some constructions of de Luca and Rauzy, Theoret. Comput. Sci., 255 (2001), 539-553.
[8] S. Ferenczi and Z. Kása. Complexity for finite factors of infinite sequences, Theoret. Comput. Sci., 218 (1999) 177-195.
qquad\qquad
qquad\qquad
[9] M. Giel-Pietraszuk, M. Hoffmann, S. Dolecka, J. Rychlewski and J. Barciszewski. Palindromes in proteins, J. Protein Chem., 22 (2003) 109-113.
[10] A. Ivány. On the d d ddd-complexity of words, Ann. Univ. Sci. Budapest. Sect. Comput., 8 (1987) 69-90.
[11] J. Jeuering. The derivation of on-line algorithms, with an application to finding palindromes, Algorithmica, 11 (1994), 146-184.
[12] Z. Kása. On the d d ddd-complexity of strings, Pure Math. Appl., 9 1-2 (1998) 119-128.
[13] A. de Luca and Al. de Luca. Combinatorial properties of Sturmian palindromes, Int. J. Found. Comput. Sci., 17 (2006) 557-573.
  1. ⋄ ⋄ ^(diamond){ }^{\diamond}⋄ Mira-Cristiana Anisiu, T. Popoviciu Institute of Numerical Analysis, Romanian Academy, email: mira@math.ubbcluj.ro
    ⋄ ⋄ ^(diamond){ }^{\diamond}⋄ Valeriu Anisiu, Faculty of Mathematics and Computer Science, Babeş-Bolyai University, email: anisiu@math.ubbcluj.ro
2008

Related Posts