Implementation of Table Inversion Algorithms

Hong Shen

Software Engineering Research Group
CRL, McMaster University,
Hamilton, Ontario, Canada L8S 4K1


Abstract

Table inversion algorithms transform one kind of table into another, preserving the semantics. This thesis implements the table inversion algorithms proposed in [23]. Each algorithm is described by three formulas. The first represents the length of the changed header, the second specifies the cells of the changed header and the third gives the grid entries of the transformed tables. The implementation is based on the Table Holder [21]. This simplifies the implementation, since we need to concern ourselves only with the realization of the algorithms instead of with both the algorithms and the complicated data structures for expressions. An analysis of the algorithms, and the examples of the implementation, are given. We also prove the commutability of the slicing and inverting operation on normal tables.

We present a new transformation algorithm which normalizes an inverted table to a normal table, preserving its dimensionality. By this method, we can recover the original normal table from the table which was inverted by the inversion algorithm in Section 2.3.1. The complexity of the algorithm is, however, rather high. We suggest a procedure which may reduce this complexity.