Encoding of multiple inheritance hierarchies and partial orders

Efficient implementation of type inclusion is an important feature of objec t oriented programming languages with multiple inheritance. The idea is to associate to each type a subset of a set S = {1,..., k} such that type incl usion coincides with subset inclusion. Such an embedding of types into 2(S) (the lattice of all subsets of S) is called a bit-vector encoding of the t ype hierarchy. In this paper, we show that most known bit-vector encoding m ethods can be inserted on a general theoretical framework using graph color ation, namely the notion of a simple encoding. We use the word simple becau se all these methods are heuristics for the general bit-vector encoding pro blem, known as the 2-dimension problem. First we provide a correct algorith m for partial orders based on simple encoding, improving the algorithm of K rall, Vitek, and Horspool (1997). Second we show that finding an optimal si mple encoding is an NP-hard problem. We end with a discussion on some pract ical issues.