Block Decomposition of Inheritance Hierarchies

. Inheritance hierarchies play a central role in object oriented languages as in knowledge representation systems. These hierarchies are acyclic directed graphs representing the underline structure of objects. This paper is devoted to the study of efficient algorithms to decompose recursively an inheritance hierarchy into independent subgraphs which are inheritance hierarchies themselves. This process gives a tree called decomposition tree. The decomposition proposed here is based on the concept of block which is an extension of the concept of h-module proposed by R. Ducournau and M. Habib [7]. M. Habib, M. Huchard and J. Spinrad [8] have presented a linear algorithm to decompose an inheritance hierarchy into h-modules. The algorithm proposed here to decompose an inheritance hierarchy into blocks generalizes the algorithm of Habib et al.. It computes a linear extension of the hierarchy such that the blocks are factors of the extension. This is a general technique applicable to differen..