A generating function that counts the combinatorial full-span sub array structure of a regular array with some applications to APL

ABSTRACT

Using a radically new way of representing arrays, we present a formalism that expands (or decomposes) a regular array into a weighted sum of null arrays. We show that this "polynomial" expansion (1.16) exhaustively represents the regular full-span array sub structure of the original array. Full-span means full length in the dimensions used. The polynomial is a generating function whose coefficients of which count and indicate the shape of the regular full-span sub arrays of the given regular array. These results are all structural. They do not use knowledge of the particular data contents of the arrays. We apply this new decomposition to catenation and lamination and uncover some new insights into array structure.The decomposition and the algebraic results provide a unifying view and new formalism for regular multi-dimensional arrays. It has application wherever multi-dimensional arrays are used, particularly to generalized hyper cube architectures, OLAP hierarchical data structures, and array oriented languages. It subsumes some previous results. Some of these applications are indicated with their bibliography.There is a combinatorial argument on the shape vector that could generate the coefficients, but it does not give the structural insight of this approach.

REFERENCES

• 1: Bhuyan, L.N. and Agrawal, D.P. Generalized hypercube and hyperbus structures for a computer network. IEEE transactions on computers, C-33 (4). 323--333.
• 2: James A. Brown , Sandra Pakin , Raymond P. Polivka, APL2: at a glance, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 3: Hal Burch , Fikret Ercal, A Fast Algorithm for Complete Subcube Recognition, Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97), p.85, December 18-20, 1997
• 4: Fan, C.K. Re: Hypercubes and POW Solution, September 18--22. American Mathematical Monthly, 44. 18--22.
• 5: Frank, R.I. Regular Array Expansions in Null Arrays With Applications: Zero is Not Nothing. Pace University School of Computer Science and Information Systems, Pace University, White Plains, NY, 2002.
• 6: Gellert, W., Gottwald, S., Hellwich, M., Kästner, H. and Küstner, H. The VNR Concise Encyclopedia of Mathematics 2nd Ed. Van Nostrand Reinhold, NY, NY, 1989. ISBN 0-442-20590-2.
• 7: IBM APL LANGUAGE. GC26-3847-5 IBM, San Jose, CA, 1983.
• 8: IBM APL2 Reference Summary. SX26-3737-01 IBM, San Jose, CA, 1985.
• 9: Knopp, Konrad Theory and Application of Infinite Series, Hafner Publishing Company NY, NY 1948.
• 10: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 11: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 12: Erik Thomsen, OLAP solutions: building multidimensional information systems, John Wiley & Sons, Inc., New York, NY, 1997
• 13: Uspensky, J.V. Theory of Equations. McGraw-Hill, New York, 1948.
• 14: Ronald I. Frank, An algorithm to compute all full-span sub arrays of a regular array, Proceedings of the 2003 conference on APL: stretching the mind, p.48-58, June 11-14, 2003, San Diego, California [doi>10.1145/882067.882074]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Generating functions
      G.2.3 Applications

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Languages, Theory

Keywords:
APL, array structure, null-array expansion, sub array