A Random Bag Preserving Product Operation

AbstractThe author's current research programme is the development of a modular calculus for the average-cost of data structuring. This modular calculus provides a novel foundation for the analysis of algorithms. Its applicability to the analysis of algorithms has been demonstrated at the Center for Efficiency-Oriented Languages (CEOL) through the design of the novel programming language MOQA and the associated average-case analysis tool DISTRI-TRACK [M. Schellekens, D. Hickey and G. Bollella, ACETT, a Linearly-Compositional Programming Language for (semi-)automated Average-Case analysis, IEEE Real-Time Systems Symposium - Work In Progress Session, 2004; M. Boubekeur, D. Hickey, J. Mc Enery and M. Schellekens, A new Approach for Modular Average-Case Timing of Real-Time Java Programs, Accepted for publication in WSEAS Transactions on Computers, 2007; M. Boubekeur, D. Hickey, J. Mc Enery and M. Schellekens, Towards Modular Average-Case Timing in Real-Time Languages: An Application to Real-Time Java, Accepted for publication on the 6th WSEAS International Conference on APPLIED COMPUTER SCIENCE (ACS'06), Tenerife, December, 2006; M. Schellekens, A Modular Calculus for the Average Cost of Data Structuring, Springer book to appear, 250 pages, May 2008 (to appear), M. Schellekens, Compositional Average-Case Analysis, preprint, under review, 2006]. Modular computations of the average cost of data structuring are possible through the fundamental notion of random bag preservation. Random bag preserving operations enable the constructive tracking of the data and the distribution of the data states during a MOQA computation. This in turn enables the (semi-)automated derivation of the average cost of the operations. Two fundamental MOQA operations enable the creation and destruction of data structures: the MOQA product operation, which is the subject of this paper, and the MOQA delete operation, which forms the subject of [M. Schellekens, Compositional Average-Case Analysis, preprint, under review, 2006]. The introduction of the entire MOQA language is well beyond the scope of this paper and will be reported in a book [M. Schellekens, A Modular Calculus for the Average Cost of Data Structuring, Springer book to appear, 250 pages, May 2008 (to appear)]. The language has been implemented at CEOL and automated derivations of average-cost of data structuring are under way. Here we report on a (simplified) version of the fundamental notion of random bag preservation and demonstrate that the central MOQA product operation possesses this crucial property