BitVector Encodings of Hierarchies 
Project
One idea to achieve these tests is to associate with each element of the poset a subset of a set S={1,...,k} such that the reachability question coincides with subset inclusion. These subsets can be represented by bit vectors of size k. For this reason, these encodings are called bitvector encodings. They provide very compact encodings in terms of space and tests can be performed in "constant" time. Generating a encoding for a poset is equivalent to embedding this poset in the lattice of all the subsets of S (the hypercube of dimension k). Our work consists in studying these encodings. In particular, the minimization of the size of the encoding is a difficult problem (NPcomplete in the general case) and we interest in incremental aspects for evolving hierarchies. This work was run by Michel Habib, Lhouari Nourine, Olivier Raynaud and Eric Thierry in the Departement of Theoretical Computer Science (IFA) of the Laboratory of Computer Science, Robotics and Microelectronics of Montpellier (LIRMM). These encodings find applications in Object Oriented Languages, Databases, Knowledge Representation Systems.
