Encoding of Multiple Inheritance Hierarchies and Partial Orders
Yves Caseau, Michel Habib, Lhouari Nourine, Olivier Raynaud · Computational Intelligence · 1999
Efficient implementation of type inclusion is an important feature of object 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 inclusion 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 type hierarchy. In this paper, we show that most known bit‐vector encoding methods can be inserted on a general theoretical framework using graph coloration, namely the notion of a simple encoding . We use the word simple because all these methods are heuristics for the general bit‐vector encoding problem, known as the 2‐dimension problem. First we provide a correct algorithm for partial orders based on simple encoding, improving the algorithm of Krall, Vitek, and Horspool (1997). Second we show that finding an optimal simple encoding is an NP‐hard problem. We end with a discussion on some practical issues.