Premium
Encoding of Multiple Inheritance Hierarchies and Partial Orders
Author(s) -
Caseau Yves,
Habib Michel,
Nourine Lhouari,
Raynaud Olivier
Publication year - 1999
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/0824-7935.00081
Subject(s) - encoding (memory) , simple (philosophy) , embedding , mathematics , theoretical computer science , heuristics , computer science , bit array , algorithm , multiple inheritance , type (biology) , artificial intelligence , mathematical optimization , object oriented programming , ecology , philosophy , epistemology , biology , programming language
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.