## 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.