Definition n(n +1) Let us recursively define matrix pairs Rn, Un of dimensions m and m n, respectively, with n of the form 2k with kN+, as follows 1. n=2: =

2n 2. n=2k: =Refinement( R2n, ) where Rn fnm(R1n(n)) R1n n n fnm(R2 (n -1)) R1n 2n U a) R2n =, = (m is the number of columns of Rn) n 0 U n fnm(Rn (1)) R1n 0 Rn m b) fkm :{0,1} [Rm Rk ], that is to say fkm (v1..vm ), returns a matrix —a linear mapping— of dimensions k m. fkm is defined such that the k rows are precisely the argument vector (v …v ):

1 m v1 … … vm fkm (v1..vm ) = v … … vm 2n c) Refinement( R2n, ) is a two-phase process.

i. Extension steps: as many consecutive extension steps are executed on the matrix R2n as necessary to assure that each row of the blocks fnm(Rin (n - i +1)),i = 1...n, and the blocks R1n have just one 1. The extension steps should be bound to sets of columns C that include either columns of the left-hand blocks only—blocks of the form fnm(Rin (n - i +1))— or columns of the right-hand blocks —of the form R1n.

Let R'2n, '2n denote the matrices resulting from executing these extension steps.

2n The matrix '2n is actually the final matrix U that we aim to define, as it is unaffected by the second phase of the Refinement process.

Fourth International Conference I.TECH 2006 2n Note: We have proved that the number of extension steps needed to construct R2n, U is exactly n n n 2 + -1 + -1 +... +1.

2 22 2n ii. Rearrangement: the product of the matrices R2n, is a matrix S2n from which it likewise follows that the product of the matrices R'2n, '2n is S2n, as it has already been demonstrated that the extension steps do not affect the product of the matrices. Assuming this result, this phase involves rearranging the matrix R'2n by means of the multiplication IS H R'2n, where IS H is the matrix that holds for 2 n 2 n 2 n 2 n 2n 2n IS H S = H. Finally, the matrix R1n that we are trying to define is precisely 2 n 2 n R2n = IS H R'2n.

2 n 2 n Note: the existence of the matrix IS H is straightforwardly deduced from the existence of the matrix 2 n 2 n c IH S, since if the expression corresponding to I is Iic Iic... Iik, jk, where c is the 2 n 2 n 2 n 2 n 1, j1 2, j H S c number of rows of H2n, then IS H = Iik, jk... Iic Iic.

2 n 2 n 2, j 2 1, jRemarks 2n 2n a) From the definitions of the matrices Tn, S2n, H2n R2n, it follows that R2n x =S2n b) As a consequence, and by definition of Rn, Un, it holds that Rn Un = Hn.

c) The maximum number of 1s present in each row of Rn is 2, whatever the value of n.

d) Let n = 2k+1 for a certain natural number k. The number of extension steps that are executed in the n n n Refinement phase of the matrices construction process is 2 + -1 + -1 +... +1.

2 22 n(n +1) e) Let A, B be two matrices of 0s and 1s, such that A B = Sn, of dimensions m and m n, respectively.

The execution of an extension step associated with the column and row sets C= {c …c}, F={f …f } of A, 1 l 1 q respectively, leads to a change in the total number of 1s present in the two matrices according to the following expression:

+ q - (l q). If the value of bi, j + q - (l q) is greater than 0 then the total number bi, j iC, j{1...n} iC, j{1..n} of 1s in the matrices increases; if the value is equal to 0 then the number of 1s is unchanged, and if the value is less than 0 the total number of 1s decreases.

As a consequence, each extension step executed in the Refinement phase of the process of constructing our matrices given in Definition 13 decreases the total sum of the number of 1s present in the two matrices.

Information Models Theorem n(n +1) Let Rn, Un be matrices of dimensions m and m n, respectively, with n of the form 2k with kN+, as defined in Definition 13.

Let #Rn, #Un denote the number of 1s in the matrices Rn and Un respectively.

It holds that 3 3 #Rn + #Un = n2 - n log2 n + n - 2log2 n - 2 2 n(n +1) This represents a constant average complexity for the set of + n Retrieve and Update operations.

As regards the number of variables z …z required by the solution defined by our matrices as a function of the 1 m problem size n. Let Var(n) denote this number of variables, which, as we know, is the same as the number of columns and rows of Rn and Un respectively. It holds that m = n log2 n - 2n + 2log2 n + Proof For the proof of these results, see [5].

Bibliography [1] D.J. Volper, M.L. Fredman, Query Time Versus Redundancy Trade-offs for Range Queries, Journal of Computer and System Sciences 23, (1981) pp.355--365.

[2] W.A. Burkhard, M.L. Fredman, D.J.Kleitman, Inherent complexity trade-offs for range query problems, Theoretical Computer science, North Holland Publishing Company 16, (1981) pp.279--290.

[3] M.L. Fredman, The Complexity of Maintaining an Array and Computing its Partial Sums, J.ACM, Vol.29, No.1 (1982) pp.250--260.

[4] A. Toni, Lower Bounds on Zero-one Matrices, Linear Algebra and its Applications, 376 (2004) 275--282.

[5] A. Toni, Complejidad y Estructuras de Datos para el problema de los rangos variables, Doctoral Thesis, Facultad de Informtica, Universidad Politcnica de Madrid, 2003.

[6] A. Toni, Matricial Model for the Range Query Problem and Lower Bounds on Complexity, submitted.

Authors' Information Adriana Toni – e-mail: atoni@fi.upm.es J.B. Castellanos – e-mail: jcastellanos@fi.upm.es Jose Joaquin Erviti – e-mail: jerviti@fi.upm.es Facultad de Informatica, Universidad Politecnica de Madrid, Spain Fourth International Conference I.TECH 2006 DESCRIPTION REDUCTION FOR RESTRICTED SETS OF (0,1) MATRICES Hasmik Sahakyan Abstract: Any set system can be represented as an n -cube vertices set. Restricted sets of n -cube weighted subsets are considered. The problem considered is in simple description of all set of partitioning characteristic vectors. A smaller generating sets are known as “boundary” and ”steepest” sets and finally we prove that the intersection of these two sets is also generating for the partitioning characteristic vectors.

1. Introduction In recent years, the processing of data flows has become a topic of active research in several fields of computer science. Continuous arrival of data items in rapid, potentially unbounded flows raises new challenges and research problems. The study of known combinatorial algorithms and their computational complexity for data flow conditions become an important issue.

Consider a ( 0,1) -matrix A of size m n. Let R = ( r1,,rm ) and S = ( s1,,sn ) denote the row and column sums of A respectively, and let U( R,S ) be the set of all ( 0,1) -matrices with row sums R and column sums S.

It was found by Gale and Ryser [R,1966] a necessary and sufficient condition for the existence of a ( 0,1) matrix of the class U( R,S ). This result has found a recent revival in the field of discrete tomography [H, 1997]. In discrete tomography the problem is to reconstruct a discrete valued function f from knowledge of weighted sums of function values over subsets of the domain. A much studied special case is m n ( 0,1) -matrices with known row and column sums, precisely matrices in the class U( R,S ).

As the number of matrices in this class may be high, it is of interest to study the reconstruction problem where with additional constraints on the ( 0,1) -matrices, which could either lead to a unique realization, or reduce the number of alternative solutions. The restrictions may be of different nature: requirements on rows of reconstructed matrices – to be different, some geometrical requirements such as convexity and connectivity, etc.

It is proven ([B,1996], [W,2001], [D,1999] that the existence problems of horizontal and vertical convex matrices and the existence problem for connected) matrices (polyominoes are NP-complete; and the reconstruction problem for horizontal and vertical convex polyominoes can be solved in polynomial time. At the same time the complexity of the existence problem for matrices with different rows is still an open problem [BL,1988].

We assume now that we consider the last mentioned problem for data flow conditions and the coordinates of column sum vector S might varied slowly by the data flow. Then - which are the allowable values for coordinates of S to correspond to column sum vectors Complete description of the set of all integer-value vectors, which serve as column sum vectors for ( 0,1) matrices with different rows, is given through its boundary elements [S,1997]. An alternative description of this set is known through its special elements - “steepest” vectors. The main result of this research states: the description might be given by the common (intersecting) elements of these sets - of upper boundary and steepest vectors, which minimizes the descriptor set size.

The research is supported partly by INTAS: 04-77-7173 project, http://www.intas.be Information Models 2. Problem Description Let consider the problem of existence of a ( 0,1) -matrix by the given column sums vector S and with different rows. Let assume that the coordinates of vector S is varying slightly by data flow, and then the problem is in description of all integer vectors, which serve as column sums vectors for ( 0,1) -matrices of fixed size and with different rows..

This problem has an equivalent formulation in terms of unit cube En.

Let M En be a vertex subset of fixed size M = m, 0 m 2n. An integer, nonnegative vector S = ( s1,s2,,sn ) is called the characteristic vector of partitions of set M, if its coordinates equal to the partition-subsets sizes of M by coordinates x1,x2,,xn - the Boolean variables composing En. si equals the size of one of the partition-subsets of M by the i -th direction and then m - si is the size of the complementary part of partition. To make this notation precise we will later assume that si is the size of the partition subset with xi = 1. Then the problem is in description of all integer-coordinate vectors, which serve as characteristic vectors of partitions for vertex subsets of size m.

3. Description through the Boundary Elements Let n denotes the set of all vertices of n dimensional, m +1 valued discrete cube, i.e. the set of all integerm+vectors S = ( s1,s2,,sn ) with 0 si m, i = 1,,n. The vertices are distributed schematically on the m n +1 layers of n according to their weights – sums of all coordinates. The L -th layer contains all vectors m+n S = ( s1,s2,,sn ) with L =.

i s i=Let denotes the set of all characteristic vectors of partitions of m -subsets of En. It is evident, that - m n. Let and are subsets of, consisting of all its upper and lower boundary vectors, m m+1 m m m correspondingly: ( ) is the set of all “upper” (“lower”) vectors S, for which for all R n greater m m m m+than S (less than S ), R.

m These sets of all “upper” and “lower” boundary vectors have symmetric structures - for each upper vector there exists a corresponding (opposite) lower vector, and vice versa; so that also the numbers of these vectors are equal:

= { S1,,Sr } and = { S1,,Sr }.

m m Let S and S be an arbitrary pair of opposite vectors from and correspondingly. I( S ) j j m m m j (equivalently I( S )) will denote the minimal sub-cube of n, passing through this pair of vectors. Then, j m+ I( S ) = { Q n | S Q S } (the coordinate-wise comparison is used).

j m+1 j j The following theorem states that the minimal sub-cubes passing the pairs of corresponding opposite vectors of the boundary subsets are continuously and exactly filling the vector area.

m r Theorem 1 [S,1997]: = S ).

m I( j j=Fourth International Conference I.TECH 2006 It follows that the description of is provided through the set of upper boundary vectors = { S1,,Sr } m m (correspondingly, the set of lower boundary vectors = { S1,,Sr } ). Let assume that the upper boundary m vectors are distributed between the layers Lmin and Lmax of n. Then for each layer L, Lmin L Lmax, it m+is sufficient to have all upper boundary vectors situated on that layer..

4. Description through the ”Steepest” elements Let introduce a concept of “steepest” vectors, defined for each layer.

Definition 1 [B,1988] ' Let S = ( s1,s2,,sn ) and S' = ( s1,s',,s' ) be two vectors of length n with integer, nonnegative 2 n ' components, and let s1 s2 sn and s1 s' s'. S' is an elementary flattening of S if and only 2 n if S' can be obtained from S by:

(1) finding i, j such that si s + 2 ; and then j ' (2) transferring 1 from the larger to the smaller; that is, si = si -1 and s'j = s +1 ; and then j (3) re-ordering the resulting sequence so that it is decreasing.

We mention that operation of elementary flattening doesn’t move vector from one layer of n to another.

m+Definition 2 [B,1988] ' Let S = ( s1,s2,,sn ) and S' = ( s1,s',,s' ) be two vectors of length n with integer, nonnegative 2 n ' components, and let s1 s2 sn and s1 s' s'. S' is flatter than S, and S is steeper than S', if 2 n and only if S' can be obtained from S by a non-empty sequence of elementary flattening.

S is a steepest vector if and only if there is no vector in, which is steeper than S.

m The following theorem is an extension of similar result [B, 1988], which is in terms of hypergraphs and degree sequences:

Theorem 2. If S belongs to then all vectors flatter than S also belong to.

m m Proof:

' Let S = ( s1,s2,,sn ) and S' = ( s1,s',,s' ) is flatter than S. It follows that there exists a sequence of m 2 n elementary flattening, which transfers S to S'. We prove that after each elementary flattening, the obtained vector belongs to. Let si s + 2 and after an elementary flattening we receive the vector m j ( s1,,si -1,,s +1,,sn ).

j n n n n Consider the partitioning of En by i th and j th directions. Let Exi-2, Exi-2, Exi-2, Exi-=1,x =1 =1,x =0 =0,x =1 =0,x =j j j j be the corresponding sub-cubes, and M, M, M, M - the corresponding xi =1,x =1 xi =1,x =0 xi =0,x =x =0,x =j j j i j subsets of M, belonging to these sub-cubes.

Information Models Then we have: M + M = si xi =1,x =1 xi =1,x =j j M + M = s xi =1,x =1 xi =0,x =1 j j j Hence M - M xi =1,x =0 xi =0,x =j j n Therefore there exist two vertices in M such that the corresponding vertices in Exi-2 don't belong xi =1,x =0 =0,x =j j to M. Moving one of them from M to M, will provide the necessary si -1 and s +xi =0,x =1 xi =1,x =0 xi =0,x =1 j j j j values.

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.