The section starts with definitions, then bounds and several further properties of the complexity functions are given.
Let be a positive integer and an alphabet. Let denote the set of -ary arrays (, positive integers), and the set of finite -ary two-dimensional arrays.
According to this definition only nonempty arrays can be -subarrays.
We remark that we are dealing with aperiodic -ary 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 [ 201 ], respectively Mitchell [ 180 ].
Notions of complexity similar to those for words can be introduced for arrays.
and the total complexity function of is
The one-dimensional complexity and total complexity functions were introduced by M. Heinz [ 110 ] in 1977, and studied later by many authors (see e.g. recent papers [ 4 ], [ 6 ], [ 30 ], [ 7 ], [ 44 ], [ 74 ], [ 62 ], [ 251 ]).
Then , and .
We mention that a -ary rainbow array exists if and only if . It is obvious that -extremal arrays always exist in for arbitrary values of , , while -perfect arrays can exist only for , satisfying .
is called maximal complexity function.
it is maximal if (29.54) holds for all , .
We present the natural bounds of the complexity function for -ary arrays , as well as those of the total complexity function.
Claim 29.51 (Anisiu, Iványi [ 8 ]) For each -ary array we have
The lower bound is sharp for homogeneous arrays and the upper bound is sharp for rainbow arrays. The total complexity of satisfies the inequality
It is obvious that the complexity cannot exceed the total number of subarrays over , that is ; it also cannot exceed the total number of subarrays of dimension of the given array (possible not all different), namely . It follows that . For a rainbow array we have .
Remark 29.52 In terms of the maximal complexity functions, inequality (29.55) may be reformulated as
It follows that every -perfect array, as well as any rainbow array, is -maximal.
The values of the complexity and total complexity for homogeneous and rainbow arrays can be easily computed.
Claim 29.53 (Anisiu, Iványi [ 8 ]) If is a homogeneous array and is an rainbow array, then
Proof. The complexity functions and were given in the proof of Proposition 29.51. Easy calculations give the formulas for and .
The shape of the complexity function for words was proved in [ 62 ], [ 160 ], [ 135 ], [ 7 ] 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 , is still trapezoidal? For , the answer is positive, as a consequence of the mentioned result for words; nevertheless, this is not true for all the values . The array in the following example has the property that increases again after becoming a constant.
one has , and .
We shall describe some properties of the function related to the shape of its graph, namely its monotonicity and its maximum.
where is the only natural number for which . The maximum of is equal to and is attained at the unique point for , and at both and for , hence is trapezoidal.
In the remaining part of this section we shall consider proper arrays (with ).
The maximum will be given by
and will be attained at one of the points , or . If , we have ; if , .
In what follows we shall consider .
Claim 29.55 (Anisiu, Iványi [ 8 ]) Let be fixed; the function is trapezoidal, the horizontal part containing at most two points; the last part is a descending line and the maximum of is attained at the first point situated on the descending line, or on .
Proof. The values of are given by the minimum of the values of an increasing exponential and of a descending line. At the beginning, if , will be situated on the exponential, and surely it will end on the descending line. Therefore will have a trapezoidal shape, with a horizontal part with at most two points.
There will be a point which is the least value of for which is on the descending line, i.e. if
The maximal value of will be given by
The maximum of over will be then .
In [ 7 ] it was proved, using the results in [ 42 ], [ 58 ], [ 172 ], [ 251 ] that there exist finite words with maximal complexity, of any given length; it follows that there are and maximal arrays for all positive integers and . More than that, in [ 6 ] the number of the words with maximal complexity is presented. Nevertheless, if both and are , the situation differs, as the following proposition shows.
Claim 29.57 (Anisiu, Iványi [ 8 ]) There are sizes , for which there are no arrays with maximal complexity.
Open question Find the pairs for which there exist maximal arrays in .
The result in Proposition 29.57 prevents us from obtaining a -ary array with maximal complexity for any and . A further question is: given , and , , is there an array which is -maximal?
A partial answer is given in [ 180 ]: in the binary case, if , there exists a array which is ()-maximal (in fact it is ()-perfect).
29.10-1 Design arrays with maximal complexity for different parameters.
Comparison of the Martin-type algorithms
Write a program and compare the real running times of
(describen in the chapter on the complexity of words),
Characterization of the solutions of equation
Characterize the solutions of (29.3) for and .
Cyclic sequences in which every possible sequence of a fixed length occurs exactly once have been studied for more than a hundred years. The first proof of the existence of -perfect sequences was published by Flye-Sainte [ 76 ] in 1894. The problem was extended to arrays by Fan, Fan, Ma, and Siu in 1985 [ 72 ].
One dimensional perfect arrays are often called de Bruijn or Good sequences, since the papers of De Bruijn [ 42 ] and Good [ 94 ] make these sequences popular. Two dimensional perfect arrays were called perfect maps by Reed and Stewart in 1962 [ 232 ] and by Paterson in 1996 [ 202 ], or de Bruijn tori by Hurlbert and Isaak and Mitchell in 1993 and later [ 118 ], [ 119 ], [ 120 ].
A good and recent review on the one-dimensional results is given in Chapter Complexity of words of this volume.
The even De Bruijn sequences were introduced by A. Iványi and Z. Tóth in 1988 [ 134 ], [ 152 ]. They proposed an algorithm constructing even sequences for arbitrary alphabet size. Later Hurlbert and Isaak [ 119 ] provided an universal algorithm which constructs an infinite sequence whose prefixes are even for the corresponding alphabet size.
The concept of growing sequences was introduced by G. Hurlbert and G. Isaak [ 119 ].
The most general existence theorem of double symmetric perfect arrays can be found in [ 132 ].
Interesting properties of De Bruijn graphs are reviewed by James Bond and Antal Iványi in [ 32 ].
Carla Savage [ 248 ] analysed De Bruijn sequences as special Gray codes.
The European Union and the European Social Fund under the grant agreement no. TÁMOP 4.2.1/B-09/1/KMR-2010-0003.