Two-dimensional arrays with maximal complexity

Mira Anisiu
(original), paper

Abstract


We present natural bounds for the complexity function of two-dimensional arrays, and we study the shape of the maximal complexity function.
Some problems concerning the existence of maximal arrays are discussed.

Authors

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

Antal Iványi
Faculty of Informatics of Eötvös Loránd University, Budapest, Hungary

Keywords

?

Paper coordinates

M.-C. Anisiu, A. Iványi, Two-dimensional arrays with maximal complexity, Pure Math. Appl., 17 (2006) nos. 3-4, 197-204.

PDF

https://ictp.acad.ro/anisiu/papers/2006-Anisiu-Ivanyi-Two-Dim.pdf

http://www.bke.hu/puma/17_3/AnisiuIvanyi.pdf

About this paper

Journal

PU.M.A

Publisher Name
DOI
Print ISSN
Online ISSN

google scholar link

[1] M.-C. Anisiu, Finite words with special complexity properties, Pure Math. Appl., 13 (2002), 31–37.
[2] M.-C. Anisiu, Z. Blázsik and Z. Kása, Maximal complexity of finite words, Pure Math. Appl., 13 (2002), 39–48.
[3] M.-C. Anisiu and J. Cassaigne, Properties of the complexity function for finite words, Revue Anal. Numér. Théor. Approx., 33 (2) (2004), 123–139.
[4] N.G. de Bruijn, A combinatorial problem, Proc. Kon. Ned. Akad. Wetensch., 49 (1946), 758–764.
[5] A. Carpi and A. de Luca, Words and special factors, Theor. Comp. Sci., 259 (2001), 145–182.
[6] J. Cassaigne, Subword complexity and periodicity in two and more dimensions. In: Developments in Language Theory, (Proc. of 4th Int. Conf. DLT, Aachen, 1999). Eds. G. Rosenberg and W. Thomas, World Scientific Publishing, River Edge, NJ, 2000, 14–21.
[7] L.J. Cummings and D. Wiedemann, Embedded de Bruijn sequences, Congr. Numer., 53 (1986), 155–160.
[8] J. Dénes and A.D. Keedwell, Frequency allocation for a mobile radio telephone system, IEEE Trans. Communications, 36 (1988), 765–767.
[9] T. Etzion, Construction of perfect maps and pseudo-random arrays, IEEE Trans. Inf. Theory, 34 (1988), 1308–1316.
[10] C.T. Fan, S.M. Fan, S.L. Ma and M.K. Siu, On de Bruijn arrays, Ars Combin., 19A (1985), 205–213.
[11] S. Ferenczi and Z. Kása, Complexity of finite and infinite words, Theor. Comp. Sci., 218 (1999), 177–195.
[12] M. Harvit, Spectrometric imager, Appl. Optics, 10 (1971), 1415–1421.
[13] M. Heinz, Zur Teilwortkomplexität für Wörter und Folgen über einem endlichen Alphabet, EIK, 13 (1977), 27–38.
[14] A. Iványi, On the d-complexity of words, Annales Univ. Sci. Budapest., Sect. Comput., 8 (1987), 69–90.
[15] A. Iványi, Construction of infinite de Bruijn arrays, Discr. Appl. Math., 22 (1988/89), 289–293.
[16] A. Iványi, Construction of three-dimensional perfect matrices, Ars Combin., 29C (1990), 33–40.
[17] A. Iványi and Z. Tóth, Construction of planar de Bruijn words. In: Papers on Automata and Languages, (ed. by I. Peák), pp. 63–69. Karl Marx Univ. of Economics, Budapest, 1988.
[18] S. Jaeger, R. Lima and B. Mossé, Symbolic analysis of finite words. In: The complexity function, Bull. Braz. Soc. Math. New Series 34 (2003), 457–477.
[19] Z. Kása, On d-complexity of strings, Pure Math. Appl., 9 (1–2) (1998), 119–128.
[20] F. Levé and P. Séébold, Proof of a conjecture on word complexity, Journées Montoises d’Informatique Théorique (Marne-la-Valée, 2000), Bull. Belg. Math. Soc. Simon Stevin, 8 (2001), 277–291.
[21] A. de Luca, On the combinatorics of finite words, Theor. Comp. Sci., 218 (1) (1999), 13–29.
[22] S.L. Ma, A note on binary arrays with certain window property, IEEE Trans. Inform. Theory, 30 (1984), 774–775.
[23] M.H. Martin, A problem of arrangements, Bull. Amer. Math. Soc., 40 (1934), 859–864.
[24] C.J. Mitchell, Aperiodic and semi-periodic perfect maps, IEEE Trans. Inform. Theory, 41 (1995), 88–95.
[25] C.J. Mitchell and K.G. Paterson, Decoding perfect maps, Des. Codes Cryptogr., 4 (1994), 11–30.
[26] K.G. Paterson, Perfect maps, IEEE Trans. Inform. Theory, 40 (1994), 743–753.
[27] J. Shallit, On the maximum number of distinct factors in a binary string, Graphs Comb., 9 (2) (1993), 197–200.

2006-Anisiu-Ivanyi-Two-Dim

Two-dimensional arrays with maximal complexity

Mira-Cristiana AnisiuTiberiu Popoviciu Institute of Numerical AnalysisRomanian AcademyP.O. Box 68, 400110 Cluj-Napoca, Romaniae-mail: mira@math.ubbcluj.roandAntal IványiFaculty of Informatics of Eötvös Loránd UniversityH-1117 Budapest, Hungary, Pázmány Peter sétány 1 / C 1 / C 1//C1 / \mathrm{C}1/C.e-mail: tony@inf.elte.hu

(Received: July 12-15, 2006)

Abstract

We present natural bounds for the complexity function of two-dimensional arrays, and we study the shape of the maximal complexity function. Some problems concerning the existence of maximal arrays are discussed.

Mathematics Subject Classifications (2000). 68R15, 05B20

1 Introduction

Arrays with elements from given sets of symbols have various applications, e.g. in frequency allocation of multibeam satellites [8], in designing mask configuration for spectrometers [12] and in cryptography [25]. In [22] possible applications in picture coding and processing are suggested.
Complexity is one of the important characteristics of such arrays. As the measure of the complexity we use the subarray complexity introduced by S. L. Ma [22] which is a natural generalization of the subword complexity defined by M. Heinz [13]. There are other measures as d d ddd-complexity [14, 19] or pattern complexity [6], and results in more dimensions [6, 9, 10, 15, 16, 22] too. Oneand two-dimensional enumerative results can be found in [17].
In this paper we consider maximal and perfect arrays, and give conditions for their existence.

2 Definitions

Let q ≥ 2 q ≥ 2 q >= 2q \geq 2q≥2 be a positive integer and X = { 0 , 1 , … , q − 1 } X = { 0 , 1 , … , q − 1 } X={0,1,dots,q-1}X=\{0,1, \ldots, q-1\}X={0,1,…,q−1} an alphabet. Let X M × N X M × N X^(M xx N)X^{M \times N}XM×N denote the set of q q qqq-ary M × N M × N M xx NM \times NM×N arrays ( M , N ≥ 1 M , N ≥ 1 M,N >= 1M, N \geq 1M,N≥1 positive integers), and X ∗ ∗ = ∪ M , N ≥ 1 X M × N X ∗ ∗ = ∪ M , N ≥ 1 X M × N X^(****)=uu_(M,N >= 1)X^(M xx N)X^{* *}=\cup_{M, N \geq 1} X^{M \times N}X∗∗=∪M,N≥1XM×N the set of finite q q qqq-ary two-dimensional arrays.
Definition 1 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. A q q qqq-ary m × n m × n m xx nm \times nm×n array B = [ b i j ] m × n B = b i j m × n B=[b_(ij)]_(m xx n)\mathcal{B}=\left[b_{i j}\right]_{m \times n}B=[bij]m×n is a subarray of the q q qqq-ary M × N M × N M xx NM \times NM×N array A = [ a k l ] M × N A = a k l M × N A=[a_(kl)]_(M xx N)\mathcal{A}=\left[a_{k l}\right]_{M \times N}A=[akl]M×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 b i j = a r + i − 1 , s + j − 1 , 1 ≤ i ≤ m , 1 ≤ j ≤ n b i j = a r + i − 1 , s + j − 1 , 1 ≤ i ≤ m , 1 ≤ j ≤ n b_(ij)=a_(r+i-1,s+j-1),1 <= i <= m,1 <= j <= nb_{i j}=a_{r+i-1, s+j-1}, 1 \leq i \leq m, 1 \leq j \leq nbij=ar+i−1,s+j−1,1≤i≤m,1≤j≤n.
According to this definition only nonempty arrays can be ( m , n m , n m,nm, nm,n )-subarrays.
We remark that we are dealing with aperiodic q q qqq-ary M × N M × N M xx NM \times NM×N arrays (written on a planar surface, with all the subarrays situated completely within the borders of the array). Another point of view is to consider the given array wrapped round on itself (written on a torus), hence a periodic array. Existence results for periodic and aperiodic arrays which contain every rectangular subarray of given sizes precisely once are given by Paterson [26], respectively Mitchell [24].
Notions of complexity similar to those for words can be introduced for arrays.
Definition 2 Let A ∈ X M × N A ∈ X M × N AinX^(M xx N)\mathcal{A} \in X^{M \times N}A∈XM×N be a q q qqq-ary array and m , n m , n m,nm, nm,n 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. Let D A ( m , n ) D A ( m , n ) D_(A)(m,n)D_{\mathcal{A}}(m, n)DA(m,n) denote the set of different m × n m × n m xx nm \times nm×n subarrays of A A A\mathcal{A}A. The subarray complexity function, or, simply, the complexity function C A : { 1 , 2 , … , M } × { 1 , 2 , … , N } → N C A : { 1 , 2 , … , M } × { 1 , 2 , … , N } → N C_(A):{1,2,dots,M}xx{1,2,dots,N}rarrNC_{\mathcal{A}}:\{1,2, \ldots, M\} \times\{1,2, \ldots, N\} \rightarrow \mathbb{N}CA:{1,2,…,M}×{1,2,…,N}→N of A A A\mathcal{A}A is
(1) C A ( m , n ) = | D A ( m , n ) | , m = 1 , 2 , … , M , n = 1 , 2 , … , N , (1) C A ( m , n ) = D A ( m , n ) , m = 1 , 2 , … , M , n = 1 , 2 , … , N , {:(1)C_(A)(m","n)=|D_(A)(m,n)|","quad m=1","2","dots","M","n=1","2","dots","N",":}\begin{equation*} C_{\mathcal{A}}(m, n)=\left|D_{\mathcal{A}}(m, n)\right|, \quad m=1,2, \ldots, M, n=1,2, \ldots, N, \tag{1} \end{equation*}(1)CA(m,n)=|DA(m,n)|,m=1,2,…,M,n=1,2,…,N,
and the total complexity function T A T A T_(A)T_{\mathcal{A}}TA of A A A\mathcal{A}A is
(2) T A = ∑ m = 1 M ∑ n = 1 N C A ( m , n ) . (2) T A = ∑ m = 1 M   ∑ n = 1 N   C A ( m , n ) . {:(2)T_(A)=sum_(m=1)^(M)sum_(n=1)^(N)C_(A)(m","n).:}\begin{equation*} T_{\mathcal{A}}=\sum_{m=1}^{M} \sum_{n=1}^{N} C_{\mathcal{A}}(m, n) . \tag{2} \end{equation*}(2)TA=∑m=1M∑n=1NCA(m,n).
The one-dimensional complexity and total complexity functions were introduced by M. Heinz [13] in 1977, and studied later by many authors (see e.g. recent papers [ 1 , 2 , 3 , 5 , 11 , 18 , 19 , 20 , 21 , 27 ] ) [ 1 , 2 , 3 , 5 , 11 , 18 , 19 , 20 , 21 , 27 ] ) [1,2,3,5,11,18,19,20,21,27])[1,2,3,5,11,18,19,20,21,27])[1,2,3,5,11,18,19,20,21,27]).
Example 3 Let X = { 0 , 1 , 2 , 3 , 4 , 5 } X = { 0 , 1 , 2 , 3 , 4 , 5 } X={0,1,2,3,4,5}X=\{0,1,2,3,4,5\}X={0,1,2,3,4,5} be an alphabet and
A 1 = ( 0 0 0 0 0 0 ) , A 2 = ( 0 1 0 0 0 2 ) , A 3 = ( 0 1 2 3 4 5 ) . A 1 = 0      0      0 0      0      0 , A 2 = 0      1      0 0      0      2 , A 3 = 0      1      2 3      4      5 . A_(1)=([0,0,0],[0,0,0]),quadA_(2)=([0,1,0],[0,0,2]),quadA_(3)=([0,1,2],[3,4,5]).\mathcal{A}_{1}=\left(\begin{array}{lll} 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right), \quad \mathcal{A}_{2}=\left(\begin{array}{lll} 0 & 1 & 0 \\ 0 & 0 & 2 \end{array}\right), \quad \mathcal{A}_{3}=\left(\begin{array}{lll} 0 & 1 & 2 \\ 3 & 4 & 5 \end{array}\right) .A1=(000000),A2=(010002),A3=(012345).
Then T A 1 = 6 , T A 2 = 15 T A 1 = 6 , T A 2 = 15 T_(A_(1))=6,T_(A_(2))=15T_{\mathcal{A}_{1}}=6, T_{\mathcal{A}_{2}}=15TA1=6,TA2=15, and T A 3 = 18 T A 3 = 18 T_(A_(3))=18T_{\mathcal{A}_{3}}=18TA3=18.
Definition 4 The q q qqq-ary M × N M × N M xx NM \times NM×N array A A A\mathcal{A}A is ( q , m , n q , m , n q,m,nq, m, nq,m,n )-extremal if
(3) C A ( m , n ) = max B ∈ X M × N C B ( m , n ) . (3) C A ( m , n ) = max B ∈ X M × N   C B ( m , n ) . {:(3)C_(A)(m","n)=max_(BinX^(M xx N))C_(B)(m","n).:}\begin{equation*} C_{\mathcal{A}}(m, n)=\max _{\mathcal{B} \in X^{M \times N}} C_{\mathcal{B}}(m, n) . \tag{3} \end{equation*}(3)CA(m,n)=maxB∈XM×NCB(m,n).
Definition 5 The q q qqq-ary M × N M × N M xx NM \times NM×N array A A A\mathcal{A}A is ( q , m , n q , m , n q,m,nq, m, nq,m,n )-perfect if it contains each of the q m n q m n q^(mn)q^{m n}qmn possible m × n q m × n q m xx nqm \times n qm×nq-ary arrays as a subarray exactly once.
Definition 6 The arrays consisting of identical letters are called homogeneous arrays, the arrays consisting of different letters are called rainbow arrays.
We mention that a q q qqq-ary M × N M × N M xx NM \times NM×N rainbow array exists if and only if q ≥ M N q ≥ M N q >= MNq \geq M Nq≥MN. It is obvious that ( q , m , n q , m , n q,m,nq, m, nq,m,n )-extremal arrays always exist in X M × N X M × N X^(M xx N)X^{M \times N}XM×N for arbitrary values of M , N M , N M,NM, NM,N, while ( q , m , n q , m , n q,m,nq, m, nq,m,n )-perfect arrays can exist only for M , N M , N M,NM, NM,N satisfying q m n = ( M − m + 1 ) ( N − n + 1 ) q m n = ( M − m + 1 ) ( N − n + 1 ) q^(mn)=(M-m+1)(N-n+1)q^{m n}=(M-m+1)(N-n+1)qmn=(M−m+1)(N−n+1).
Definition 7 The function H q , M , N : { 1 , 2 , … , M } × { 1 , 2 , … , N } → N H q , M , N : { 1 , 2 , … , M } × { 1 , 2 , … , N } → N H_(q,M,N):{1,2,dots,M}xx{1,2,dots,N}rarrNH_{q, M, N}:\{1,2, \ldots, M\} \times\{1,2, \ldots, N\} \rightarrow \mathbb{N}Hq,M,N:{1,2,…,M}×{1,2,…,N}→N given by
(4) H q , M , N ( m , n ) = min { q m n , ( M − m + 1 ) ( N − n + 1 ) } (4) H q , M , N ( m , n ) = min q m n , ( M − m + 1 ) ( N − n + 1 ) {:(4)H_(q,M,N)(m","n)=min{q^(mn),(M-m+1)(N-n+1)}:}\begin{equation*} H_{q, M, N}(m, n)=\min \left\{q^{m n},(M-m+1)(N-n+1)\right\} \tag{4} \end{equation*}(4)Hq,M,N(m,n)=min{qmn,(M−m+1)(N−n+1)}
is called maximal complexity function.
Definition 8 The q q qqq-ary M × N M × N M xx NM \times NM×N array A A A\mathcal{A}A is ( q , m , n q , m , n q,m,nq, m, nq,m,n )-maximal if
(5) C A ( m , n ) = H q , M , N ( m , n ) ; (5) C A ( m , n ) = H q , M , N ( m , n ) ; {:(5)C_(A)(m","n)=H_(q,M,N)(m","n);:}\begin{equation*} C_{\mathcal{A}}(m, n)=H_{q, M, N}(m, n) ; \tag{5} \end{equation*}(5)CA(m,n)=Hq,M,N(m,n);
it is maximal if (5) holds for all m = 1 , 2 , … , M , n = 1 , 2 , … , N m = 1 , 2 , … , M , n = 1 , 2 , … , N m=1,2,dots,M,n=1,2,dots,Nm=1,2, \ldots, M, n=1,2, \ldots, Nm=1,2,…,M,n=1,2,…,N.

3 Bounds

We present the natural bounds of the complexity function for q q qqq-ary arrays A ∈ X M × N A ∈ X M × N AinX^(M xx N)\mathcal{A} \in X^{M \times N}A∈XM×N, as well as those of the total complexity function.
Proposition 9 For each q q qqq-ary M × N M × N M xx NM \times NM×N array A A A\mathcal{A}A we have
(6) 1 ≤ C A ( m , n ) ≤ min { q m n , ( M − m + 1 ) ( N − n + 1 ) } m = 1 , 2 , … , M , n = 1 , 2 , … , N . (6) 1 ≤ C A ( m , n ) ≤ min q m n , ( M − m + 1 ) ( N − n + 1 ) m = 1 , 2 , … , M , n = 1 , 2 , … , N . {:[(6)1 <= C_(A)(m","n) <= min{q^(mn),(M-m+1)(N-n+1)}],[m=1","2","dots","M","n=1","2","dots","N.]:}\begin{gather*} 1 \leq C_{\mathcal{A}}(m, n) \leq \min \left\{q^{m n},(M-m+1)(N-n+1)\right\} \tag{6}\\ m=1,2, \ldots, M, n=1,2, \ldots, N . \end{gather*}(6)1≤CA(m,n)≤min{qmn,(M−m+1)(N−n+1)}m=1,2,…,M,n=1,2,…,N.
The lower bound is sharp for homogeneous arrays and the upper bound is sharp for rainbow arrays. The total complexity of A A A\mathcal{A}A satisfies the inequality
(7) M N ≤ T A ≤ ∑ i = 1 M ∑ j = 1 N H q , M , N ( i , j ) (7) M N ≤ T A ≤ ∑ i = 1 M   ∑ j = 1 N   H q , M , N ( i , j ) {:(7)MN <= T_(A) <= sum_(i=1)^(M)sum_(j=1)^(N)H_(q,M,N)(i","j):}\begin{equation*} M N \leq T_{\mathcal{A}} \leq \sum_{i=1}^{M} \sum_{j=1}^{N} H_{q, M, N}(i, j) \tag{7} \end{equation*}(7)MN≤TA≤∑i=1M∑j=1NHq,M,N(i,j)
Proof. From the definition of the subarray it follows that C A ( m , n ) ≥ 1 , m = 1 , 2 , … , M , n = 1 , 2 , … , N C A ( m , n ) ≥ 1 , m = 1 , 2 , … , M , n = 1 , 2 , … , N C_(A)(m,n) >= 1,m=1,2,dots,M,n=1,2,dots,NC_{\mathcal{A}}(m, n) \geq 1, m= 1,2, \ldots, M, n=1,2, \ldots, NCA(m,n)≥1,m=1,2,…,M,n=1,2,…,N; for a homogeneous array the equality holds.
It is obvious that the complexity C A ( m , n ) C A ( m , n ) C_(A)(m,n)C_{\mathcal{A}}(m, n)CA(m,n) cannot exceed the total number of subarrays over X X XXX, that is q m n q m n q^(mn)q^{m n}qmn; it also cannot exceed the total number of subarrays of dimension m × n m × n m xx nm \times nm×n of the given array (possible not all different), namely ( M − m + 1 M − m + 1 M-m+1M-m+1M−m+1 ) ( N − n + 1 N − n + 1 N-n+1N-n+1N−n+1 ). It follows that 1 ≤ C A ( m , n ) ≤ min { q m n , ( M − m + 1 ) ( N − n + 1 ) } , m = 1 , 2 , … , M , n = 1 , 2 , … , N 1 ≤ C A ( m , n ) ≤ min q m n , ( M − m + 1 ) ( N − n + 1 ) , m = 1 , 2 , … , M , n = 1 , 2 , … , N 1 <= C_(A)(m,n) <= min{q^(mn),(M-m+1)(N-n+1)},m=1,2,dots,M,n=1,2,dots,N1 \leq C_{\mathcal{A}}(m, n) \leq \min \left\{q^{m n},(M-m+1)(N-n+1)\right\}, m=1,2, \ldots, M, n=1,2, \ldots, N1≤CA(m,n)≤min{qmn,(M−m+1)(N−n+1)},m=1,2,…,M,n=1,2,…,N. For a rainbow array R R R\mathcal{R}R we have C R ( m , n ) = ( M − m + 1 ) ( N − n + 1 ) = min { q m n , ( M − m + 1 ) ( N − n + 1 ) } C R ( m , n ) = ( M − m + 1 ) ( N − n + 1 ) = min q m n , ( M − m + 1 ) ( N − n + 1 ) } C_(R)(m,n)=(M-m+1)(N-n+1)=min{q^(mn),(M:}-m+1)(N-n+1)}C_{\mathcal{R}}(m, n)=(M-m+1)(N-n+1)=\min \left\{q^{m n},(M\right. -m+1)(N-n+1)\}CR(m,n)=(M−m+1)(N−n+1)=min{qmn,(M−m+1)(N−n+1)}.
By summing up the inequalities (6) we obtain (7).
Remark 10 In terms of the maximal complexity functions, inequality (6) may be reformulated as
1 ≤ C A ( m , n ) ≤ H q , M , N ( m , n ) , m = 1 , 2 , … , M , n = 1 , 2 , … , N . 1 ≤ C A ( m , n ) ≤ H q , M , N ( m , n ) , m = 1 , 2 , … , M , n = 1 , 2 , … , N . 1 <= C_(A)(m,n) <= H_(q,M,N)(m,n),quad m=1,2,dots,M,quad n=1,2,dots,N.1 \leq C_{\mathcal{A}}(m, n) \leq H_{q, M, N}(m, n), \quad m=1,2, \ldots, M, \quad n=1,2, \ldots, N .1≤CA(m,n)≤Hq,M,N(m,n),m=1,2,…,M,n=1,2,…,N.
It follows that every ( q , m , n q , m , n q,m,nq, m, nq,m,n )-perfect array, as well as any rainbow array, is ( q , m , n q , m , n q,m,nq, m, nq,m,n )-maximal.
The values of the complexity and total complexity for homogeneous and rainbow arrays can be easily computed.
Proposition 11 If H H H\mathcal{H}H is a homogeneous M × N M × N M xx NM \times NM×N array and R R R\mathcal{R}R is an M × N M × N M xx NM \times NM×N rainbow array, then
C H ( m , n ) = 1 , C R ( m , n ) = ( M − m + 1 ) ( N − n + 1 ) , m = 1 , 2 , … , M , n = 1 , 2 , … , N C H ( m , n ) = 1 , C R ( m , n ) = ( M − m + 1 ) ( N − n + 1 ) , m = 1 , 2 , … , M , n = 1 , 2 , … , N {:[C_(H)(m","n)=1","quadC_(R)(m","n)=(M-m+1)(N-n+1)","],[m=1","2","dots","M","n=1","2","dots","N]:}\begin{gathered} C_{\mathcal{H}}(m, n)=1, \quad C_{\mathcal{R}}(m, n)=(M-m+1)(N-n+1), \\ m=1,2, \ldots, M, n=1,2, \ldots, N \end{gathered}CH(m,n)=1,CR(m,n)=(M−m+1)(N−n+1),m=1,2,…,M,n=1,2,…,N
and
T H = M N , T R = M ( M + 1 ) N ( N + 1 ) 4 . T H = M N , T R = M ( M + 1 ) N ( N + 1 ) 4 . T_(H)=MN,quadT_(R)=(M(M+1)N(N+1))/(4).T_{\mathcal{H}}=M N, \quad T_{\mathcal{R}}=\frac{M(M+1) N(N+1)}{4} .TH=MN,TR=M(M+1)N(N+1)4.
Proof. The complexity functions C H C H C_(H)C_{\mathcal{H}}CH and C R C R C_(R)C_{\mathcal{R}}CR were given in the proof of Proposition 9. Easy calculations give the formulas for T H T H T_(H)T_{\mathcal{H}}TH and T R T R T_(R)T_{\mathcal{R}}TR.
The shape of the complexity function for words was proved in [ 21 , 20 , 18 , 3 ] [ 21 , 20 , 18 , 3 ] [21,20,18,3][21,20,18,3][21,20,18,3] to be trapezoidal, i.e. it has an ascending part, possibly a horizontal one, and the last part is a descending line. The main feature is that after becoming constant, the complexity function of an arbitrary word cannot increase again. The question for arrays is: for a fixed m 0 m 0 m_(0)m_{0}m0, is C A ( m 0 , ⋅ ) C A m 0 , ⋅ C_(A)(m_(0),*)C_{\mathcal{A}}\left(m_{0}, \cdot\right)CA(m0,⋅) still trapezoidal? For m 0 = 1 m 0 = 1 m_(0)=1m_{0}=1m0=1, the answer is positive, as a consequence of the mentioned result for words; nevertheless, this is not true for all the values m 0 = 1 , 2 , … , M m 0 = 1 , 2 , … , M m_(0)=1,2,dots,Mm_{0}=1,2, \ldots, Mm0=1,2,…,M. The array A A A\mathcal{A}A in the following example has the property that C A ( 2 , ⋅ ) C A ( 2 , ⋅ ) C_(A)(2,*)C_{\mathcal{A}}(2, \cdot)CA(2,⋅) increases again after becoming a constant.
Example 12 For the array A ∈ { 0 , 1 } 3 × 19 A ∈ { 0 , 1 } 3 × 19 Ain{0,1}^(3xx19)\mathcal{A} \in\{0,1\}^{3 \times 19}A∈{0,1}3×19 given by
A = ( 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 ) A = 1      0      0      0      0      1      0      0      0      0      0      1      0      0      0      0      0      0      1 1      1      1      1      1      1      1      1      1      1      1      1      1      1      1      1      1      1      1 0      0      0      1      1      1      1      0      1      1      0      0      1      0      1      0      0      0      0 A=([1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,1,1,1,1,0,1,1,0,0,1,0,1,0,0,0,0])\mathcal{A}=\left(\begin{array}{lllllllllllllllllll} 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \end{array}\right)A=(100001000001000000111111111111111111110001111011001010000)
one has C A ( 2 , 4 ) = C A ( 2 , 5 ) = 21 , C A ( 2 , 6 ) = C A ( 2 , 7 ) = 22 C A ( 2 , 4 ) = C A ( 2 , 5 ) = 21 , C A ( 2 , 6 ) = C A ( 2 , 7 ) = 22 C_(A)(2,4)=C_(A)(2,5)=21,C_(A)(2,6)=C_(A)(2,7)=22C_{\mathcal{A}}(2,4)=C_{\mathcal{A}}(2,5)=21, C_{\mathcal{A}}(2,6)=C_{\mathcal{A}}(2,7)=22CA(2,4)=CA(2,5)=21,CA(2,6)=CA(2,7)=22 and C A ( 2 , 8 ) = 21 C A ( 2 , 8 ) = 21 C_(A)(2,8)=21C_{\mathcal{A}}(2,8)=21CA(2,8)=21.

4 Properties of the maximal complexity function

We shall describe some properties of the function H q , M , N H q , M , N H_(q,M,N)H_{q, M, N}Hq,M,N related to the shape of its graph, namely its monotonicity and its maximum.
For M = 1 M = 1 M=1M=1M=1 (or N = 1 N = 1 N=1N=1N=1 ) the arrays are in fact finite sequences (words). It was shown in [ 2 , 3 , 21 ] [ 2 , 3 , 21 ] [2,3,21][2,3,21][2,3,21] that for a given N N NNN we have
H q , 1 , N ( 1 , n ) = { q n , n ≤ k N − n + 1 , k + 1 ≤ n ≤ N H q , 1 , N ( 1 , n ) = q n , n ≤ k N − n + 1 , k + 1 ≤ n ≤ N H_(q,1,N)(1,n)={[q^(n)","n <= k],[N-n+1","k+1 <= n <= N]:}H_{q, 1, N}(1, n)=\left\{\begin{array}{l} q^{n}, n \leq k \\ N-n+1, k+1 \leq n \leq N \end{array}\right.Hq,1,N(1,n)={qn,n≤kN−n+1,k+1≤n≤N
where k k kkk is the only natural number for which q k + k ≤ N < q k + 1 + k + 1 q k + k ≤ N < q k + 1 + k + 1 q^(k)+k <= N < q^(k+1)+k+1q^{k}+k \leq N<q^{k+1}+k+1qk+k≤N<qk+1+k+1. The maximum of H q , 1 , N H q , 1 , N H_(q,1,N)H_{q, 1, N}Hq,1,N is equal to N − k N − k N-kN-kN−k and is attained at the unique point k + 1 k + 1 k+1k+1k+1 for q k + k < N ≤ q k + 1 + k + 1 q k + k < N ≤ q k + 1 + k + 1 q^(k)+k < N <= q^(k+1)+k+1q^{k}+k<N \leq q^{k+1}+k+1qk+k<N≤qk+1+k+1, and at both k k kkk and k + 1 k + 1 k+1k+1k+1 for N = q k + k N = q k + k N=q^(k)+kN=q^{k}+kN=qk+k, hence H q , 1 , N H q , 1 , N H_(q,1,N)H_{q, 1, N}Hq,1,N is trapezoidal.
In the remaining part of this section we shall consider proper arrays (with M , N ≥ 2 ) M , N ≥ 2 ) M,N >= 2)M, N \geq 2)M,N≥2).
REMARK 13 If both sizes of the array are smaller than the cardinal of the alphabet X ( M , N ≤ q ) X ( M , N ≤ q ) X(M,N <= q)X(M, N \leq q)X(M,N≤q), we have
( M − m + 1 ) ( N − n + 1 ) ≤ q 2 ≤ q m n for m n ≠ 1 ( M − m + 1 ) ( N − n + 1 ) ≤ q 2 ≤ q m n  for  m n ≠ 1 (M-m+1)(N-n+1) <= q^(2) <= q^(mn)" for "mn!=1(M-m+1)(N-n+1) \leq q^{2} \leq q^{m n} \text { for } m n \neq 1(M−m+1)(N−n+1)≤q2≤qmn for mn≠1
hence
H q , M , N ( m , n ) = { min { q , M N } , m = n = 1 ( M − m + 1 ) ( N − n + 1 ) , otherwise. H q , M , N ( m , n ) = min { q , M N } , m = n = 1 ( M − m + 1 ) ( N − n + 1 ) ,  otherwise.  H_(q,M,N)(m,n)={[min{q","MN}","m=n=1],[(M-m+1)(N-n+1)","" otherwise. "]:}H_{q, M, N}(m, n)=\left\{\begin{array}{l} \min \{q, M N\}, m=n=1 \\ (M-m+1)(N-n+1), \text { otherwise. } \end{array}\right.Hq,M,N(m,n)={min{q,MN},m=n=1(M−m+1)(N−n+1), otherwise. 
The maximum will be given by
H max = max { min { q , M N } , N ( M − 1 ) , M ( N − 1 ) } H max = max { min { q , M N } , N ( M − 1 ) , M ( N − 1 ) } H_(max)=max{min{q,MN},N(M-1),M(N-1)}H_{\max }=\max \{\min \{q, M N\}, N(M-1), M(N-1)\}Hmax=max{min{q,MN},N(M−1),M(N−1)}
and will be attained at one of the points ( 1 , 1 ) , ( 1 , 2 ) ( 1 , 1 ) , ( 1 , 2 ) (1,1),(1,2)(1,1),(1,2)(1,1),(1,2) or ( 2 , 1 ) ( 2 , 1 ) (2,1)(2,1)(2,1). If q < M N q < M N q < MNq<M Nq<MN, we have H max = max { q , N ( M − 1 ) , M ( N − 1 ) } H max  = max { q , N ( M − 1 ) , M ( N − 1 ) } H_("max ")=max{q,N(M-1),M(N-1)}H_{\text {max }}=\max \{q, N(M-1), M(N-1)\}Hmax =max{q,N(M−1),M(N−1)}; if q ≥ M N , H max = M N = h ( 1 , 1 ) q ≥ M N , H max  = M N = h ( 1 , 1 ) q >= MN,H_("max ")=MN=h(1,1)q \geq M N, H_{\text {max }}=M N= h(1,1)q≥MN,Hmax =MN=h(1,1).
In what follows we shall consider max { M , N } > q max { M , N } > q max{M,N} > q\max \{M, N\}>qmax{M,N}>q.
Proposition 14 Let m 0 ∈ { 1 , … , M } m 0 ∈ { 1 , … , M } m_(0)in{1,dots,M}m_{0} \in\{1, \ldots, M\}m0∈{1,…,M} be fixed; the function H q , M , N ( m 0 , ⋅ ) H q , M , N m 0 , ⋅ H_(q,M,N)(m_(0),*)H_{q, M, N}\left(m_{0}, \cdot\right)Hq,M,N(m0,⋅) is trapezoidal, the horizontal part containing at most two points; the last part is a descending line and the maximum of H q , M , N ( m 0 , ⋅ ) H q , M , N m 0 , ⋅ H_(q,M,N)(m_(0),*)H_{q, M, N}\left(m_{0}, \cdot\right)Hq,M,N(m0,⋅) is attained at the first point d m 0 d m 0 d_(m_(0))d_{m_{0}}dm0 situated on the descending line, or on d m 0 − 1 d m 0 − 1 d_(m_(0))-1d_{m_{0}}-1dm0−1.
Proof. The values of H q , M , N ( m 0 , n ) , n ∈ { 1 , … , N } H q , M , N m 0 , n , n ∈ { 1 , … , N } H_(q,M,N)(m_(0),n),n in{1,dots,N}H_{q, M, N}\left(m_{0}, n\right), n \in\{1, \ldots, N\}Hq,M,N(m0,n),n∈{1,…,N} are given by the minimum of the values of an increasing exponential and of a descending line. At the beginning, if ( M − m 0 + 1 ) N > q m 0 , H q , M , N ( m 0 , ⋅ ) M − m 0 + 1 N > q m 0 , H q , M , N m 0 , ⋅ (M-m_(0)+1)N > q^(m_(0)),H_(q,M,N)(m_(0),*)\left(M-m_{0}+1\right) N>q^{m_{0}}, H_{q, M, N}\left(m_{0}, \cdot\right)(M−m0+1)N>qm0,Hq,M,N(m0,⋅) will be situated on the exponential, and surely it will end on the descending line. Therefore H q , M , N ( m 0 , ⋅ ) H q , M , N m 0 , ⋅ H_(q,M,N)(m_(0),*)H_{q, M, N}\left(m_{0}, \cdot\right)Hq,M,N(m0,⋅) will have a trapezoidal shape, with a horizontal part with at most two points.
There will be a point d m 0 ≤ N d m 0 ≤ N d_(m_(0)) <= Nd_{m_{0}} \leq Ndm0≤N which is the least value of n n nnn for which H q , M , N ( m 0 , n ) H q , M , N m 0 , n H_(q,M,N)(m_(0),n)H_{q, M, N}\left(m_{0}, n\right)Hq,M,N(m0,n) is on the descending line, i.e. if d m 0 > 1 d m 0 > 1 d_(m_(0)) > 1d_{m_{0}}>1dm0>1
( M − m 0 + 1 ) ( N − d m 0 + 1 ) ≤ q m 0 d m 0 ( M − m 0 + 1 ) ( N − d m 0 + 2 ) ≥ q m 0 ( d m 0 − 1 ) M − m 0 + 1 N − d m 0 + 1 ≤ q m 0 d m 0 M − m 0 + 1 N − d m 0 + 2 ≥ q m 0 d m 0 − 1 {:[(M-m_(0)+1)(N-d_(m_(0))+1) <= q^(m_(0)d_(m_(0)))],[(M-m_(0)+1)(N-d_(m_(0))+2) >= q^(m_(0)(d_(m_(0))-1))]:}\begin{aligned} & \left(M-m_{0}+1\right)\left(N-d_{m_{0}}+1\right) \leq q^{m_{0} d_{m_{0}}} \\ & \left(M-m_{0}+1\right)\left(N-d_{m_{0}}+2\right) \geq q^{m_{0}\left(d_{m_{0}}-1\right)} \end{aligned}(M−m0+1)(N−dm0+1)≤qm0dm0(M−m0+1)(N−dm0+2)≥qm0(dm0−1)
The maximal value of H q , M , N ( m 0 , ⋅ ) H q , M , N m 0 , ⋅ H_(q,M,N)(m_(0),*)H_{q, M, N}\left(m_{0}, \cdot\right)Hq,M,N(m0,⋅) will be given by
μ m 0 = max { q m 0 ( d m 0 − 1 ) , ( M − m 0 + 1 ) ( N − d m 0 + 1 ) } μ m 0 = max q m 0 d m 0 − 1 , M − m 0 + 1 N − d m 0 + 1 mu_(m_(0))=max{q^(m_(0)(d_(m_(0))-1)),(M-m_(0)+1)(N-d_(m_(0))+1)}\mu_{m_{0}}=\max \left\{q^{m_{0}\left(d_{m_{0}}-1\right)},\left(M-m_{0}+1\right)\left(N-d_{m_{0}}+1\right)\right\}μm0=max{qm0(dm0−1),(M−m0+1)(N−dm0+1)}
The maximum of H q , M , N H q , M , N H_(q,M,N)H_{q, M, N}Hq,M,N over { 1 , … , M } × { 1 , … , N } { 1 , … , M } × { 1 , … , N } {1,dots,M}xx{1,dots,N}\{1, \ldots, M\} \times\{1, \ldots, N\}{1,…,M}×{1,…,N} will be then H max = max { μ m : m ∈ { 1 , … , M } } H max = max μ m : m ∈ { 1 , … , M } H_(max)=max{mu_(m):m in{1,dots,M}}H_{\max }= \max \left\{\mu_{m}: m \in\{1, \ldots, M\}\right\}Hmax=max{μm:m∈{1,…,M}}.
Remark 15 The maximum of H q , M , N H q , M , N H_(q,M,N)H_{q, M, N}Hq,M,N can be attained at a unique point (for example H 2 , 4 , 5 ( 2 , 2 ) = 12 ) H 2 , 4 , 5 ( 2 , 2 ) = 12 {:H_(2,4,5)(2,2)=12)\left.H_{2,4,5}(2,2)=12\right)H2,4,5(2,2)=12) or at several points ( H 2 , 4 , 2 ( 1 , 2 ) = H 2 , 4 , 2 ( 2 , 1 ) = H 2 , 4 , 2 ( 3 , 1 ) = 4 ) H 2 , 4 , 2 ( 1 , 2 ) = H 2 , 4 , 2 ( 2 , 1 ) = H 2 , 4 , 2 ( 3 , 1 ) = 4 (H_(2,4,2)(1,2)=H_(2,4,2)(2,1)=:}{:H_(2,4,2)(3,1)=4)\left(H_{2,4,2}(1,2)=H_{2,4,2}(2,1)=\right. \left.H_{2,4,2}(3,1)=4\right)(H2,4,2(1,2)=H2,4,2(2,1)=H2,4,2(3,1)=4).

5 On the existence of maximal arrays

In [3] it was proved, using the results in [4, 7, 23, 27] that there exist finite words with maximal complexity, of any given length; it follows that there are M × 1 M × 1 M xx1M \times 1M×1 and 1 × N 1 × N 1xx N1 \times N1×N maximal arrays for all positive integers M M MMM and N N NNN. More than that, in [2] the number of the words with maximal complexity is presented. Nevertheless, if both M M MMM and N N NNN are ≥ 2 ≥ 2 >= 2\geq 2≥2, the situation differs, as the following proposition shows.
Proposition 16 There are sizes M , N ≥ 2 M , N ≥ 2 M,N >= 2M, N \geq 2M,N≥2 for which there are no arrays with maximal complexity.
Proof. For M = N = 4 M = N = 4 M=N=4M=N=4M=N=4 calculations show that the total complexity T A T A T_(A)T_{\mathcal{A}}TA of any 4 × 4 4 × 4 4xx44 \times 44×4 array is ≤ 69 ≤ 69 <= 69\leq 69≤69, while ∑ i = 1 4 ∑ j = 1 4 H 2 , 4 , 4 ( i , j ) = 70 ∑ i = 1 4   ∑ j = 1 4   H 2 , 4 , 4 ( i , j ) = 70 sum_(i=1)^(4)sum_(j=1)^(4)H_(2,4,4)(i,j)=70\sum_{i=1}^{4} \sum_{j=1}^{4} H_{2,4,4}(i, j)=70∑i=14∑j=14H2,4,4(i,j)=70. It follows that for each 4 × 4 4 × 4 4xx44 \times 44×4 array A A A\mathcal{A}A there exists at least one pair ( m , n ) ( m , n ) (m,n)(m, n)(m,n) for which C A ( m , n ) < H 2 , 4 , 4 ( m , n ) C A ( m , n ) < H 2 , 4 , 4 ( m , n ) C_(A)(m,n) < H_(2,4,4)(m,n)C_{\mathcal{A}}(m, n)< H_{2,4,4}(m, n)CA(m,n)<H2,4,4(m,n).
Open question Find the pairs M , N M , N M,NM, NM,N for which there exist maximal arrays in X ∗ ∗ X ∗ ∗ X^(****)X^{* *}X∗∗.
The result in Proposition 16 prevents us from obtaining a q q qqq-ary array with maximal complexity for any M M MMM and N ≥ 2 N ≥ 2 N >= 2N \geq 2N≥2. A further question is: given M , N M , N M,NM, NM,N and m ≤ M , n ≤ N m ≤ M , n ≤ N m <= M,n <= Nm \leq M, n \leq Nm≤M,n≤N, is there an M × N M × N M xx NM \times NM×N array A m , n A m , n A_(m,n)\mathcal{A}_{m, n}Am,n which is ( q , m , n q , m , n q,m,nq, m, nq,m,n )-maximal?
A partial answer is given in [24]: in the binary case, if ( M − m + 1 ) ( N − n + 1 ) = 2 m n ( M − m + 1 ) ( N − n + 1 ) = 2 m n (M-m+1)(N-n+1)=2^(mn)(M-m+1)(N-n+1)= 2^{m n}(M−m+1)(N−n+1)=2mn, there exists a M × N M × N M xx NM \times NM×N array which is ( 2 , m , n ) ( 2 , m , n ) (2,m,n)(2, m, n)(2,m,n)-maximal (in fact it is ( 2 , m , n ) ( 2 , m , n ) (2,m,n)(2, m, n)(2,m,n) perfect).
Acknowledgment. The research of the first author was supported by the program GAR 13/2006 in the frame of academic exchange between the Hungarian Academy of Science and the Romanian Academy.

References

[1] M.-C. Anisiu, Finite words with special complexity properties, Pure Math. Appl., 13 (2002), 31-37.
[2] M.-C. Anisiu, Z. Blázsik and Z. Kása, Maximal complexity of finite words, Pure Math. Appl., 13 (2002), 39-48.
[3] M.-C. Anisiu and J. Cassaigne, Properties of the complexity function for finite words, Revue Anal. Numér. Théor. Approx., 33 (2) (2004), 123-139.
[4] N.G. de Bruijn, A combinatorial problem, Proc. Kon. Ned. Akad. Wetensch., 49 (1946), 758-764.
[5] A. Carpi and A. de Luca, Words and special factors, Theor. Comp. Sci., 259 (2001), 145-182.
[6] J. Cassaigne, Subword complexity and periodicity in two and more dimensions. In: Developments in Language Theory, (Proc. of 4th Int. Conf. DLT, Aachen, 1999). Eds. G. Rosenberg and W. Thomas, World Scientific Publishing, River Edge, NJ, 2000, 14-21.
[7] L.J. Cummings and D. Wiedemann, Embedded de Bruijn sequences, Congr. Numer., 53 (1986), 155-160.
[8] J. Dénes and A.D. Keedwell, Frequency allocation for a mobile radio telephone system, IEEE Trans. Communications, 36 (1988), 765-767.
[9] T. Etzion, Construction of perfect maps and pseudo-random arrays, IEEE Trans. Inf. Theory, 34 (1988), 1308-1316.
[10] C.T. Fan, S.M. Fan, S.L. Ma and M.K. Siu, On de Bruijn arrays, Ars Combin., 19A (1985), 205-213.
[11] S. Ferenczi and Z. Kása, Complexity of finite and infinite words, Theor. Comp. Sci., 218 (1999), 177-195.
[12] M. Harvit, Spectrometric imager, Appl. Optics, 10 (1971), 1415-1421.
[13] M. Heinz, Zur Teilwortkomplexität für Wörter und Folgen über einem endlichen Alphabet, EIK, 13 (1977), 27-38.
[14] A. Iványi, On the d d ddd-complexity of words, Annales Univ. Sci. Budapest., Sect. Comput., 8 (1987), 69-90.
[15] A. Iványi, Construction of infinite de Bruijn arrays, Discr. Appl. Math., 22 (1988/89), 289-293.
[16] A. Iványi, Construction of three-dimensional perfect matrices, Ars Combin., 29C (1990), 33-40.
[17] A. Iványi and Z. Tóth, Construction of planar de Bruijn words. In: Papers on Automata and Languages, (ed. by I. Peák), pp. 63-69. Karl Marx Univ. of Economics, Budapest, 1988.
[18] S. Jaeger, R. Lima and B. Mossé, Symbolic analysis of finite words. In: The complexity function, Bull. Braz. Soc. Math. New Series 34 (2003), 457-477.
[19] Z. Kása, On d-complexity of strings, Pure Math. Appl., 9 (1-2) (1998), 119-128.
[20] F. Levé and P. Séébold, Proof of a conjecture on word complexity, Journées Montoises d'Informatique Théorique (Marne-la-Valée, 2000), Bull. Belg. Math. Soc. Simon Stevin, 8 (2001), 277-291.
[21] A. de Luca, On the combinatorics of finite words, Theor. Comp. Sci., 218 (1) (1999), 13-29.
[22] S.L. MA, A note on binary arrays with certain window property, IEEE Trans. Inform. Theory, 30 (1984), 774-775.
[23] M.H. Martin, A problem of arrangements, Bull. Amer. Math. Soc., 40 (1934), 859-864.
[24] C.J. Mitchell, Aperiodic and semi-periodic perfect maps, IEEE Trans. Inform. Theory, 41 (1995), 88-95.
[25] C.J. Mitchell and K.G. Paterson, Decoding perfect maps, Des. Codes Cryptogr., 4 (1994), 11-30.
[26] K.G. Paterson, Perfect maps, IEEE Trans. Inform. Theory, 40 (1994), 743-753.
[27] J. Shallit, On the maximum number of distinct factors in a binary string, Graphs Comb., 9 (2) (1993), 197-200.
2006

Related Posts